[Udemy] 해쉬 테이블(Hash Table)이란 ?

정의

해쉬 테이블은 모든 언어에서 사용하는 자료구조로, 해쉬 테이블은 key, value로 구성된 자료구조이다.

자바스크립트에서 객체가 해쉬 테이블이다.

 

해쉬 테이블을 구현하는 방법은 수많은 방법이 있고 각 방법 마다 효율성이 달라지기 때문에

여기선 어떻게 구현하는지 정도만 이해하고 실제로 해쉬 테이블을 사용할 때는 객체를 사용하는 것을 추천한다.

 

 

코드 및 구현

1. Hash 함수 구현

해쉬 테이블을 구현하기 위해선 key 값을 입력했을 때, 해당 key 값에 해당하는 특정한 값을 반환하는 함수인

Hash 함수를 구현해야 한다.

예를 들어, 특정 값인 0을 반환하면 [[key, value], ... ] 이런식으로 배열에 특정 값(인덱스)에 key, value를 가진 배열을 가진다.

function firstHash(key, arrLen) {
    let total = 0;
    for (let char of key) {
        let value = char.charCodeAt(0) - 96;
        total = (total + value) % arrLen;
    }
    return total;
}

 

charCodeAt 메서드는 string 값에 해당하는 숫자를 반환하는 메서드이다.

또한, arrLen값은 hash 함수가 위치할 수 있는 인덱스 범위를 지정해준다.

arrLen이 100이면, hash 함수는 0~99 사이의 값을 반환해준다.

 

하지만 위 함수는 string 값만 사용해야 하며, 시간 복잡도가 상수가 아니고, 동일한 해쉬 값이 중복될 수 있다.

이를 개선해보자.

 

 

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;
    }
}

 

해쉬 테이블의 성능을 높이기 위해 글자 길이가 어느 정도 지점까지 반복문을 순회하도록 지점을 정해두었다.

WEIRD_PRIME이라는 소수값을 곱해줘서 최대한 중복이 없는 해쉬값을 반환하도록 설정해주었다.

배열 길이의 나머지 값을 할당하는 이유는 해쉬 값의 범위가 배열 길이 넘지 않도록 하기 위함이다.

 

 

2. set 메서드 구현

set 메서드는 key, value를 전달하여 해쉬 값을 통해 배열에 저장한다.

set(key, value) {
        let index  = this._hash(key);
        if (!this.keyMap[index]) {
            this.keyMap[index] = []
        }
        let duplicatedKeyIdx = this.keyMap[index].findIndex(obj => obj[0] === key)
        if (duplicatedKeyIdx > -1) {
            this.keyMap[index][duplicatedKeyIdx] = [key, value]
        } else {
            this.keyMap[index].push([key, value])    
        }
    }

 

해쉬함수를 통해 구한 index 값에 해당하는 값이 없으면 빈 배열을 추가한다.

만약에 해당 인덱스에 위치한 배열 요소 중 동일한 키값이 존재하면 덮어씌워주고

그렇지 않으면 [key ,value] 배열을 추가한다.

 

 

3. get 메서드 구현

get 메서드는 해쉬 값 index에 해당하는 [key, value]를 조회하는 메서드이다.

get(key) {
        let index = this._hash(key);
        let keyValues= this.keyMap[index]

        if (Array.isArray(keyValues)) {
            let [k,v] = keyValues.find((value) => value[0] === key);
            return [k,v]
        }
        return;
    }

 

만약 해쉬 테이블에 중복된 index가 존재하여 다수의 배열 요소로 이뤄져있다면,

다수의 배열 요소 중 key 값이 동일한 값을 찾아서 반환한다.

 

 

4. keys, values 메서드 구현

keys 메서드는 모든 유일한 key 값들을 반환하고,

values 메서드는 모든 value 값들을 반환한다.

// Object.keys()는 애초에 객체가 중복된 key를 가지고 있을 수 없기에 유일한 key들만 반환한다.
keys() {
        let keysArr = [];
        for (let i = 0; i < this.keyMap.length; i++){
            if (this.keyMap[i]) {
                for (let obj of this.keyMap[i]) {
                    if (keysArr.includes(obj[0])) continue;
                    keysArr.push(obj[0])
                }
            }
        }
        return keysArr;
    }

    // Object.values()는 중복된 값도 모두 반환한다.
    values() {
        let valuesArr = [];
        for (let i = 0; i < this.keyMap.length; i++){
            if (this.keyMap[i]) {
                for (let obj of this.keyMap[i]) {
                    valuesArr.push(obj[1])
                }
            }
        }
        return valuesArr;
    }

 

Object.keys() 메서드와 유사하게 유일한 key 값들만 반환하도록

keysArr에 포함되어 있는지 확인하는 로직을 추가했다.

values 메서드의 경우, 중복되는 값이더라도 모든 값을 반환하여야 하기 때문에

중복을 확인하는 로직을 제거했다.

 

 

시간 복잡도

삽입 - O(1)

제거 - O(1)

접근 - O(1)

 

해쉬 테이블은 자료의 삽입, 제거, 접근 모두 용이한 자료구조이다.

다만, 앞서 말했듯이 지금 구현한 해쉬 테이블은 해쉬 테이블이 어떤 구조로 동작하는지

이해를 하기 위해 만들어본 아주 기초적인 예시이므로

직접 해쉬 테이블을 사용해야 할 경우에는 자바스크립트의 객체를 적극 사용하자.

 

 

참조

Udemy - Js 알고리즘 & 자료구조 강의