해쉬테이블(Hash Table)

해쉬라는 말을 많이 들어본적이 있을텐데, 바로 인스타그램의 해쉬태그의 원리도 바로 해쉬테이블에서 파생된 것!

#나이키 라고 검색하게 되면 #나이키 에 맵핑되어 있는 모든 게시물을 가져와 보여 줄 수 있다.

해쉬 구조

키(key)에 데이터(Value)를 저장하는 데이터 구조

1. 성능이 굉장히 좋기 때문에 해쉬라는 키(기능)을 확장한 여러가지 함수, 알고리즘을 기반으로 최근 블록체인에서 많이 사용된다.

2. 키를 해쉬 함수에 넣으면 데이터가 저장되어야 할 위치를 알 수 있다.

3. 보통 배열로 Hash Table 사이즈 만큼 생성 후에 사용한다

key를 통해 바로 데이터를 가져올 수 있기 때문에 속도가 획기적으로 빨라진다.

해쉬테이블에서 알아둬야할 용어

• 해쉬(Hash): 임의 값을 고정 길이로 변환하는 것
• 해쉬 테이블(Hash Table): 키와 배열의 인덱스를 이용하여 데이터를 저장하는 자료구조이다
  (Key-Value 쌍으로 이루어지는 데이터 구조)
• 해쉬 함수(Hash Function): Key에 대한 산술 연산을 이용해 데이터 위치를 찾음
  key 값을 넣으면 해쉬 주소가 나오는 함수
• 해쉬 값 or 주소 : 해쉬테이블의 특정테이터를 저장하는 공간과 연결됨
• 슬롯 : 한개의 데이터를 저장할 수 있는 공간

여기서 나온 해쉬함수는 내가 만들거나 이미 만들어져 있는 함수를 뜻한다.

해쉬의 장단점

• 장점
  데이터 저장/읽기 속도가 빠르다(검색속도가 빠르다)
  해쉬는 키에 대한 데이터 값이 있는지 확인이 쉬움
• 단점
  일반적으로 저장공간을 많이 차지한다 (충돌을 피하기 위해 저장공간을 충분하게 세팅)
  키의 해당주소가 동일한 경우 충돌을 해결하기 위한 자료구조가 필요하다.
  (오버라이딩 될 수 있기 때문)

  위 단점의 해결방안중 하나가 바로 체이닝(chaning)으로 Linked List를 활용하여 해시 충돌시 연결리스트로 데이터를 이어놓는 방식이 있다.

해쉬의 주요 용도

• 검색이 많이 필요한 경우
• 저장, 삭제, 읽기가 빈번하게 일어나는 경우
• 캐쉬 구현할시 (중복 확인이 쉽기 때문)
  (프론트에서 메모이제이션으로 성능리팩토링을 하게 될때 사용되는 캐시가 바로 해쉬)
  캐쉬는 해쉬를 사용해 데이터가 있는지 없는지 빠르게 확인할 수 있게 된다

javascript 해시테이블 구현

function hashStringToInt(s, tableSize){
  let hash = 17;
  for (let i=0;i<s.length; i++){
    hash = (13 * hash * s.charCodeAt(i)) % tableSize
  }
  return hash
}

class HashTable {
  table = new Array(3);
  numItems = 0;

  resize = () => {
    const newTable = new Array(this.table.length * 2);
    this.table.forEach(item=>{
      if(item){
        item.forEach(([key,value])=>{
          const idx = hashStringToInt(key, newTable.length);
          if(newTable[idx]){
            newTable[idx].push([key, value])
          }else{
            newTable[idx] = [[key, value]]
          }
        })
      }
    })
    this.table = newTable
  }

  setItem = (key, value) => {
    this.numItems++;
    const loadFactor = this.numItems / this.table.length;
    if(loadFactor > 0.8){
      console.log("resize")
      this.resize()
    }

    const idx = hashStringToInt(key, this.table.length);
    if(this.table[idx]){
      this.table[idx].push([key, value])
    }else{
      this.table[idx] = [[key, value]]
    }
  }

  getItem = key => {
    const idx = hashStringToInt(key, this.table.length);
    if(!this.table[idx]){
      return null;
    }
    return this.table[idx].find(x => x[0] === key)[1];
  }
}

const myTable = new HashTable()
myTable.setItem('firstname', 'bob');
myTable.setItem('lastname', 'bobby');
myTable.setItem('age', 2);
myTable.setItem('dob', '1/2/3');
myTable.getItem('firstname');

console.log(myTable.table.length)
console.log(myTable.getItem("firstname"));
console.log(myTable.getItem("lastname"));
console.log(myTable.getItem("age"));

reference

https://ko.wikipedia.org/wiki/%ED%95%B4%EC%8B%9C_%ED%85%8C%EC%9D%B4%EB%B8%94