해시 테이블 구현 (Hash Table Implementation)

구현 코드 예시

class HashMap:
    """체이닝 방식의 간단한 해시맵."""

    def __init__(self, capacity=8):
        self.capacity = capacity
        self.size = 0
        self.buckets = [[] for _ in range(capacity)]

    def _index(self, key):
        return hash(key) % self.capacity

    def put(self, key, value):
        bucket = self.buckets[self._index(key)]
        for i, (k, _) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)        # 이미 있으면 값만 교체
                return
        bucket.append((key, value))
        self.size += 1
        if self.size > self.capacity * 0.75:    # 적재율 초과 → 확장
            self._resize()

    def get(self, key, default=None):
        for k, v in self.buckets[self._index(key)]:
            if k == key:
                return v
        return default

    def remove(self, key):
        bucket = self.buckets[self._index(key)]
        for i, (k, _) in enumerate(bucket):
            if k == key:
                bucket.pop(i)
                self.size -= 1
                return True
        return False

    def _resize(self):
        old = self.buckets
        self.capacity *= 2
        self.buckets = [[] for _ in range(self.capacity)]
        for bucket in old:                       # 전부 다시 배치해야 한다
            for k, v in bucket:
                self.buckets[hash(k) % self.capacity].append((k, v))

버킷 안에서 k == key로 한 번 더 비교하는 것에 주목하자. 해시값이 같아도 키가 다를 수 있으므로, 해시 일치는 후보를 좁힐 뿐 최종 판정은 키 자체의 비교다.

좋은 해시 함수의 조건

• 균등 분포: 키들이 버킷 전체에 고르게 흩어져야 한다. 한쪽으로 몰리면 충돌이 폭증한다.
• 결정성: 같은 키는 언제나 같은 값을 내야 한다. 그래서 변경 가능한 객체는 키가 될 수 없다. 파이썬에서 리스트를 dict 키로 쓰면 TypeError가 나는 이유다.
• 빠른 계산: 해시 계산이 느리면 O(1)의 의미가 없다.
• 눈사태 효과: 키가 조금만 달라도 해시값이 크게 달라져야 한다.

자바에서 equals()를 재정의하면 hashCode()도 반드시 함께 재정의해야 하는 이유가 여기 있다. 같다고 판정되는 두 객체가 서로 다른 해시값을 가지면 다른 버킷으로 가서 영영 못 찾는다.

자주 하는 실수

• 해시가 같으면 키도 같다고 가정한다. 버킷 안에서 실제 키 비교가 반드시 필요하다.
• 가변 객체를 키로 쓴다. 넣은 뒤 내용을 바꾸면 해시값이 달라져 찾을 수 없게 된다. 파이썬 튜플은 되지만 리스트는 안 되는 이유다.
• 리사이징 때 위치를 그대로 옮긴다. 버킷 수가 바뀌면 나머지 연산 결과가 달라진다. 전부 다시 계산해야 한다.
• 개방 주소법에서 삭제한 칸을 그냥 비운다. 뒤로 밀려 있던 항목을 못 찾게 된다. 삭제 표식이 필요하다.
• equals만 재정의하고 hashCode를 빼먹는다. 자바 면접 단골이자 실무 버그 단골이다.
• 순서를 기대한다. 해시 테이블은 원래 순서를 보장하지 않는다. 파이썬 dict가 3.7부터 삽입 순서를 유지하는 것은 구현상의 추가 보장일 뿐 해시 테이블의 성질이 아니다.

면접에서 이렇게 물어본다

• 해시 테이블이 평균 O(1)인 이유와 최악에 O(n)이 되는 조건을 설명해 보라.
• 충돌은 왜 피할 수 없는가.
• 체이닝과 개방 주소법의 장단점을 비교해 보라.
• 적재율이란 무엇이며 리사이징은 언제 어떻게 일어나는가.
• 리사이징이 O(n)인데도 삽입이 평균 O(1)인 이유는 무엇인가.
• 좋은 해시 함수의 조건은 무엇인가.
• equals와 hashCode를 함께 재정의해야 하는 이유를 설명해 보라.
• 가변 객체를 키로 쓰면 안 되는 이유는 무엇인가.