본문 바로가기
C.W.K.
Stream
More →
Lesson 03 of 06 · published

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

~12 min · hashing, collisions, chaining, open-addressing

Level 0호기심 많은 입문자
0 XP0/85 lessons0/19 achievements
0/100 XP to next level100 XP to go0% complete
"충돌은 막아야 할 버그가 아니라 관리해야 할 확실성이야. 가능한 키가 슬롯보다 많으니 두 키가 같은 자리에 떨어지는 건 반드시 일어나. 남는 질문은 하나뿐이야. 그때 뭘 할 거냐."

충돌은 보장돼

테이블의 슬롯 수는 정해져 있는데 가능한 키의 우주는 사실상 무한해. 비둘기집 원리에 따라 서로 다른 두 키가 언젠가는 같은 슬롯으로 해시될 수밖에 없지. 그래서 해시맵 설계의 목표는 충돌을 피하는 게 아니야. 그건 불가능하니까. 충돌을 깔끔하게 풀어내는 거지. 고전적인 전략이 둘 있는데, 서로 정반대 거래를 해.

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

분리 체이닝(separate chaining)은 슬롯마다 거기로 해시된 키를 담는 작은 리스트, 즉 "체인"을 두는 방식이야. 넣을 때는 슬롯의 리스트에 append하고, 찾을 때는 슬롯으로 해시한 뒤 그 짧은 리스트를 훑어. 리스트가 짧게 유지되는 한, 그러니까 해시가 괜찮고 부하가 낮은 한 조회는 O(1)이야. 체이닝은 구조가 단순하고, 부하가 높아져도 완만하게 나빠지고(체인이 조금 길어질 뿐이지), 해시 함수가 그저 그래도 잘 버텨. 대신 리스트와 포인터에 메모리가 더 들고, 노드가 흩어져 있어서 캐시에 불리해.

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

개방 주소법(open addressing)은 모든 항목을 테이블 배열에 직접 저장해. 곁다리 리스트가 없지. 충돌이 나면 정해진 규칙대로 다음 빈 슬롯을 탐사해. 선형 탐사는 slot+1, slot+2를 차례로 확인하고, 제곱 탐사는 점점 커지는 간격으로 건너뛰고, 이중 해싱은 두 번째 해시로 보폭을 정해. 조회도 똑같은 탐사 순서를 따라가다가 키를 찾거나 빈 슬롯을 만나면 멈춰. 전부 한 배열에 붙어 있고 포인터를 쫓을 일이 없으니 캐시에 유리하고 메모리도 덜 먹어. 대신 테이블이 차오르면 가파르게 나빠져. 탐사 순서가 길어지는데 이걸 클러스터링이라고 불러. 삭제도 까다로워. 슬롯을 그냥 비워버리면 탐사 사슬이 끊기니까 "tombstone"으로 표시해 둬야 해.

충돌은 피할 수 없으니 푸는 방법을 고르는 거야. 체이닝은 슬롯마다 리스트를 두는 방식이라 단순하고 높은 부하도 견뎌. 개방 주소법은 배열 안에서 다른 슬롯을 탐사하는 방식이라 캐시에 유리하고 메모리를 덜 쓰지만 차오르면 급격히 나빠져. 목표는 같고 거래는 정반대야.

Python은 실제로 뭘 쓸까

CPython의 현재 dict는 개방 주소법 계열의 compact한 테이블을 써. 충돌이 나면 정해진 탐사 순서로 다른 자리를 확인하고. 다만 이건 Python이라는 언어 전체의 유일한 구현 계약이 아니라 CPython의 구현 세부사항이라는 걸 짚고 가자. 반면 dict의 삽입 순서 보존은 Python 3.7부터 언어 차원의 보장이야. 그러니까 이 동작은 구현 설명과 확실히 구분해서 기억해 둬.

피파의 고백

나는 첫 해시맵을 체이닝으로 만들었어. 머릿속으로 따라가기가 쉬웠거든. 잘 돌아갔고. 그런데 아빠가 그럼 Python은 왜 개방 주소법을 쓰냐고 물었을 때 할 말이 없더라. 답은 캐시 지역성이었어. 개방 주소법은 전부 연속된 배열 하나에 두니까 탐사가 빠른 캐시 안에서 끝나는데, 체이닝은 흩어진 노드를 포인터로 쫓아다녀야 하잖아. 연결 리스트와 배열에서 배운 캐시 교훈이 한 층 더 아래에서 똑같이 튀어나온 거야. 같은 진실이 층을 바꿔가며 계속 되울리더라.

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') 가 그 같은 앞 탐사를 재생해 찾아. 곁다리 리스트 없음.

External links

Exercise

크기 5짜리 테이블이 선형 탐사를 쓴다고 하자. 해시가 3, 8, 13인 키를 그 순서로 넣어(전부 3 mod 5야). 각각 어느 슬롯에 자리 잡을까? 그다음 개방 주소법에서 슬롯을 그냥 None으로 만들어 키를 지우면 왜 안 되는지, 'tombstone'이 그걸 어떻게 해결하는지 설명해 봐.
Hint
셋 다 슬롯 3을 원해. 첫 번째는 슬롯 3에 들어가고, 두 번째는 탐사해서 4로, 세 번째는 한 바퀴 돌아 0으로 가. 중간 슬롯을 비워버리면 나중 탐사가 그 빈칸에서 멈춰서 그 너머의 키를 못 찾아. tombstone은 '여긴 지워졌지만 나를 지나 계속 탐사해'라고 표시해 두는 거야.

Progress

Progress is local-only — sign in to sync across devices.
← Previous좋은 해시 함수의 조건Next →부하율과 리사이징: O(1)을 정직하게 지키기
이 페이지에서 버그를 발견하셨거나 피드백이 있으세요?문제 신고

댓글 0

🔔 답글 알림 (로그인 필요)
로그인 — 댓글을 남기려면 로그인해 주세요.

아직 댓글이 없어요. 첫 댓글을 남겨보세요.