6. 해시 테이블(HashTable)

해시 테이블이란?

해시 함수를 사용하여 인덱스를 만들어 테이블을 만드는 자료 구조

분류해주는 해시 함수가 중요함

빠른 데이터 읽기, 삽입, 삭제가 가능하다.

메모리를 많이 차지한다.

해시테이블의 구현

양방향 연결 리스트를 활용하여 해시 테이블을 만들 수 있다.

import { DoublyLinkedList } from './DoublyLinkedList.mjs';

class HashData {
    constructor(key, value) {
        this.key = key;
        this.value = value;
    }
}
// 해시함수의 결과 값이 중복 일 수 있으니 양방향 연결 리스트를 사용한다.
class HashTable {//양방향 연결 리스트인 10개의 배열을 만들어 준다.
    constructor() {
        this.arr = [];
        for (let i = 0; i < 10; i++) {
            this.arr[i] = new DoublyLinkedList();
        }
    }
    hashFunction(number) { // index를 위한 해시 함수를 만들어 준다.
        return number % 10;
    }
    set(key, value) {
        this.arr[this.hashFunction(key)].insertAt(0, new HashData(key, value));
    }
    get(key) {
        let currentNode = this.arr[this.hashFunction(key)].head;
        while (currentNode != null) {
            if (currentNode.data.key == key) {
                return currentNode.data.value;
            }
            currentNode = currentNode.next;
        }
        return null;
    }
    remove(key) {
        let list = this.arr[this.hashFunction(key)];
        let currentNode = list.head;
        let deletedIndex = 0;
        while (currentNode != null) {
            if (currentNode.data.key == key) {
                return list.deleteAt(deletedIndex);
            }
            currentNode = currentNode.next;
            deletedIndex++;
        }
        return null;
    }
}

export { HashTable };

아래와 같이 테스트 할 수 있다.

import { HashTable } from './HashTable.mjs';

let hashTabla = new HashTable();

hashTabla.set(1, '이운재');
hashTabla.set(4, '최진철');
hashTabla.set(20, '홍명보');
hashTabla.set(6, '유상철');
hashTabla.set(22, '송종국');
hashTabla.set(21, '박지성');
hashTabla.set(5, '김남일');
hashTabla.set(10, '이영표');
hashTabla.set(8, '최태욱');
hashTabla.set(9, '설기현');
hashTabla.set(14, '이천수');

console.log(`1: ${hashTabla.get(1)}`);
hashTabla.remove(1);
console.log(`1: ${hashTabla.get(1)}`);
console.log(`21: ${hashTabla.get(21)}`);

λ node test_HashTable.mjs 
1: 이운재
1: null
21: 박지성