[JS] Linear Probing 방식의 Hash Table 구현

class LinearProbingHashTable {
    constructor(size) {
        this.size = size;
        this.table = new Array(size);
    }

    LinearHashTable(key) {
        let temp = 0;
        for (let i = 0; i < key.length; i++) {
            temp += key.charCodeAt(i);
        }
        return temp % this.size;
    }

    put(key, value) {
        const index = this.LinearHashTable(key);

        if (!this.table[index]) this.table[index] = [{ key, value }];
        else {
            let i = index;
            while (this.table[i] !== undefined) {
                if (this.table[i][0].key === key) {
                    this.table[i][0].value = value;
                    return;
                }
                i = (i + 1) % this.size;
            }
            this.table[i] = [{ key, value }];
        }
    }

    get(key) {
        const index = this.LinearHashTable(key);

        if (!this.table[index]) return undefined;

        let i = index;
        while (this.table[i] !== undefined) {
            if (this.table[i][0].key === key) return this.table[i][0].value;

            i = (i + 1) % this.size;
        }

        return undefined;
    }
}

const linearProbingHashTable = new LinearProbingHashTable(10);

linearProbingHashTable.put('강호동', '010-1111-1111');
linearProbingHashTable.put('유재석', '010-2222-2222');
linearProbingHashTable.put('이수근', '010-3333-3333');
linearProbingHashTable.put('서장훈', '010-4444-4444');

console.log(linearProbingHashTable.get('강호동'));
console.log(linearProbingHashTable.get('유재석'));
console.log(linearProbingHashTable.get('이수근'));
console.log(linearProbingHashTable.get('서장훈'));

Linear Probing 방식의 Hash Table 은 기존의 Hash Table 에서 해시 충돌이 발생할 경우에 사용되는 개선안이다.

 

예를들어 Hash Table 클래스에 존재하는 hash 메서드가 서로 다른 입력에 대해 동일한 index 값을 반환하는 경우 Hash Collision 이 발생한다.

 

이를 해결하는 두 가지 방법 중, Open Addressing 방식의 선형 탐색을 만족하는 Hash Table이 있다.

 

( 나머지 하나는 Separate Chaning 방식으로, Hash Collision 시 충돌이 일어나는 entry를 연결 리스트로 연결한다. )

        if (!this.table[index]) this.table[index] = [{ key, value }];
        else {
            let i = index;
            while (this.table[i] !== undefined) {
                if (this.table[i][0].key === key) {
                    this.table[i][0].value = value;
                    return;
                }
                i = (i + 1) % this.size;
            }
            this.table[i] = [{ key, value }];
        }

해당 if-else 구문에서 else문이 Linear Probing 방식의 주요 예외처리 로직이다.

 

이를 통해 일차함수의 보폭으로 충돌이 발생한 메모리 버킷의 index 값의 다음 위치를 검색 및 할당하여 Hash Collision 을 방지한다.

 

해당 방법은 특정 영역에서 키가 물리면 탐색 횟수가 늘어나 성능이 떨어진다는 단점이 있다.

 

추가적인 방식으로는 이차원 탐색(Quadratic Probling)과 더블 해싱(Double Hashing)이 존재한다.