충돌하면 테이블 안의 다른 빈 칸을 찾아 넣는 방식(open addressing). 모든 데이터가 배열 하나에 들어간다.
탐사 방식 세 가지
① 선형 탐사(linear probing) — 한 칸씩 뒤로 h, h+1, h+2, h+3, … 가장 단순하고 캐시 효율이 최고다(바로 옆 칸이라 이미 캐시에 있다). 문제는 1차 군집화(primary clustering) — 값이 뭉치면 그 덩어리가 계속 커진다.
[ ][ ][A][B][C][D][ ][ ]
└── 이 구간에 해시되면 전부 D 뒤로 밀린다 → 덩어리가 더 커짐
② 제곱 탐사(quadratic probing) — 간격을 제곱으로
- h, h+1², h+2², h+3², … — = h, h+1, h+4, h+9, … 1차 군집화는 없어지지만, 같은 버킷으로 해시된 키끼리는 같은 경로를 밟는다 (2차 군집화).
③ 이중 해싱(double hashing) — 간격 자체를 두 번째 해시로 h, h + 1·h₂(key), h + 2·h₂(key), … 키마다 탐사 경로가 달라 군집화가 가장 적다. 대신 해시 계산이 두 번이다.
삭제가 까다롭다 — 묘비(tombstone)
[A][B][C] A, B, C 가 모두 같은 버킷 0에 해시됐다고 하자
↑ B를 그냥 지우면
[A][ ][C] get(C) → 0번부터 탐사 → 1번이 비었네 → "없다"고 판단 ✗
중간에 빈 칸이 생기면 탐사가 거기서 멈춰 뒤의 값을 못 찾는다. 그래서 지운 자리에 "여기 있었지만 지워짐" 표시(묘비)를 남긴다.
- [A][🪦][C] — 탐사는 묘비를 지나쳐 계속 → C를 찾는다
묘비가 쌓이면 탐사가 길어지므로 주기적으로 재해싱해 정리해야 한다. 체이닝에는 없는 부담이다.
부하율의 벽
배열 안에만 넣으므로 부하율이 1을 넘을 수 없다. 그리고 1에 가까워질수록 탐사 길이가 급격히 늘어난다.
부하율 0.5 → 평균 탐사 약 1.5회 부하율 0.9 → 평균 탐사 약 5.5회
- 부하율 0.99 → 평균 탐사 약 50회 — ← 사실상 붕괴
그래서 개방 주소법은 부하율을 0.5~0.7 이하로 유지한다. 체이닝보다 빈 공간을 더 많이 남겨 둬야 한다.
왜 그래도 쓰나 — 캐시
모든 값이 연속된 배열에 있어 탐사 중 캐시 히트가 잘 난다. 체이닝은 포인터를 따라 힙 여기저기를 뛰므로 캐시 미스가 잦다. 현대 CPU에서 이 차이는 복잡도 상수항보다 큰 영향을 준다.
파이썬 dict, Go map, 여러 고성능 해시맵 라이브러리가 개방 주소법을 쓰는 이유다.