해시테이블 (Hash Table) 구현해보기

해시함수

임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수

해시 함수 특성

• 압축성: 다양한 가변 길이의 입력에 대해 고정된 크기의 결과값을 반환하는 성질
• 효율성: 어떤 입력 값에 대해서도 많은 자원과 시간이 소요되지 않고 처리되는 성질
• 저항성: 결과값을 바탕으로 입력 값을 찾는 것이 불가능한 성질

아래와 같이 어떤 길이의 키 값이 들어오더라도 두자리 숫자로 반환되는 것을 확인할 수 있으며, 한 번 변화된 결과값에 대해서는 어떤 입력값을 넣었는지 찾는 것이 어렵다.

해시테이블 (Hash Table)

Hash함수를 사용하여 평균 O(1) 시간 복잡도로 특정 값을 신속하게 찾는 자료구조
array에서 for문을 순회하는 것이 아니라 바로 인덱스에 접근하기 때문에 신속하게 찾을 수 있다.

해시 충돌 해결 방법

만약에 key가 같은 hash값을 가리키고 있다고 하면, 기존에 저장되어 있는 값 때문에 저장이 되지 않거나 해당 값이 이미 저장이 되었다고 판단할 수도 있기 때문에 충돌이 일어날 수 있다.

• 해시 함수 변경: 더 큰 숫자의 공간과 Modular 산술 값을 이용해 충돌 최소화
• 자료구조 확장: Open Addressing Method(선형 조사법, 이중해시), Close Addressing Method(체이닝)

구현 메서드

• 객체 초기화 / 크기 반환: HashTable.clear(), HashTable.size()
• 전체 데이터 반환, 전체 데이터 출력: HashTable.getBuffer(), HashTable.print()
• 데이터 추가 / 삭제 / 반환: HashTable.put(), HashTable.remove(), HashTable.get()

1. element 클래스 선언

hash는 key와 value로 이루어진 객체들을 다루는 자료구조이기 때문에 Element 클래스가 필요하다.

class Element {
    constructor(key, value) {
        this.key = key;
        this.value = value;
    }
}

2. hash table 클래스 선언

미리 정의해 둔 HASH_SIZE를 넣어 새로운 테이블 객체를 만들어준다.

class HashTable {
    constructor() {
        this.table = new Array(HASH_SIZE);
        this.length = 0;
    }
}

3. 해시 함수 생성 (hashCode())

가장 중요한 함수 중 하나인 hashCode, 즉 해시코드를 만드는 함수이다.
각자의 글자의 char코드를 더해서 전체 hash의 사이즈로 나눈 나머지로 만든다.

hashCode(key) {
        let hash = 0;
        for (let i = 0; i < key.length; ++i) {
            hash += key.charCodeAt(i);
        }
        return hash % HASH_SIZE;
    }

4. 데이터 추가 (put(key, value))

hashcode를 생성한 이후, 그 위치가 undefined일 경우에만 데이터를 추가해 준다.

put(key, value) {
        let index = this.hashCode(key);
        
        if (this.table[index] !== undefined) {
            return false;
        }

        this.table[index] = new Element(key, value);
        this.length++;
    }

5. 데이터 조회 (get(key))

간단하게 바로 index로 접근해서 데이터를 가져온다.

get(key) {
        return this.table[this.hashCode(key)];
    }

6. 데이터 삭제 (remove(key))

데이터가 undefined는 아닌지 확인한 이후, 해당 데이터를 삭제하고, 미리 저장한 데이터를 return 값으로 돌려준다.

remove(key) {
        let element = this.table[this.hashCode(key)];
        
        if (element !== undefined) {
            delete this.table[this.hashCode(key)];
            this.length--;
        }

        return element;
    }

7. 테이블 초기화 (clear())

테이블을 기존의 HASH_SIZE로 초기화 시켜주고, 길이 또한 0으로 바꿔준다.

clear() {
        this.table = new Array(HASH_SIZE);
        this.length = 0;
    }

8. 크기 반환 (size())

size() {
        return this.length;
    }

9. 데이터 셋 반환 (getBuffer())

테이블의 길이만큼 탐색한 후 table에 데이터가 존재한다면, array에 저장한 후 return 한다.

getBuffer() {
        let array = [];
        for (let i = 0; i < this.table.length; i++) {
            if (this.table[i]) {
                array.push(this.table[i]);
            }
        }
        return array;
    }

10. 데이터 셋 출력 (print())

있는 테이블의 데이터 개수 만큼 print한다.

print() {
        for (let i = 0; i < this.table.length; i++) {
            if (this.table[i]) {
                console.log(`${i} -> ${this.table[i].key} : ${this.table[i].value}`);
            }
        }
    }

여기서 가장 문제점은 HASH_TABLE의 수가 적으면 hash값이 겹칠 수 있고, 이는 데이터가 삭제되거나 중복되는 일이 발생할 수 있다는 것이다. 이것을 loselose hash size**라고 한다.

⇒ 그래서 선형조사법 해시테이블이나, 체이닝 해시테이블을 사용한다.

하지만 해시 함수를 변경해서 찾아내는 방법도 존재한다.

djb2 hash function

조금이나마 덜 겹치도록 만드는 방법

1. HASH_SIZE를 변경한다. (겹치기 힘든 소수 값으로 변경하는 것)
2. hash 함수 내부의 seed 값을 소수로 변경한다.
3. 각 key의 char값을 더해줄 때 hash 값에 소수를 곱한 값을 더해준다.

// djb2 hash size
const HASH_SIZE = 1013;

hashCode(key) {
        let hash = 5381; //seed, 모두 값이 소수로 되어있음
        for (let i = 0; i < key.length; i++) {
            hash = hash * 33 + key.charCodeAt(i);
        }
        return hash % HASH_SIZE;
    }

관련 전체 코드는 Git에 업로드 해두었습니다.
Github_hashTable