해시테이블 (Hash Table)

해시테이블이란?

• 프로그래밍 언어에 따라서 조금씩 다른 이름을 가지고 있음
  해시(Hash), 맵(Map), 해시맵(HashMap), 딕셔너리(Dictionary)
• 해시 함수로 테이블의 인덱스를 새로 만들기 때문에 해시테이블이라는 이름이 붙음. 

해시테이블의 장단점

장점

1. 빠른 검색 속도: 평균적으로 O(1)의 시간 복잡도로 데이터를 검색할 수 있 음.
2. 빠른 삽입 및 삭제: 평균적으로 O(1)의 시간 복잡도로 데이터를 삽입하거나 삭제할 수 있 음.
3. 유연성: 다양한 종류의 데이터를 효율적으로 저장하고 검색할 수 있음.

단점

1. 충돌 문제: 두 개 이상의 키가 동일한 해시값을 가질 때 충돌이 발생. 이를 해결하기 위해 추가적인 메모리와 시간이 필요.
2. 메모리 사용량: 해시테이블은 효율적인 성능을 위해 종종 실제 데이터보다 큰 메모리 공간을 요구.
3. 해시 함수의 선택: 좋은 해시 함수를 선택하지 않으면 성능이 저하될 수 있음.

요약

• 좋은 해시 함수가 필요함
• 검색속도, 삽입, 삭제는 빠름
• 두 개 이상의 키가 동일한 해시값을 가질때 충돌 발생.

해시 테이블의 주요 연산

• 데이터 삽입
• 데이터 읽기
• 데이터 제거

자바스크립트에서는 객체(Object)와 Map을 사용하여 해시테이블을 구현할 수 있다.

 

자바스크립트 예시

class HashTable {
    constructor(size = 53) {
        this.keyMap = new Array(size);
    }

    // 해시 함수
    _hash(key) {
        let total = 0;
        let WEIRD_PRIME = 31;
        for (let i = 0; i < Math.min(key.length, 100); i++) {
            let char = key[i];
            let value = char.charCodeAt(0) - 96;
            total = (total * WEIRD_PRIME + value) % this.keyMap.length;
        }
        return total;
    }

    // 키-값 쌍을 추가합니다.
    set(key, value) {
        let index = this._hash(key);
        if (!this.keyMap[index]) {
            this.keyMap[index] = [];
        }
        this.keyMap[index].push([key, value]);
    }

    // 키를 이용해 값을 가져옵니다.
    get(key) {
        let index = this._hash(key);
        if (this.keyMap[index]) {
            for (let i = 0; i < this.keyMap[index].length; i++) {
                if (this.keyMap[index][i][0] === key) {
                    return this.keyMap[index][i][1];
                }
            }
        }
        return undefined;
    }

    // 모든 키를 가져옵니다.
    keys() {
        let keysArr = [];
        for (let i = 0; i < this.keyMap.length; i++) {
            if (this.keyMap[i]) {
                for (let j = 0; j < this.keyMap[i].length; j++) {
                    if (!keysArr.includes(this.keyMap[i][j][0])) {
                        keysArr.push(this.keyMap[i][j][0]);
                    }
                }
            }
        }
        return keysArr;
    }

    // 모든 값을 가져옵니다.
    values() {
        let valuesArr = [];
        for (let i = 0; i < this.keyMap.length; i++) {
            if (this.keyMap[i]) {
                for (let j = 0; j < this.keyMap[i].length; j++) {
                    if (!valuesArr.includes(this.keyMap[i][j][1])) {
                        valuesArr.push(this.keyMap[i][j][1]);
                    }
                }
            }
        }
        return valuesArr;
    }
}

// 해시테이블 사용 예시
let ht = new HashTable();
ht.set("hello", "world");


// 객체 활용하기
class HashTable {
    constructor() {
        this.table = {};
    }

    // 키-값 쌍을 추가합니다.
    set(key, value) {
        this.table[key] = value;
    }

    // 키를 이용해 값을 가져옵니다.
    get(key) {
        return this.table.hasOwnProperty(key) ? this.table[key] : undefined;
    }

    // 키를 이용해 값을 제거합니다.
    remove(key) {
        if (this.table.hasOwnProperty(key)) {
            delete this.table[key];
            return true;
        }
        return false;
    }

    // 모든 키를 가져옵니다.
    keys() {
        return Object.keys(this.table);
    }

    // 모든 값을 가져옵니다.
    values() {
        return Object.values(this.table);
    }

    // 해시 테이블이 비어있는지 확인합니다.
    isEmpty() {
        return Object.keys(this.table).length === 0;
    }

    // 해시 테이블의 크기를 반환합니다.
    size() {
        return Object.keys(this.table).length;
    }

    // 해시 테이블을 비웁니다.
    clear() {
        this.table = {};
    }
}

// Map 활용
class HashTable {
    constructor() {
        this.table = new Map();
    }

    // 키-값 쌍을 추가합니다.
    set(key, value) {
        this.table.set(key, value);
    }

    // 키를 이용해 값을 가져옵니다.
    get(key) {
        return this.table.get(key);
    }

    // 키를 이용해 값을 제거합니다.
    remove(key) {
        return this.table.delete(key);
    }

    // 모든 키를 가져옵니다.
    keys() {
        return Array.from(this.table.keys());
    }

    // 모든 값을 가져옵니다.
    values() {
        return Array.from(this.table.values());
    }

    // 해시 테이블이 비어있는지 확인합니다.
    isEmpty() {
        return this.table.size === 0;
    }

    // 해시 테이블의 크기를 반환합니다.
    size() {
        return this.table.size;
    }

    // 해시 테이블을 비웁니다.
    clear() {
        this.table.clear();
    }
}