[DS] 해시 테이블 (Hash Table)

출처 : https://ko.wikipedia.org/wiki/해시_테이블

해시 테이블

해시테이블은 데이터를 빠르게 검색하기 위한 자료구조로, 키(key)와 값(value)의 쌍으로 이루어져 있습니다. 각각의 키는 해시 함수(hash function)를 통해 해시값(hash value)으로 변환되어 배열(buckets)의 인덱스와 연결됩니다. 이렇게 구성된 해시테이블은 O(1) 시간 복잡도로 데이터를 검색하고 삽입할 수 있어서 매우 효율적인 자료구조입니다.

 

해시(Hash)란?

임의의 길이를 가진 데이터를 고정된 길이의 데이터로 변환하는 것을 말합니다. 해시테이블에서는 이러한 해시 함수(hash function)를 사용하여 데이터의 고유한 인덱스를 생성합니다. 해시 함수는 입력값으로 받은 데이터를 해시값으로 변환하여, 이 값을 인덱스로 사용하게 됩니다. 이렇게 해시함수를 사용하여 생성된 인덱스는 데이터를 검색하는 데 매우 효율적이며, 해시테이블의 핵심적인 역할을 담당합니다.

 

해시 충돌(Hash Collision) 문제

• 해시 충돌(Hash Collision)은 서로 다른 키(key) 값들이 해시 함수(hash function)를 거쳐 동일한 해시값(hash value)을 가지는 경우를 말합니다. 해시테이블에서는 해시값을 배열의 인덱스로 사용하므로, 해시 충돌이 발생하면 해당 인덱스에 이미 다른 데이터가 존재하는 경우 충돌이 발생합니다.
• 해시 충돌은 해시 함수의 성능이나 테이블 크기 등에 따라 발생 빈도가 달라집니다. 따라서 충돌을 최소화하기 위해 충분한 크기의 테이블을 사용하거나, 해시 함수를 잘 선택하여 충돌을 최소화해야 합니다. 또한 충돌이 발생했을 때 충돌을 해결하는 방법에 대한 알고리즘도 필요합니다. 대표적인 충돌 해결 알고리즘으로는 Separate Chaining, Open Addressing 등이 있습니다.
  
  

Separate Chaining

• Separate Chaining은 충돌이 발생하면 해당 인덱스에 연결리스트(linked list)를 생성하여 충돌한 모든 데이터를 연결리스트에 추가하는 방식입니다. 이렇게 하면 같은 인덱스에 다른 값들을 연결리스트로 구분하여 저장할 수 있기 때문에, 충돌이 발생해도 데이터를 효율적으로 저장할 수 있습니다.

• 장점 : 구현이 비교적 간단하며, 저장할 데이터의 크기가 동일하지 않거나 삭제가 빈번하지 않는 경우 유용합니다.
• 단점 : 연결 리스트의 길이가 길어질수록 검색 속도는 점차 느려지게됩니다. 따라서 충돌이 발생할 가능성이 높은 데이터를 저장해야 하는 경우에는 다른 해시 충돌 해결 알고리즘을 사용하는 것이 더 좋을 수 있습니다.
  
  

Open Addressing

• Open Addressing은 충돌이 발생했을 때 다른 빈 인덱스를 찾아서 데이터를 저장하는 방식입니다.
• 대표적인 Open Addressing 기법으로는 선형 탐사(Linear Probing), 이차원 탐사(Quadratic Probing), 이중 해싱(Double Hashing) 등이 있습니다.
• 선형 탐사는 충돌이 발생하면 다음 인덱스를 순차적으로 탐색하고, 이차원 탐사는 제곱수를 이용해 다음 인덱스를 탐색합니다. 이중 해싱은 해시 함수를 하나 더 사용하여 충돌이 발생하면 두 번째 해시 함수를 사용하여 다른 인덱스를 찾아냅니다.

• 장점 : 해시 테이블 내의 다른 빈 인덱스를 찾아 데이터를 저장하기 때문에, 데이터를 저장하는 공간을 연결 리스트로 생성하지 않아도 되어 메모리를 더 효율적으로 사용할 수 있습니다. 또한 연결 리스트를 사용하지 않기 때문에, 저장된 데이터의 검색 속도가 상대적으로 더 빠릅니다.
• 단점 : Open Addressing은 해시 충돌이 발생하면 빈 슬롯을 찾을 때까지 다른 슬롯을 순회해야 하므로 검색 속도가 느려집니다.
  
  

해시 테이블 구현 (Python)

• 해시테이블 클래스 HashTable은 리스트를 이용하여 각 버킷(bucket)을 구현합니다.
• 해시 함수로는 파이썬 내장 hash() 함수를 이용하였으며, 충돌이 발생할 경우 체이닝 방식을 이용하여 충돌을 해결합니다.
• insert() 메서드는 새로운 키-값 쌍을 해시테이블에 추가합니다.
• search() 메서드는 주어진 키에 대응하는 값을 반환합니다.
• delete() 메서드는 주어진 키에 대응하는 키-값 쌍을 삭제합니다.

※ 하지만, 이 코드는 매우 간단한 구현이므로 일부 상황에서는 충돌이 발생하면 제대로 작동하지 않을 수 있습니다. 따라서 가능하다면 파이썬 내장 딕셔너리를 사용하는 것이 더욱 간편하고 안정적입니다.

class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [[] for _ in range(self.size)]

    def _hash_function(self, key):
        return hash(key) % self.size

    def insert(self, key, value):
        index = self._hash_function(key)
        for i, kv in enumerate(self.table[index]):
            k, v = kv
            if k == key:
                self.table[index][i] = (key, value)
                break
        else:
            self.table[index].append((key, value))

    def search(self, key):
        index = self._hash_function(key)
        for k, v in self.table[index]:
            if k == key:
                return v
        raise KeyError(key)

    def delete(self, key):
        index = self._hash_function(key)
        for i, kv in enumerate(self.table[index]):
            k, v = kv
            if k == key:
                del self.table[index][i]
                return
        raise KeyError(key)
    
#Test Code
h_table = HashTable(8)
h_table.insert('a', '1111')
h_table.insert('b', '3333')
h_table.insert('c', '5555')
h_table.insert('d', '8888')
print(h_table.table)
print(h_table.search('d'))

h_table.delete('d')

print(h_table.table)