좋은 해시 함수의 조건

"해시맵은 해시 함수만큼만 좋아. 나쁜 해시도 여전히 '정답'이긴 해. 다만 O(1)이라는 꿈을 조용히 O(n) 연결 리스트로 되돌려놓을 뿐이지."

좋은 해시의 세 속성

해시 함수는 이런 조건을 갖춰야 해.

결정론적 — 같은 키는 언제나 같은 해시를 내놔야 해. 이게 안 되면 저장한 걸 다시 못 찾아. 타협의 여지가 없어.
균일 — 서로 다른 키를 테이블 전체에 고르게 흩어야 해. 그래야 슬롯이 비슷한 속도로 차고 충돌이 드물지. O(1)을 지켜주는 게 이 성질이야.
빠름 — 입력 길이에 비추어 충분히 빨라야 해. 정수처럼 크기가 고정된 키의 해시는 O(1)로 봐도 되지만, 긴 문자열이나 튜플의 첫 해시는 일반적으로 키 길이만큼 읽어야 한다는 걸 기억해.

좋은 해시에는 눈사태(avalanche) 성질이 있어. 키를 아주 조금만 바꿔도("cat"과 "car"처럼) 해시가 전혀 다른 값으로 튀어. 비슷하게 생긴 키들이 같은 슬롯에 뭉치는 걸 막아주는 게 정확히 이 성질이고.

나쁜 해시가 왜 조용한 살인자인가

합법이면서 최악인 해시 함수를 상상해 봐. 어떤 키가 오든 return 0. 결정론적이고 빠르지. 그리고 재앙이야. 모든 키가 슬롯 0에 떨어지니까 "해시맵"이 선형으로 훑어야 하는 거대한 체인 하나로 주저앉아. 조회는 O(n)이 되는데, 어디에도 고장 난 티가 안 나. 코드는 여전히 '정답'이고 그냥 느릴 뿐이거든. 진짜 키 여럿을 적은 슬롯에 몰아넣는 해시는 이렇게 에러 한 줄 없이 성능만 조용히 부숴. 해시 함수의 균일성이 곧 O(1)과 O(n)의 갈림길이야.

좋은 해시는 결정론적이고, 균일하고, 빠르지. 여기서 위험한 실패는 '정답인데 뭉치는' 경우야. 멀쩡히 돌아가면서 O(1) 조회를 조용히 O(n) 훑기로 떨어뜨리거든. 속도를 지켜주는 건 균일성이야.

반드시 지켜야 하는 계약

객체를 dict 키로 쓰려면 같은 객체는 같은 해시를 가져야 하고, 저장되어 있는 동안 해시가 바뀌면 안 돼. Python에서 값 기반 __eq__를 정의하면서 __hash__를 같이 정의하지 않으면 보통 __hash__ = None이 되고, 그 인스턴스는 해시할 수 없게 돼. str, int, 그리고 해시 가능한 값만 담은 tuple이 대표적인 키야. list, dict, set은 가변이라 기본적으로 해시가 안 되고. 가변 상태를 값 비교와 해시 양쪽에 쓰는 객체라면 아예 키로 안 쓰는 게 안전해.

여담으로, Python은 문자열 해시에 프로세스마다 다른 무작위 시드를 섞어. 그래서 hash("x")가 실행할 때마다 달라지지. 공격자가 전부 충돌하는 키를 미리 만들어 오는 걸 막으려는 의도적인 보안 조치고, 이 트랙 마지막에서 다시 볼 거야.

피파의 고백

커스텀 객체에 값 기반 __eq__를 붙여놓고 dict 키로 쓰려다가 Python한테 "해시 불가"라며 바로 문전박대당한 적이 있어. 예전 같았으면 왜 막냐고 투덜댔겠지만, 그건 거짓말하는 딕셔너리가 생기는 걸 막아준 안전장치였어. 그때 아빠 규칙이 그대로 박혔지. "동등성과 해시는 한 쌍으로 설계해. 그리고 키가 들어간 뒤엔 해시에 쓰는 상태를 건드리지 마."

Code

뭉치는 해시와 균일한 해시, 그리고 eq/hash 계약·python

# 끔찍한 해시 vs 괜찮은 해시 — 같은 데이터, 아주 다른 뭉침.
def terrible_hash(key, size):
    return 0                      # 전부 슬롯 0 -> O(n) 체인

def ok_hash(key, size):
    return hash(key) % size       # Python 해시가 키를 잘 퍼뜨려

keys = ["apple", "banana", "cherry", "date", "fig", "grape"]
for name, fn in [("terrible", terrible_hash), ("ok", ok_hash)]:
    slots = {}
    for k in keys:
        slots.setdefault(fn(k, 8), []).append(k)
    print(name, "-> slot usage:", {s: len(v) for s, v in sorted(slots.items())})
# terrible: 모든 키가 한 슬롯에 (길이 6 체인 하나).
# ok: 키가 여러 슬롯에 퍼짐 (짧은 체인 -> O(1) 조회).

# 커스텀 키의 __eq__/__hash__ 계약:
class Point:
    def __init__(self, x, y): self.x, self.y = x, y
    def __eq__(self, o): return (self.x, self.y) == (o.x, o.y)
    def __hash__(self): return hash((self.x, self.y))   # __eq__ 와 일치해야 함

d = {Point(1, 2): "here"}
print(d[Point(1, 2)])    # 'here' — 같은 점은 같게 해시돼서, 찾아짐

Exercise

누가 문자열을 '문자 코드의 합 mod table_size'로 해싱하자고 제안했어. 이 방식에서 충돌하는 실제 키 두 개를 대고, 왜 심하게 뭉치는지 설명해 봐(힌트는 애너그램이야). 그다음, 어떤 클래스가 __eq__는 id 번호 비교로 정의했는데 __hash__는 Python 기본인 객체 정체성을 그대로 쓴다면 뭐가 깨지는지도 말해.

Hint

'listen'과 'silent'는 애너그램이라 문자 코드 합이 똑같아서 같은 슬롯으로 가. 애너그램끼리는 전부 충돌하니까 균일성과는 거리가 멀지. 그리고 __eq__는 두 객체를 같다고 하는데 __hash__가 서로 다른 해시를 주면, set이나 dict가 둘을 다른 슬롯에 넣어버려서 영영 같은 것으로 안 봐.

좋은 해시의 세 속성

나쁜 해시가 왜 조용한 살인자인가

반드시 지켜야 하는 계약

피파의 고백

Code

External links

Exercise

Progress

댓글 0