[자료구조와 알고리즘] Hash Table 구현해보기

이미지 출처: https://en.wikipedia.org/wiki/Hash_table

Hash Table을 구현하는 방법 (해시 충돌시 해결 방법)
1) Open Addressing (비어 있는 공간을 찾아서 데이터 삽입) :
Linear Probing 선형 탐색 | Quadratic Probing 이차원 탐색 | Double Hashing 더블 해싱
2) Separate Chaining (해시 값을 통해 찾은 공간에 링크드 리스트처럼 데이터를 연결)

중에 Open Addressing의 선형 탐색 방법으로 구현해보겠습니다.

class HashTable {
    constructor() {
      	// 해시 테이블에 저장된 데이터의 양
        this.size = 0;
      	// 127의 길이를 갖는 해시 테이블의 저장 공간을 생성
        this.table = new Array(127);
    }

  	// 해시 함수는 key의 각 글자 하나의 아스키 코드를 더해서 
  	// 해시 테이블의 사이즈보다 작은 값으로 계산합니다.
    _hash(key) {
        let hash = 0;
        for (let i=0; i<key.length; i++) {
            hash += key.charCodeAt(i);
        }
        return hash % this.table.length;
    }

    set(key, value) {
        let index = this._hash(key);
      	// 해시 함수를 통해 계산한 해시 값이 없을 경우
        if (!this.table[index] || this.table[index].length !== 0) {
            this.table[index] = value;
        // 이미 존재하는 해시 값인 경우 
        } else {
            let i = 1;
            while (true) {
              	// 선형 탐색을 통해서 빈 저장 공간을 찾지 못했을 경우 에러 반환
                if (i > this.table.length) {
                    return new Error('Fail to set this value');
                }
              	// i를 하나씩 증가시켜서 선형 탐색을 통해 빈 저장 공간에 저장
                index = (index + i++) % this.table.length;
                if (!this.table[index] || this.table[index].length !== 0) {
                    this.table[index] = value;
                    break;
                }
            }
        }
        this.size++;
    }

    get(key) {
      	// 해시 값으로 데이터를 조회
        const index = this._hash(key);
        return this.table[index];
    }
}

이렇게 구현한 Hash Table 클래스를 객체로 생성해서 테스트해보겠습니다.

const hashTable = new HashTable();
hashTable.set('abc', 'val1')
hashTable.set('abd', 'val2')

console.log(hashTable)
console.log(hashTable.get('abc'))
/**
HashTable {
  size: 2,
  table: [ <40 empty items>, 'val1', 'val2', <85 empty items> ]
}
val1
**/