자료구조 - HashTable

2020-07-25

갑분자;
최근에 코딩테스트를 봤는데 결과보고 충격을 먹어서 공부를 시작했다.
코딩테스트 공부를 자바스크립트로 하면 나중에 코드 짤 때도
구현 능력이 향상되지 않을까 하는 생각으로. 겸사겸사 공부하고 있다.

자바스크립트에서는 Object와 Map을 구현하는 데에 Hash가 사용되었다고 함.
검색, 삽입, 삭제에 소모되는 평균 시간이 O(1)로 매우 빠름.

해시법

데이터를 저장할 위치를 간단한 연산을 통해 구하는 것을 해시법(hashing)
연산을 통해 나온 값을 표에 정리한 것을 해시 값(hash value)이라고 한다.

ex)
키 값을 13으로 나눈 나머지를 해시 값으로 한다.
키 값 : 5 / 6 / 14 / 20 / 29 / 34 / 37 / 51 / 69 / 75
해시 값 : 5 / 6 / 1 / 7 / 3 / 8 / 11 / 12 / 4 / 10

여기서 ‘해시 값 = 키 값 % 13’라는 식,
즉 키 값으로 해시 값을 만드는 과정이 해시 함수(hash function)
보통은 나머지(modulo) 연산이 자주 들어감.

해시 값이 인덱스가 되게끔 키 값을 저장한 배열이 해시 테이블(hash table)
해시 테이블의 각 요소(배열 한 칸)를 버킷(bucket)이라고 함.

해시 함수를 통해 구한 해시 값에 해당하는 버킷에 이미 값이 들어가있으면,
즉 저장될 버킷이 중복되면 충돌(collision)
충돌을 최소화하는 방향으로 해시 함수를 만들어야 함.
(해시 값이 고르게 퍼질 수 있도록)

충돌의 해결책

오픈 주소법(Open Addressing)

빈 버킷을 찾을 때까지 연산을 반복한다.

선형 탐사법(Linear Probing)
순차적으로 탐사하는 방법. 1번 인덱스에 값이 들어있으면 2번에 넣음.
제곱 탐사법(Quadratic Probing)
탐사하는 폭이 제곱으로 늘어남. 처음에 겹치면 1만큼,
두 번째 겹치면 4만큼 건너가서 값을 집어넣음.
해싱 반복
빈 버킷을 찾을 때까지, 해싱 연산을 계속해서 반복한다.
이중 해싱(Double Hashing)
해시 함수를 이중으로 사용하는 방법.
최초 해시를 얻을 때 사용하는 함수를 하나 마련하고,
충돌이 났을 경우 탐사 이동폭을 얻는 함수를 또 하나 마련한다.

체인법

= 분리 연결법, 체이닝(Chaining)
같은 해시 값을 갖는 요소들(키 값들)을 연결 리스트(Linked List)로 관리한다.

연결 리스트뿐 아니라, 트리를 사용한다.
오픈 해시법(Open hashing)이라고도 한다.
각 버킷에는 연결 리스트의 첫 번째 노드에 대한 참조가 저장된다.

데이터가 들어가는 순서의 역순으로 노드 순서가 지정된다.
데이터를 삽입할 때, 맨 마지막 노드로 들어가게 되면
노드를 타고가는 과정에서 시간적인 소모가 발생한다.
따라서, 수행시간을 최대한 줄이기 위해 새로 들어오는 데이터를
맨 앞에다가 집어넣는다.

Resizing

테이블이 꽉 차면 데이터를 저장할 공간이 없을 수도 있고
테이블에 빈 공간이 적어지면서, 충돌이 많이 발생하여
빈 공간을 찾는 시간이 점점 늘어날 수도 있다.
혹은, 체인법을 사용하는 경우 버킷에 저장된 리스트의 길이가
너무 길어져서 리스트 탐색 시간이 너무 길어질 수도 있다.

그래서 테이블의 크기는 어느 정도 비워져 있는 것이 성능 상 좋다.
특별한 알고리즘은 없고, 기존 크기의 두 배정도로 새로운 테이블을 선언하여
기존 테이블의 데이터를 그대로 복사한다.

혹은 Rehashing을 통해 너무 길어진 리스트의 데이터들을 재분배하기도 한다.

Hash Table 자료구조의 단점

순서가 있는 배열에는 어울리지 않음
공간 효율성이 떨어짐
Hash function의 의존도가 높음

간단한 HashTable의 코드 구현

String을 input으로 받는 hash function.
버킷은 linked list가 아닌 배열로 구현함.

var hash = (string, max) => {
    var hash = 0;
    for(var i = 0; i < string.length; i++) {
        hash += string.charCodeAt(i);
    }
    return hash % max;
}

let HashTable = function() {
    let storage = [];
    const storageLimit = 4;
    
    this.print = function() {
        console.log(storage);
    }

    this.add = function(key, value) {
        var index = hash(key, storageLimit);
        if(storage[index] === undefined) {
            storage[index] = [
                [key, value]
            ];
        } else {
            var inserted = false;
            for(var i = 0; i < storage[index].length; i++) {
                if(storage[index][i][0] === key) {
                    storage[index][i][1] = value;
                    inserted = true;
                }
            }
            if(inserted === false) {
                storage[index].push([key, value]);
            }
        }
    };

    this.remove = function(key) {
        var index = hash(key, storageLimit);
        if(storage[index].length === 1 && storage[index][0][0] === key) {
            delete storage[index];
        } else {
            for(var i = 0; i < storage[index]; i++) {
                if(storage[index][i][0] === key) {
                    delete storage[index][i];
                }
            }
        }
    };

    this.lookup = function(key) {
        var index = hash(key, storageLimit);
        if(storage[index] === undefined) {
            return undefined;
        } else {
            for(var i = 0; i < storage[index].length; i++) {
                if(storage[index][i][0] === key) {
                    return storage[index][i][1];
                }
            }
        }
    };
};

let ht = new HashTable();
ht.add('beau', 'person');
ht.add('fido', 'dog');
ht.add('rex', 'dinosaur');
ht.add('tux', 'penguin');
console.log(ht.lookup('tux'));
ht.print();

알고리즘 문제

일단 프로그래머스의 해시 문제만 풀어봐서 다 이런건지는 모르겠지만
일반적으로 알고리즘 문제에서의 해시는
‘key-value’ 쌍을 가진 자료구조 정도를 의미하는 것 같다.
그래서 그냥 가진 객체나 Map만 써도 풀 수 있는 경우가 많더라.

출처 1 : Evan Moon님의 블로그
출처 2 : cyranocoding.log
출처 3 : freeCodeCamp.org 유튜브

 AJAX 자료구조 - Linked List 