해시 테이블이란? 동작 원리, 코드, 시간 복잡도

해시 테이블이 해결하는 문제

사용자 레코드 100만 건을 저장해 두고 이메일로 하나를 찾아야 한다고 해 봅시다. 리스트를 훑으면 O(n)입니다. 리스트를 정렬해 두면 이진 탐색으로 O(log n)에 찾을 수 있지만 삽입이 느려집니다. 해시 테이블은 레코드가 몇 개든 평균 O(1)에 찾으며, 삽입과 삭제도 똑같이 빠릅니다.

그래서 해시 테이블은 어디에나 있습니다. 프로그래밍 언어의 딕셔너리와 집합, 데이터베이스 해시 인덱스, 캐시, 컴파일러의 심볼 테이블, 중복 제거 등에 쓰입니다.

쉬운 말로 설명하는 원리

번호가 붙은 갈고리 100개가 있는 보관소를 상상해 보세요. 모든 갈고리를 뒤져 내 코트를 찾는 대신, 직원이 이름으로 갈고리 번호를 계산해 곧장 그곳으로 갑니다. 이 번호를 계산하는 함수가 해시 함수입니다. 좋은 해시 함수는 빠르고, 같은 키에는 항상 같은 번호를 주며, 서로 다른 키를 갈고리 전체에 고르게 퍼뜨립니다.

1. h = hash(key)를 계산합니다.
2. 버킷을 고릅니다: index = h % capacity.
3. 그 버킷 안에서만 키를 찾습니다.

예제: 체이닝으로 충돌 처리하기

버킷이 4개인 테이블과 간단한 장난감 해시 함수(글자 순서 번호의 합, a = 1, b = 2, ...)를 사용합니다.

act와 bee는 cat과 충돌합니다. 이제 bee를 조회하려면 버킷 0의 항목 세 개를 확인해야 합니다. 해시 함수가 나쁘거나(글자 합은 순서를 무시합니다) 버킷이 너무 적으면 체인이 길어져 테이블이 느려집니다. 실제 해시 함수는 키의 모든 비트를 섞고, 실제 테이블은 너무 차면 크기를 키웁니다.

체이닝을 사용한 파이썬 구현

각 버킷은 [key, value] 쌍의 리스트입니다. 항목 수가 버킷 수의 0.75배(로드 팩터)를 넘으면 테이블은 용량을 두 배로 늘리고 모든 항목을 다시 삽입합니다.

class HashTable:
    def __init__(self, capacity=8):
        self.buckets = [[] for _ in range(capacity)]
        self.size = 0
    def _bucket(self, key):
        return self.buckets[hash(key) % len(self.buckets)]
    def put(self, key, value):
        bucket = self._bucket(key)
        for pair in bucket:
            if pair[0] == key:
                pair[1] = value        # update existing key
                return
        bucket.append([key, value])
        self.size += 1
        if self.size > 0.75 * len(self.buckets):
            self._resize()
    def get(self, key, default=None):
        for k, v in self._bucket(key):
            if k == key:
                return v
        return default
    def delete(self, key):
        bucket = self._bucket(key)
        for i, (k, _) in enumerate(bucket):
            if k == key:
                bucket.pop(i)
                self.size -= 1
                return True
        return False
    def _resize(self):
        old = [pair for bucket in self.buckets for pair in bucket]
        self.buckets = [[] for _ in range(2 * len(self.buckets))]
        self.size = 0
        for k, v in old:
            self.put(k, v)

t = HashTable()
for i, word in enumerate(["red", "green", "blue", "cyan", "pink", "gold", "gray"]):
    t.put(word, i)
t.put("red", 100)
t.delete("blue")
print(t.get("red"), t.get("blue"), t.size, len(t.buckets))  # 100 None 6 16

충돌 해결 전략 비교

CPython의 dict는 섭동(perturbation)을 적용한 탐사 순서의 개방 주소법을 쓰며, 파이썬 3.7부터는 순회가 삽입 순서를 따르도록 보장합니다. Java의 HashMap은 체이닝을 쓰고 긴 체인을 균형 트리로 바꿉니다.

시간 복잡도와 공간 복잡도

평균 O(1)은 좋은 해시 함수와 제한된 로드 팩터에 달려 있습니다. 파이썬은 프로세스마다 문자열 해시를 무작위화(해시 시딩)하므로, 공격자가 충돌하는 키를 대량으로 보내 서버를 요청당 O(n)으로 느리게 만들기 어렵습니다.

흔한 실수

• 가변 객체를 키로 쓰거나, 클래스에 __hash__ 없이 __eq__만 정의하는 실수. 같은 객체는 해시도 같아야 합니다.
• 정렬된 순서를 기대하는 실수. 해시 테이블은 빠른 조회를 줄 뿐 순서는 주지 않습니다. 범위 질의나 최솟값이 필요하면 정렬된 리스트나 균형 트리(이진 탐색 트리)를 쓰세요.
• 실행 간에 hash() 값이 같다고 믿는 실수: PYTHONHASHSEED를 고정하지 않으면 문자열 해시는 파이썬 프로세스마다 달라집니다. 안정적인 해시가 필요하면 hashlib를 쓰세요.
• 해시 테이블을 보안 도구로 착각하는 실수. 해시 테이블은 빠른 비암호학적 해시를 사용합니다. 비밀번호에는 전용 비밀번호 해싱 함수가 필요합니다.

언제 쓰는가와 면접 단골 활용

"이거 본 적 있나?" 또는 "이 키의 값은 무엇인가?"에 빠르게 답해야 할 때마다 해시 테이블을 쓰세요. 순서, 범위, 가장 가까운 키도 필요하다면 이진 탐색 트리나 정렬된 배열을 쓰세요.

대표 문제: 투 섬(각 숫자의 인덱스를 저장하고 target - x를 조회), 빈도 세기(collections.Counter), 정렬한 글자로 애너그램 묶기, 중복 탐지, 동적 계획법의 메모이제이션이 있습니다.

def two_sum(nums, target):
    seen = {}                      # value -> index
    for i, x in enumerate(nums):
        if target - x in seen:
            return seen[target - x], i
        seen[x] = i
    return None
print(two_sum([2, 7, 11, 15], 9))  # (0, 1)