하루5분코딩"Hash Table"

## Hash Table : 키, 값 쌍을 저장하고 있는 자료구조

• 값이 들어오면 hash function 을 거쳐 storage에 있는 bucket 에 객체와 비슷한 형태로 key 와 value(tuples) 로 저장이 된다. 그래서 key 를 입력 하게 되면 value 가 출력 되는 형태이다.
• hash table 은 미리 storage 의 사이즈를 정해서 값을 받는다. 그렇다면 많은 양이 들어오면 어떻게 해야하는가?
  ✓ storage 에 75% 가 차면 2배로 늘리고 25% 만 차지하면 반으로 나눠준다. 이렇게 메모리를 효율적으로 사용한다.
• 정보를 입력하면 바로 출력되고 빠르기까지 한 hashtable 단점은?
  ✓해쉬 충돌 - 배열과 달리 자료구조가 정렬되어 있지 않다. 즉, 메모리 공간에서 주소에 순차적으로 값을 부여하지 않고, 렌덤하게 값을 부여하게 된다. 그래서 같은 buket 에 여러개의 tuple 이 존재 할수 있다. 이것을 해쉬 충돌이라고 한다.
  

✓ Method

• insert(key, value) - 주어진 키와 값을 저장합니다. 이미 해당 키가 저장되어 있다면 값을 덮어씌웁니다.

• retrieve(key) - 주어진 키에 해당하는 값을 반환합니다. 없다면 undefined를 반환합니다.

• remove(key) - 주어진 키에 해당하는 값을 삭제하고 값을 반환합니다. 없다면 undefined를 반환합니다.

• _resize(newLimit) - 해시 테이블의 스토리지 배열을 newLimit으로 리사이징하는 함수입니다. 리사이징 후 저장되어 있던 값을 전부 다시 해싱을 해주어야 합니다. 구현 후 HashTable 내부에서 사용하시면 됩니다.

✓ 사용

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

 retrieve(key) {
    const index = hashFunction(key, this._limit);
    let buket = this._storage.get(index)
    if(buket===undefined){
      return undefined
    }
    return buket[key]
  }

  remove(key) {
    const index = hashFunction(key, this._limit);
    let buket = this._storage.get(index)
    let result = buket[key]
    delete buket[key]
    this._size--
    if(this._size < this._limit*0.25){
      this._resize(this._limit/2)
    }
    return result;
  }

  _resize(newLimit) {
    let old = this._storage
    this._size = 0
    this._limit = newLimit
    this._storage = LimitedArray(newLimit)
    old.each((buket)=>{
      for(let key in buket){
        this.insert(key , buket[key])
      }
    })
    return this._storage
  }