[Javascript] 자료구조 - Hash Table

 

 

 

1. 해시 테이블(Hash Table)이란?

해시 테이블은 key와 value의 쌍으로 데이터를 저장하는 자료구조이다. 해시 테이블은 보통 배열을 기반으로 하며, 각각의 키에 대해 고유한 해시 함수를 사용하여 인덱스로 변환한 후 해당 인덱스에 값을 저장해서 빠른 데이터 검색 및 삽입을 가능하게 한다.

해시 테이블은 해시 함수를 사용하여 키를 인덱스로 변환하므로 데이터를 빠르게 검색하고 삽입할 수 있는데 해시 함수의 시간 복잡도가 O(1)에 가까울 경우에 검색 및 삽입 연산의 평균 시간 복잡도도 O(1)에 가깝다.
해시 테이블의 각 키는 해시 함수를 통해 고유한 인덱스로 변환된다. 이로 인해 중복된 키가 발생할 수 없으며, 각 키는 하나의 값과 연결된다. 가끔 해시 테이블의 문제로 해시 충돌이라는 상황이 발생한다. 해시 충돌은 서로 다른 키들이 동일한 해시값을 가질 수 있으며, 이를 해시 충돌이라고 한다. 해시 충돌을 해결하기 위해 다양한 방법이 사용되는데 주요한 방법으로는 개방 주소법(Open Addressing)과 체이닝(Chaining)이 있다.

 

2. 해시 테이블이 사용되는 사례

해시 테이블은 다양한 영역에서 활용되며, 주로 데이터베이스 인덱싱, 캐싱, 언어 번역, 파일 검색 및 인덱싱, 네트워크 라우팅 테이블, 그리고 다양한 자료구조의 구현에 사용된다. 데이터베이스에서는 해시 테이블을 사용하여 데이터의 레코드 위치를 빠르게 찾기 위한 인덱싱에 활용되며, 캐시에서는 자주 액세스되는 데이터를 메모리에 저장하여 성능을 향상시키는 데 활용된다.

언어 번역 서비스에서는 해시 테이블을 사용하여 단어나 문장을 해당 언어의 번역으로 빠르게 변환하고, 파일 시스템에서는 파일 검색을 위해 파일 이름이나 경로를 해시 테이블에 저장하여 빠르게 수행된다. 네트워크에서는 라우터가 패킷을 전송하기 위한 최적의 경로를 결정하기 위해 해시 테이블을 사용하며, 자료구조에서는 해시 맵이나 집합과 같은 추상 자료형을 구현하는 데 사용된다. 

 

3. Javascript로 구현한 해시 테이블

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

    _hash(key) {
        let total = 0;
        const 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 * prime + value) % this.keyMap.length;
        }
        return total;
    }

    set(key, value) {
        const index = this._hash(key);
        if (!this.keyMap[index]) {
            this.keyMap[index] = [];
        }
        this.keyMap[index].push([key, value]);
    }

    get(key) {
        const 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() {
        const 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() {
        const 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;
    }
}

// 사용 예시
const ht = new HashTable();
ht.set("hello", "world");
ht.set("apple", "banana");
console.log(ht.get("hello")); // Output: world
console.log(ht.keys()); // Output: ['hello', 'apple']
console.log(ht.values()); // Output: ['world', 'banana']

 

 

4. Python으로 구현한 해시 테이블

class HashTable:
    def __init__(self, size=53):
        self.size = size
        self.key_map = [None] * self.size

    def _hash(self, key):
        total = 0
        prime = 31
        for char in key[:100]:
            total = (total * prime + ord(char) - 96) % self.size
        return total

    def set(self, key, value):
        index = self._hash(key)
        if not self.key_map[index]:
            self.key_map[index] = []
        self.key_map[index].append((key, value))

    def get(self, key):
        index = self._hash(key)
        if self.key_map[index]:
            for k, v in self.key_map[index]:
                if k == key:
                    return v
        return None

    def keys(self):
        keys_arr = []
        for item in self.key_map:
            if item:
                for k, v in item:
                    keys_arr.append(k)
        return keys_arr

    def values(self):
        values_arr = []
        for item in self.key_map:
            if item:
                for k, v in item:
                    values_arr.append(v)
        return values_arr

# 사용 예시
ht = HashTable()
ht.set("hello", "world")
ht.set("apple", "banana")
print(ht.get("hello"))  # Output: world
print(ht.keys())  # Output: ['hello', 'apple']
print(ht.values())  # Output: ['world', 'banana']