해시 테이블은 매우 유용한 데이터 구조로, 효율적인 데이터 접근과 삽입을 지원합니다. 하지만 때로는 해시 테이블에서 충돌(collisions)이 발생할 수 있습니다. 충돌이란 서로 다른 키(key)에 대해 같은 해시 값(hash value)이 나오는 상황을 말합니다. 이러한 충돌을 감지하고 해결하는 것은 해시 테이블의 성능을 향상시키는 중요한 과제입니다.

충돌 해결 기법

1. 체인법(Chaining)

체인법은 해시 테이블의 각 버킷(bucket)에 연결 리스트(linked list)를 사용하여 충돌을 해결하는 방법입니다. 충돌이 발생하면 해당 버킷에 있는 연결 리스트에 키-값(pair)을 추가합니다. 이렇게 하면 한 버킷에 여러 개의 키-값이 저장될 수 있으며, 충돌이 발생했을 때도 쉽게 검색할 수 있습니다.

2. 개방 주소법(Open Addressing)

개방 주소법은 충돌이 발생했을 때 다른 빈 버킷에 키-값을 저장하는 방법입니다. 대표적인 개방 주소법 방식으로는 선형 탐사(linear probing)와 이차 탐사(quadratic probing), 이중 해싱(double hashing) 등이 있습니다. 이러한 방식들은 충돌이 발생한 위치에서 일정한 간격만큼 이동하여 다른 빈 버킷을 찾는 방법입니다.

해싱 기법

해싱 기법은 효율적인 해시 테이블을 구현하기 위해 사용되는 기법들입니다. 해시 함수(hash function)는 임의의 길이의 데이터를 고정된 크기의 값으로 매핑하는 함수로, 해시 테이블에서 키를 해시 값으로 변환하는 역할을 합니다.

1. 분할 해싱(Division Hashing)

분할 해싱은 키를 해시 테이블의 크기로 나눈 나머지를 해시 값으로 사용하는 가장 간단한 방법입니다. 이 방법은 해시 테이블의 크기가 소수(prime number)일 때 효과적입니다.

2. 접기 해싱(Folding Hashing)

접기 해싱은 키를 일정한 길이로 나누고 나눈 부분들을 합쳐서 해시 값을 만드는 방법입니다. 예를 들어, 12345678이라는 키를 3자리씩 나누면 12, 34, 56, 78이 되고 이를 합치면 해시 값인 1234가 됩니다.

3. 폴리 해싱(Polynomial Hashing)

폴리 해싱은 키의 각 문자를 계수로 삼아 다항식을 만들고 이를 해싱하여 해시 값을 구하는 방법입니다. 예를 들어, ‘abcd’라는 문자열을 다항식으로 표현하면 a * x^3 + b * x^2 + c * x + d가 되고, 이를 해싱해 해시 값을 구합니다.

Python에서 해시 테이블을 사용하는 경우 충돌 해결과 해싱 기법을 효율적으로 적용하여 성능을 개선할 수 있습니다. 이러한 기법들을 적절히 선택하고 구현하는 것은 중요한 과제입니다.

# Chaining 예시

class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.next = None

class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [None] * size
    
    def hash_function(self, key):
        return key % self.size
    
    def insert(self, key, value):
        hash_value = self.hash_function(key)
        if self.table[hash_value] is None:
            self.table[hash_value] = Node(key, value)
        else:
            node = self.table[hash_value]
            while node.next:
                node = node.next
            node.next = Node(key, value)
    
    def get(self, key):
        hash_value = self.hash_function(key)
        node = self.table[hash_value]
        
        while node:
            if node.key == key:
                return node.value
            node = node.next
        
        raise KeyError("Key not found")