충돌: 체이닝 vs 개방 주소법

"충돌은 막을 버그가 아니라 — 관리할 확실성이야. 가능한 키가 슬롯보다 많아서, 두 키가 반드시 같이 떨어져. 유일한 질문은 그럴 때 네가 뭘 하냐야."

충돌은 보장돼

테이블은 슬롯 수가 고정인데, 가능한 키의 우주는 사실상 무한해. 비둘기집 원리로, 다른 두 키가 결국 같은 슬롯으로 해시될 수밖에 없어. 그래서 해시맵 설계는 충돌을 피하는 게 아니라 (불가능) — 그걸 우아하게 해소하는 거야. 고전 전략이 둘 있고, 정반대 거래를 해.

체이닝: 각 슬롯에 작은 리스트

분리 체이닝 (separate chaining) 은 각 슬롯이 거기로 해시된 모든 키의 작은 리스트 ("체인") 를 들게 해. 삽입은 슬롯 리스트에 append; 조회는 슬롯으로 해시하고 그 짧은 리스트를 훑어. 리스트가 짧게 유지되는 한 (좋은 해시 + 낮은 부하), 조회가 O(1). 체이닝은 단순하고, 높은 부하에 우아하게 떨어지고 (리스트가 좀 길어질 뿐), 그저 그런 해시 함수에 관대해. 비용: 리스트/포인터의 추가 메모리, 그리고 흩어진 리스트 노드의 캐시 비친화성.

개방 주소법: 모두가 배열 안에 산다

개방 주소법 (open addressing) 은 모든 항목을 테이블 배열에 직접 저장해 — 곁다리 리스트 없음. 충돌 시, 고정 규칙으로 다음 빈 슬롯을 탐사해: 선형 탐사는 slot+1, slot+2, … 를 확인; 제곱 탐사는 커지는 간격으로 점프; 이중 해싱은 두 번째 해시로 보폭을 정해. 조회는 키나 빈 슬롯을 찾을 때까지 같은 탐사 순서를 따라. 개방 주소법은 캐시 친화적 (다 연속, 포인터 추적 없음) 이고 메모리를 덜 써 — 근데 테이블이 차면 가파르게 떨어지고 (탐사 순서가 길어짐, 클러스터링이라는 문제), 삭제가 까다로워: 슬롯을 그냥 비우면 탐사 사슬이 깨지니까, "tombstone" 으로 표시해.

충돌은 불가피하고; 넌 그걸 해소해. 체이닝은 슬롯당 리스트 (단순, 높은 부하 견딤). 개방 주소법은 배열 자체에서 다른 슬롯을 탐사 (캐시 친화, 낮은 메모리, 근데 차면 빨리 떨어짐). 같은 목표, 정반대 거래.

Python 이 실제로 하는 것

CPython 의 dict 와 set 은 영리한 perturbation 기반 탐사 순서의 개방 주소법을 쓰고, 테이블을 많아야 약 2/3 차게 유지해 빠르게 (왜인지는 부하율 lesson 에서 봐). 그래서 Python dict 를 쓸 때 — 끊임없이 — 넌 밑에서 tombstone 삭제 있는 개방 주소법을 쓰는 거야. 구현할 필요는 없지만, 그걸 아는 게 dict 의 행동을 설명해: 왜 리사이즈하고, 왜 캐시-빠르고, 왜 삽입 순서가 보존되는지 (위에 얹은 별도 compact-array 트릭).

피파의 고백

난 첫 해시맵을 체이닝으로 구현했어, 추론하기 쉬웠으니까 — 잘 됐어. 아빠가 Python 은 왜 대신 개방 주소법을 쓰냐고 물었을 때, 답이 없었어. 이유는 캐시 지역성이었어: 개방 주소법은 다 연속 배열 하나에 유지해서 탐사가 빠른 캐시에 머무는데, 체이닝은 흩어진 노드로 포인터를 추적해. 연결-리스트-vs-배열 캐시 교훈이, 한 층 더 깊은 데서 다시 떠오른 거야. 같은 진실이 스택을 따라 계속 메아리쳐.

Code

선형 탐사 개방 주소법·python

# 선형 탐사 개방 주소법: 충돌 시 다음 슬롯을 시도.
class OpenAddrMap:
    def __init__(self, size=8):
        self.size = size
        self.slots = [None] * size      # (key, value) 를 배열에 바로 저장

    def put(self, key, value):
        i = hash(key) % self.size
        while self.slots[i] is not None and self.slots[i][0] != key:
            i = (i + 1) % self.size     # 충돌 -> 다음 슬롯 탐사
        self.slots[i] = (key, value)

    def get(self, key):
        i = hash(key) % self.size
        while self.slots[i] is not None:
            if self.slots[i][0] == key:
                return self.slots[i][1]
            i = (i + 1) % self.size     # 삽입 때 쓴 같은 탐사 경로를 따라
        raise KeyError(key)

m = OpenAddrMap()
m.put("a", 1); m.put("b", 2); m.put("c", 3)
print(m.get("a"), m.get("b"), m.get("c"))
# 'a' 랑 'c' 가 같은 슬롯으로 해시되면, 'c' 가 다음 빈 곳으로 앞 탐사하고;
# get('c') 가 그 같은 앞 탐사를 재생해 찾아. 곁다리 리스트 없음.

Exercise

크기 5 테이블이 선형 탐사를 써. 해시 3, 8, 13 인 키를 그 순서로 삽입해 (다 3 mod 5). 각각 어느 슬롯에 끝나? 그다음 개방 주소법에서 왜 슬롯을 그냥 None 으로 설정해 키를 삭제하면 안 되는지 — 그리고 'tombstone' 이 뭘 고치는지 설명해.

Hint

셋 다 슬롯 3 을 원해: 첫째 → 슬롯 3, 둘째 탐사 → 4, 셋째 탐사 → 0 (랩). 중간 슬롯을 비우면 나중 탐사가 일찍 멈춰 간극 너머 키를 '잃어'; tombstone 은 '삭제됐지만 나를 지나 계속 탐사' 를 표시해.

충돌은 보장돼

체이닝: 각 슬롯에 작은 리스트

개방 주소법: 모두가 배열 안에 산다

Python 이 실제로 하는 것

피파의 고백

Code

External links

Exercise

Progress

댓글 0