Python

[Python] Hash Collision과 Perfect Hashing: 왜 충돌은 피할 수 없을까?

Hoonia 2025. 4. 9. 17:05

Hash Table(해시 테이블)은 빠른 탐색과 삽입이 가능한 자료구조로, 알고리즘이나 시스템 설계에서 자주 사용된다. 파이썬의 dict 역시 해시 테이블 기반으로 동작한다.
이번에는 해시 테이블을 직접 구현해보면서 Hash Collision(해시 충돌)이 실제로 어떻게 발생하는지를 실험해봤고, Perfect Hashing(완전 해시)이라는 개념도 함께 정리해봤다.

체이닝 방식으로 해시맵 구현해보기

아래는 Chaining(체이닝) 방식으로 충돌을 처리하는 간단한 해시맵 구현이다.
self.table은 버킷 리스트이며, 같은 해시값을 가진 키들이 하나의 버킷 안 리스트에 연결된다.

class ChainedHashMap:
    def __init__(self, size: int = 1):
        self.size = size
        self.table = [[] for _ in range(size)]
    
    def hash(self, key: str) -> int:
        # 문자열 key를 숫자로 변환한 뒤, 테이블 크기로 나눈다
        return sum(ord(c) for c in key) % self.size

    def put(self, key: str, value: int) -> None:
        for i, (k, v) in enumerate(self.table[self.hash(key)]):
            if k == key:
                self.table[self.hash(key)][i] = (key, value)
                return
        self.table[self.hash(key)].append((key, value))

    def get(self, key: str) -> int | None:
        for k, v in self.table[self.hash(key)]:
            if k == key:
                return v
        return -1
    
    def remove(self, key: str) -> None:
        for i, (k, v) in enumerate(self.table[self.hash(key)]):
            if k == key:
                del self.table[self.hash(key)][i]
                return
        return -1

hash() 함수는 key의 각 문자를 ord()로 정수화한 값을 모두 더하고, 테이블 크기(size)로 나눈다.
매우 단순한 방식이지만, 해시 함수의 기본 원리를 실험해보기엔 적당하다.

Hash Collision(해시 충돌)은 어떻게 발생하는가?

테이블 크기를 1로 설정하면 어떤 키든 항상 같은 버킷(인덱스 0)으로 해시된다. 즉, 충돌이 강제로 발생하는 상황이 된다.

hashmap = ChainedHashMap(size=1)
hashmap.put("a", 1)
hashmap.put("b", 2)
hashmap.put("abc", 3)

이 경우 버킷 0에는 다음과 같이 저장된다:

버킷 0: [('a', 1), ('b', 2), ('abc', 3)]

서로 다른 키들이 같은 버킷에 저장되는 것이 바로 Hash Collision(해시 충돌)이며, Chaining(체이닝) 방식에서는 이처럼 내부 리스트를 통해 충돌을 해결한다.

충돌은 피할 수 없을까?

이쯤에서 이런 질문이 생긴다:
"해시 테이블이 무한히 크다면, 충돌을 아예 없앨 수 있지 않을까?"

이론적으로는 가능하다.
만약 테이블이 무한한 크기를 가지고 있고, 각 키에 대해 항상 고유한 인덱스를 계산해주는 Perfect Hash Function(완벽한 해시 함수)이 존재한다면, 충돌은 발생하지 않을 수 있다.

하지만 현실은 다음과 같다:

  • 실제 메모리는 유한하다. 테이블 크기를 무한히 키울 수 없다.
  • 대부분의 해시 함수는 무한한 문자열 집합을 유한한 숫자 범위로 압축해야 한다. 이 과정에서 충돌은 필연적으로 발생한다.
  • 따라서 현실의 해시 테이블은 충돌이 전제된 설계이며, Chaining(체이닝), Open Addressing(오픈 어드레싱) 등의 방법으로 충돌을 처리한다.

Perfect Hashing(완전 해시)이란?

Perfect Hashing(완전 해시)은 말 그대로 충돌이 단 한 번도 발생하지 않는 해시 구조를 의미한다.
이 구조는 다음 조건을 만족할 때만 구현할 수 있다:

  • 사용할 Key Set(키 집합)이 고정되어 있고
  • 해당 키들을 미리 알고 있으며
  • 각 키를 고유한 인덱스로 매핑할 수 있는 해시 함수를 구성할 수 있을 때

예를 들어 어떤 시스템에서 사용할 키가 "if", "else", "while", "return" 같은 고정된 키워드라면, 이들에 대해서는 완전 해시 함수를 만들 수 있다.

마무리하며

이번 실험을 통해 Hash Collision(해시 충돌)이 어떻게 발생하는지, 그리고 그 충돌을 어떻게 처리할 수 있는지를 직접 확인해볼 수 있었다.
충돌은 해시 테이블의 실패가 아니라, 오히려 예측된 현상이라는 점도 인상 깊었다. 충돌을 완전히 피할 수 없다면, 잘 다루는 설계가 핵심이라는 걸 다시금 느꼈다.