좋은 해시 함수를 만드는 것

"해시맵은 해시 함수만큼만 좋아. 나쁜 건 여전히 '정답' 이야 — 그냥 네 O(1) 꿈을 조용히 O(n) 연결 리스트로 되돌릴 뿐이야."

좋은 해시의 세 속성

해시 함수는 이래야 해:

결정론적 — 같은 키가 늘 같은 해시를 만들어. 이거 없으면 저장한 걸 못 찾아. 타협 불가.
균일 — 다른 키를 테이블에 고르게 퍼뜨려, 슬롯이 비슷한 속도로 차고 충돌이 드물게. 이게 O(1) 을 지켜.
빠름 — 계산이 싸야 (O(1) 에 가깝게), 안 그러면 직접 주소법으로 얻은 속도를 해시 자체가 먹어.

좋은 해시는 눈사태 (avalanche) 성질이 있어: 키를 살짝만 바꿔도 ("cat" vs "car") 해시가 완전히 다른 값으로 흩어져, 그게 정확히 비슷한 키가 같은 슬롯에 뭉치는 걸 막아.

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

최악의 합법적 해시 함수를 생각해: 모든 키에 return 0. 결정론적이고 빨라 — 그리고 재앙이야. 모든 키가 슬롯 0 에 떨어져서, "해시맵" 이 선형으로 훑는 거대한 체인 하나로 무너져. 조회가 O(n) 이고, 아무것도 망가져 보이지 않아; 코드는 '정답', 그냥 느릴 뿐. 그래서 뭉치는 해시 (많은 진짜 키를 적은 슬롯에 매핑) 가 에러 없이 성능을 조용히 파괴해. 해시 함수의 균일성이 O(1) 과 O(n) 의 차이야.

좋은 해시는 결정론적, 균일, 빠름. '정답인데 뭉침' 이 위험한 실패야: 계속 작동하면서 O(1) 조회를 조용히 O(n) 훑기로 떨어뜨려. 균일성이 속도를 지켜.

네가 존중해야 할 계약

해시 함수를 밑바닥부터 쓸 일은 드물어 — 근데 네 객체를 dict 키로 쓰는 순간, 계약을 물려받아: 두 객체가 같으면, 같은 해시를 가져야 한다. Python 에선 __eq__ 랑 __hash__ 가 일치해야 한다는 뜻. 어기면 — '같은' 두 객체가 다른 해시 — 맵이 그걸 다른 슬롯에 저장해서, 하나를 다른 걸로 절대 못 찾아. 같으면-해시도-같음이 해싱을 믿을 수 있게 만드는 규칙이야.

(여담: Python 은 문자열 해시를 프로세스별 무작위 시드로 소금 쳐서, hash("x") 가 실행마다 달라. 공격자가 다 충돌하는 키를 만드는 걸 막는 의도적 보안 조치야 — 이 트랙 마지막 lesson 에서 다시 봐.)

피파의 고백

한 번 커스텀 객체를 dict 키로 만들고, 두 인스턴스가 같게 비교되도록 __eq__ 를 정의하고, 거기 맞게 __hash__ 정의하는 걸 잊었어. 맵이 '같은' 두 객체를 다른 슬롯에 신나게 저장하고 조회하니 둘 다 없다고 맹세했어. 에러 없음 — 그냥 거짓말하는 딕셔너리. 아빠의 규칙, 그 뒤로 박혔어: "__eq__ 를 건드리면, __hash__ 를 건드려. 둘은 한 쌍이거나 버그거나."

Code

뭉치는 해시 vs 균일, 그리고 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