자료구조 Hash Table

Hash Table은 뭘까요?

링크드 리스트를 먼저 배우고 해시테이블을 보니 좀 더 쉽게 이해가 됐던거 같습니다.
해시테이블이 작동하는 원리는 생각보다 쉽습니다!
간단하게 설명하면

1. 해시함수에 키를 넣는다.
2. 해시함수는 그 키와 값이 들어가야할 인덱스번호를 준다.
3. 키와 값을 해당 인덱스번호에 저장시킨다.

이렇습니다!

위의 순서와 사진을 함께 본다면 확 와닿을 것 같습니다.

그럼 왜 Hash Table을 사용할까요?

음 만약 일반 배열에 데이터를 저장하고 있는데 원하는 값을 찾으려면 auto k 해야할까요? 배열의 특성상 위치를 알지 못하는 이상 처음부터 순회해야 찾을 수 있을 겁니다.. 만약 운이 나쁘다면 끝까지 가야 찾을 수 있지 않을 까요? 배열이 짧은 배열이라면 별로 상관 없겠지만 만약 데이터의 양이 100만개 혹은 1000만개 그 이상이면 어떨까요? 운이 나쁘다면 1000만번째까지 가서 확인해봐야 할 수 도 있습니다.

이럴때 해시 테이블을 사용한다면 찾고싶은 키를 해시함수에 넣고 나온 번호를 가지고 해당 번호에가서 키를 찾으면 훨씬 빠르게 찾을 수 있을 겁니다! 메모리도 효율적으로 사용할 수 있을꺼구요!

Hash Table 슈도코드

1.Insert
1.1. 빈 객체를 하나 만든다
1.2. 해시함수에 입력 받은 키와 최대길이를 넣고 인덱스를 받아온다.
1.3. 만약 가방[인덱스]가 비었다면
1.4. 빈 객체[key]에 값을 넣고
1.5. 객체를 가방에 넣는다.
1.6. 없으면 가방[key]에 값을 넣는다.
1.7. 사이즈 + 1

2. Retrieve
2.1. 만약 가방[인덱스] 가 비었다면 undefined 반환
2.2. 가방의 인덱스에 키를 반환

3. Remove
3.1. 만약 인덱스에 키가 있다면
3.2. delete로 삭제하기
3.3. 사이즈 - 1

4. Resize
4.1. 현재 가방을 변수에 저장
4.2. 최대 가방크기를 입력받은 가방크기로 바꾸기
4.3. 가방 내용 초기화
4.4. 가방 크기 초기화
4.5. 저장해둔 가방에서 하나씩 꺼내 insert함수로 실행

Hash Table js 코드

class HashTable {
  constructor() {
    this._size = 0;
    this._bucketNum = 8;
    this._storage = LimitedArray(this._bucketNum);
  }

  insert(key, value) {
    let obj = {}
    const index = hashFunction(key, this._bucketNum);
    if(this._storage.get(index) === undefined){
      obj[key] = value
      this._storage.set(index, obj)
    }
    else{
      obj = this._storage.get(index)
      obj[key] = value
      this._storage.set(index, obj)
    }
    this._size++
    if(this._size > (this._bucketNum * 0.75)){
    this._resize(this._bucketNum * 2)
    }
  }
  

  retrieve(key) {  /// 현재 한 객체에 다 모여 있는 형태임 ex : {key: value, key: value, key: value, key: value .....}
    const index = hashFunction(key, this._bucketNum);
      if(this._storage.get(index) === undefined){
        return undefined;
      }
      return this._storage.get(index)[key]
  }
  

  remove(key) {
    const index = hashFunction(key, this._bucketNum);
    if(this._storage.get(index)[key]){
      delete this._storage.get(index)[key]
      this._size--
      if(this._size < (this._bucketNum * 0.25)){
        this._resize(this._bucketNum / 2)
        }
    }
    }
 
  _resize(newBucketNum) {
    let oldstorage = this._storage
    this._bucketNum = newBucketNum
    this._storage = LimitedArray(newBucketNum);
    this._size = 0;

    oldstorage.each(obj => {
      for(let key in obj){
        this.insert(key, obj[key])
      }
    })
  return this._storage
  }
}