Hash Table

대부분의 언어에서 이미 내장 함수를 가지지만 여기서는 직접 해시 테이블을 함수를 만들어 구현한다.!

해시 테이블 특징

• JS에서는 Obj, Map을 가진다.

• 해시 테이블은 키-값 쌍을 저장하는데 사용된다.

• 해시 테이블의 키는 순서를 가지지 않는다.

• 값을 찾거나, 새로운 값을 추가하거나, 값을 제거하는데 아주 빠르다.

  좋은 해시 테이블이란?

• 속도가 빠르다

• 일관된 방식으로 분배를 해서 다른 것들과 겹치지 않게 해야 한다.

• 특정 입력값을 입력할 때마다 같은 출력값이 나와야 한다.

충돌 처리

개별 체이닝(Separate Chaining)

• 같은 장소에 여러 데이터를 저장할때 배열이나 연결 리스트 등과 같은 것을 활용하여 이중 데이터 구조를 쓰는것
• 테이블의 길이보다 더 많은 데이터를 저장할 수 있다.
  

직진 탐색법(Linear Probing)

충돌이 발생하면 다음 빈칸이 어디인지 확인하고 빈칸에 저장한다, 이렇게 하면 데이터가 같은 인덱스에 저장되는 것을 막을 수 있다.

해시 테이블 구현 (키값은 스트링만 사용)

배열의 길이가 소수 일경우 소수가 아닐때보다 충돌 횟수가 줄어든다.

class HashTable { 
   constructor(size=53){
       this.keyMap = new Array(size)
   }
   _hash(key){
       let total = 0
       let WEIRD_PRIME = 31
       for(let i =0; i<Math.min(key.length,100); i++){
           let char = key[i]
           let value = char.charCodeAt(0) - 96
           total = (total * WEIRD_PRIME + value) % this.keyMap.length
       }
       return total
   }
}

Set method 구현

1. key와 value를 받는다.
2. key를 해시한후에 개별 체이닝을 통해 해시 테이블에 저장한다.

set(key,value){
       let hashKey = this._hash(key)
       if(!this.keyMap[hashKey]){
           this.keyMap[hashKey] = []
       }
       this.keyMap[hashKey].push([key,value])
       return this
   }

Get method 구현

1. key를 받는다.
2. key를 해시한후 값을 확인한다.
3. key가 없다면 return undefined

get(key) {
        let hashKey = this._hash(key)
        if(this.keyMap[hashKey]){
            for(let i = 0; i<this.keyMap[hashKey].length; i++){
                if(this.keyMap[hashKey][i][0] === key){
                    return this.keyMap[hashKey][i][1]
                }
            }
        }
        return undefined
    }

Keys method 구현

테이블에 있는 모든 키를 포함한 목록을 출력한다.

 keys(){
        let keysArr = []
        for(let i = 0; i< this.keyMap.length; i++){
            if(this.keyMap[i]){
                for(let j = 0; j<this.keyMap[i].length; j++){
                    if(!keysArr.includes(this.keyMap[i][j][0])){
                        keysArr.push(this.keyMap[i][j][0])
                    }
                }
            }
        }
        return keysArr
    }

Values method 구현

테이블에 있는 모든 값을 포함한 목록을 출력한다.

values(){
        let valuesArr = []
        for(let i = 0; i< this.keyMap.length; i++){
            if(this.keyMap[i]){
                for(let j = 0; j<this.keyMap[i].length; j++){
                    if(!valuesArr.includes(this.keyMap[i][j][1])){
                        valuesArr.push(this.keyMap[i][j][1])
                    }
                }
            }
        }
        return valuesArr
    }

시간 복잡도

• Insert : O(1)
• Deletion : O(1)
• Access : O(1)