해시 테이블 내부 완전 정복 — Open Addressing, Robin Hood, Swiss Table, SipHash, SIMD까지 (2025)

0. 같은 자료구조가 언어마다 다른 이유

모든 언어가 해시 테이블을 제공한다. 이름만 다를 뿐:

• Python dict
• JavaScript Map, 객체 속성
• Java HashMap
• C++ std::unordered_map
• Go map
• Rust HashMap
• Swift Dictionary

모두 같은 "O(1) 평균 삽입/조회" 인터페이스. 그런데 내부 구현을 열어보면 완전히 다르다. 어떤 건 체이닝, 어떤 건 오픈 어드레싱, 어떤 건 트리 폴백, 어떤 건 SIMD 병렬 탐색.

왜 이렇게 다양한가? 이 글은 해시 테이블의 내부 알고리즘이 지난 60년간 어떻게 진화했는지, 각 언어가 어떤 트레이드오프를 택했는지, 그리고 "Hash Flooding" 같은 보안 공격이 왜 알고리즘 선택을 강제했는지를 파헤친다.

1. 기본 문제 — 무한 주소를 유한 테이블에 매핑

1.1 이상적 세계

"이름" → "전화번호" 매핑. 이름이 10억 개 가능, 테이블 크기는 1000.

10억 가지 이름을 1000 개 슬롯에 욱여넣으려면 충돌 (collision) 이 불가피. 해시 테이블의 모든 알고리즘은 결국 "충돌을 어떻게 다룰 것인가" 의 답이다.

1.2 해시 함수의 역할

hash("Alice") → 1,234,567,890
slot = hash("Alice") mod 1000 = 890

좋은 해시 함수의 조건:

• 균등성: 입력 분포가 이상해도 출력은 균등.
• 결정론: 같은 입력 = 같은 출력.
• 빠름: 해시 계산 자체가 병목이 안 되도록.
• 보안 (때때로): 공격자가 충돌을 의도적으로 못 만들게.

1.3 왜 % N 인가 — 그리고 파워 오브 투의 트릭

hash % table_size 로 슬롯 선택. 하지만 % 는 느린 연산.

파워 오브 투: table_size = 2^k 이면 hash & (size - 1) 로 대체 가능 (비트 AND). 10배 빠름.

Java HashMap, Rust HashMap, Swift Dictionary 가 이 방식. Python 3.3+ 도 채택.

단점: 해시의 하위 비트만 씀 → 해시 함수가 하위 비트에 편향돼 있으면 재앙. 그래서 Java 는 해시를 한 번 더 섞는다 :

static int hash(Object key) {
    int h = key.hashCode();
    return h ^ (h >>> 16);  // 상하위 섞기
}

2. 충돌 해결 전략 — 체이닝 vs 오픈 어드레싱

2.1 체이닝 (Separate Chaining)

각 슬롯이 연결 리스트 로 여러 엔트리 저장:

Slot 0: → null
Slot 1: → [Alice, 010...] → [Charlie, 010...] → null
Slot 2: → [Bob, 010...] → null
Slot 3: → null

장점:

• 구현 단순.
• 삭제 쉬움.
• Load factor > 1 가능 (슬롯보다 엔트리 많아도 됨).

단점:

• 캐시 미스: 연결 리스트 노드들이 메모리 여기저기 흩어짐.
• 각 노드마다 포인터 오버헤드 (16-24 바이트).
• 긴 체인에서 공격 받을 수 있음 (Hash Flooding).

2.2 오픈 어드레싱 (Open Addressing)

슬롯이 꽉 차면 다음 슬롯 에 넣음. 별도 자료구조 없이 한 배열만 사용.

Linear Probing: 다음 슬롯으로 한 칸씩:

hash("Alice") → slot 1 (비어있음) → 저장
hash("Bob")   → slot 1 (차 있음)  → slot 2 (비어있음) → 저장
hash("Charlie") → slot 1 → 2 → 3 → 저장

장점:

• 캐시 친화: 인접 슬롯 순차 접근.
• 포인터 없음.
• Load factor < 1 에서 매우 빠름.

단점:

• Primary Clustering: 긴 "연속 점유 구간" 발생.
• 삭제가 어려움 (tombstone 필요).
• Load factor 가 0.7 넘으면 급격 저하.

2.3 Quadratic Probing, Double Hashing

• Quadratic: 다음 슬롯을 1, 4, 9, 16, ... (제곱수) 떨어져 탐색.
• Double Hashing: 두 번째 해시 함수로 스텝 크기 결정.

클러스터링 완화. 하지만 캐시 효율이 linear probing 보다 나쁨. 대부분 현대 구현은 linear.

2.4 Load Factor — 언제 확장할 것인가

load_factor = 엔트리 수 / 슬롯 수

• 체이닝: 보통 0.75 에서 확장.
• 오픈 어드레싱: 0.5 ~ 0.7 에서 확장 (더 일찍).

확장 시 모든 엔트리를 새 테이블에 재해싱. 일회성 O(n) 비용. 거대한 맵에서는 수 초 멈춤 가능.

3. Java HashMap — 체이닝 + Red-Black Tree (Java 8, 2014)

3.1 왜 트리로 폴백하는가

체이닝 + 악의적 입력 = 모든 키가 같은 버킷으로 → 체인 길이 O(n) → 조회가 O(n).

Java 8 이전: 체인이 길어지면 그냥 느려짐. Java 8+: 체인 길이 > 8 이면 Red-Black Tree 로 변환 → O(log n) 복구.

// HashMap.java 의 TreeNode 로직
if (binCount >= TREEIFY_THRESHOLD - 1)  // 8
    treeifyBin(tab, hash);

3.2 버킷 구조

bucket[0] → null
bucket[1] → Node(Alice) → Node(Bob) → Node(...)    // 짧으면 리스트
bucket[2] → TreeNode(...)                           // 길면 Red-Black Tree
bucket[3] → null

3.3 Hash Flooding 공격

2003년 Crosby & Wallach 의 논문이 공개: HTTP 파라미터를 JSON 으로 받는 서버가 있다면, 공격자가 같은 해시를 가진 수천 개 키를 전송 → 파싱에 O(n²) → 서버 마비.

Java 8 의 트리 폴백은 이 공격의 완화책. 체인 길이가 선형이 아니라 로그로 자라므로 O(n log n) 최악.

3.4 여전한 한계

• 컴퓨터 아키텍처 관점에서 포인터 추적 다수 → 캐시 미스.
• TreeNode 는 더 큰 오브젝트 → GC 부담.
• 대량 동시 접근 시 ConcurrentHashMap 이 더 복잡한 구조.

4. Rust HashMap — SipHash 의 보안 우선 철학

4.1 Rust 의 선택 (2016~)

Rust 표준 라이브러리 HashMap: 오픈 어드레싱 + Robin Hood Hashing + SipHash.

2022년 Swiss Table 기반 hashbrown 으로 내부 교체. 하지만 기본 해시는 여전히 SipHash-1-3.

4.2 SipHash — MAC 급 해시

SipHash (Aumasson & Bernstein, 2012) 는 암호학적 해시:

• 128비트 키 로 초기화.
• 출력 예측 불가 (키 없이).
• 일반 해시보다 느리지만 보안성 높음.

왜 느린 걸 기본으로?

Hash Flooding 공격이 가능한 모든 사용 사례를 기본으로 안전하게.

Rust 프로그램이 웹 프레임워크에서 쓰이면 외부 입력을 받음 → 기본이 안전해야 함.

성능이 중요하면 개발자가 의도적으로 FxHash 같은 빠른 해시로 교체 :

use fxhash::FxHashMap;
let mut map = FxHashMap::default();

4.3 Robin Hood Hashing — 공평한 도둑

Linear probing 의 변형. "긴 거리 이동한 엔트리를 우대."

삽입:

• 슬롯에 이미 엔트리가 있음.
• 내 probe 거리 > 기존 엔트리의 probe 거리 이면 자리를 뺏고 기존을 다음으로 밀어냄.

결과: 모든 엔트리의 probe 거리가 평등해짐 → 최악 조회 시간 단축.

이름의 유래: "부자 (짧은 거리) 에게서 뺏어 가난한 자 (긴 거리) 에게 준다" = Robin Hood.

4.4 백워드 시프트 삭제

일반 linear probing 삭제는 tombstone 필요. Robin Hood 는:

• 삭제된 슬롯의 다음 엔트리들을 한 칸씩 앞으로 당김.
• 단, 당긴 엔트리가 자기 원래 위치면 멈춤.

Tombstone 없이 깔끔한 삭제. 삭제 후에도 probe 거리 유지.

5. Swiss Table — 2017년 Google의 혁명

5.1 등장

Matt Kulukundis 가 CppCon 2017 에서 "Designing a Fast, Efficient, Cache-friendly Hash Table" 발표. Abseil 라이브러리에 포함. 이후 Rust hashbrown, Go 1.24 map 이 같은 아이디어.

5.2 핵심 아이디어 — 메타데이터 분리

기존: 각 슬롯 = [hash, key, value] 또는 [empty/occupied flag, key, value].

Swiss Table: 컨트롤 바이트 배열 을 별도 관리.

ctrl: [h2, h2, empty, deleted, h2, h2, h2, empty, ...] (각 1바이트)
entries: [key+value, key+value, ..., ]

• h2 = 해시의 하위 7비트 (Matches 확인용).
• empty, deleted 는 특수 값.
• 컨트롤 바이트가 연속 메모리 → SIMD 병렬 비교.

5.3 SIMD 로 16개 슬롯 동시 검사

조회 과정:

1. hash(key) 계산 → h1, h2 분리
2. slot = h1 % size 로 시작
3. ctrl[slot..slot+16] 을 SSE 레지스터로 한 번에 로드
4. h2 와 16바이트 비교 (_mm_cmpeq_epi8)
5. 매치된 위치들 추출 → entries[pos] 검사
6. empty 비트가 있으면 종료 (더 탐색 안 함)

한 번의 SIMD 명령으로 16개 슬롯 동시 검사. x86-64 SSE2 로 2 사이클, AVX2 로 32개 동시.

5.4 성능 비교

ADS 팀 벤치마크 (2017):

• std::unordered_map 대비 2-3배 빠름.
• 메모리 사용량 50% 감소.
• 최악 탐색 거리 훨씬 짧음.

5.5 Rust hashbrown, Go 1.24

• Rust: hashbrown crate → std HashMap 이 2022년 이를 채택.
• Go 1.24 (2024): 표준 map 을 Swiss Table 기반으로 교체. 30% 빠름, 메모리 20% 감소.

한 알고리즘이 5-10년 만에 주요 언어 표준에 모두 도입된 드문 예.

6. Python dict — Compact, Ordered

6.1 Python 3.6+ 의 디자인

Raymond Hettinger 가 2016년 제안한 구조:

indices: [None, 0, None, 1, None, 2, ...]    (sparse)
entries: [(hash, key, value), (hash, key, value), ...]  (dense, 삽입 순서)

• indices 가 작은 배열 (int8, int16, int32) → 메모리 절약.
• entries 는 밀집 → 삽입 순서 유지 (Python 3.7 부터 공식 보장).
• 반복이 빠름 (entries 를 순차 탐색).

6.2 왜 충돌 탐색이 특이한가

Python 의 probe 함수는 perturbation 을 쓴다:

i = (5 * i + 1 + perturb) & mask;
perturb >>= 5;

해시의 상위 비트까지 점진적으로 활용 → 공격적 입력에도 분산 보장.

6.3 SipHash 도입 (Python 3.4+)

2012년 Hash Flooding 공격이 공개되자 Python 도 SipHash 로 전환. 기본 hash() 가 문자열에 대해 SipHash-2-4. 그래서 Python REPL 마다 해시값이 달라짐 (랜덤 키):

>>> hash("hello")
-7193419568434834712   # 세션마다 다름

7. C++ std::unordered_map — 체이닝의 족쇄

7.1 표준의 제약

C++11 표준이 std::unordered_map 을 정의할 때 몇 가지 요구사항이 뒤따라오는 성능 제한:

• iterator stability: 엔트리 삽입/삭제 후에도 기존 iterator 유효. → 재해싱 시에도.
• 포인터/참조 stability: &map[key] 가 재해싱 후에도 유효해야 함.

이 요구사항 때문에 체이닝 (포인터 저장) 이 사실상 강제됨. Linear probing 은 재해싱 시 엔트리 위치가 바뀌어서 불가능.

결과: std::unordered_map 은 현대 해시 테이블 중 가장 느린 축:

• 각 엔트리가 heap 할당.
• 버킷 = 연결 리스트 포인터.
• 캐시 miss 잔치.

7.2 대안 라이브러리

• Abseil flat_hash_map: Swiss Table. 2-3배 빠름. Google 내부 표준.
• tsl::robin_map, tsl::hopscotch_map: robin hood, hopscotch.
• boost::unordered_flat_map (Boost 1.81+): 역시 Swiss Table 계열.

C++ 표준 위원회가 차기 표준에서 이 제약을 완화할지 논의 중.

8. JavaScript Map — V8 의 진화

8.1 객체 속성 vs Map

ES6 Map 이전에는 객체를 맵처럼 사용. 문제:

• 키가 문자열만.
• prototype 오염 (__proto__ 등).
• 반복 순서 불명.

Map 은:

• 임의 타입 키.
• 삽입 순서 보장.
• 별도 자료구조로 최적화.

8.2 V8 의 Map 구현

V8 는 OrderedHashMap:

• 체이닝 기반.
• 삽입 순서 배열 + 해시 테이블.
• 대용량에서 느림 (V8 팀이 이를 알고 있고 개선 중).

2020년대 초반 Shift-Reduce Hash Table 등 새 구현 제안 있었으나 아직 표준 미도입.

8.3 객체의 속성 최적화

V8 의 객체 속성 접근은 Hidden Classes (C++의 vtable 과 유사) + Inline Cache 로 O(1). 사실상 struct field 접근 수준. 하지만 속성 이름이 동적이면 Dictionary Mode 로 fallback → 느림.

"단일 핫한 객체는 필드 제한" 이 V8 최적화의 기본 조언.

9. Go map — 내부 설계와 2024년 Swiss Table 전환

9.1 Go 1.23 까지의 구조

각 버킷이 8개 슬롯:

bucket {
    topbits[8]    // 해시의 상위 8비트 (빠른 미스 판정)
    keys[8]
    values[8]
    overflow *bucket  // 오버플로우 체인
}

• 8개가 한 캐시 라인 근처에 모임 → 효율.
• overflow 가 생기면 이중 연결 리스트.

9.2 1.24 의 Swiss Table 전환

2024년 Go 1.24: 표준 map 을 Swiss Table 로 교체. 성능 벤치:

• 조회 30% 빠름.
• 메모리 15-20% 감소.
• 반복 미소 느려짐 (tradeoff).

이는 Go 설계 철학의 변화를 상징. 초기 Go 는 단순성 우선 → 점점 성능 튜닝 수용.

10. 해시 함수들 — 용도별 선택

10.1 범용 빠른 해시

• FNV-1a: 단순, 짧은 문자열.
• MurmurHash3: 범용, 균등 분포 좋음.
• xxHash, xxHash3: 매우 빠름 (수 GB/s). 보안 없음.
• CityHash, FarmHash: Google. xxHash 대비 비슷한 속도.

10.2 해시 플러딩 내성

• SipHash-2-4: 완전 보안 모드.
• SipHash-1-3: Rust 기본. 성능/보안 타협.
• aHash: Rust 대체. HW AES 명령어 사용, 빠름 + 보안.

10.3 암호학적 해시

• SHA-2, SHA-3, BLAKE3: 충돌 저항, 선이미지 저항. 해시 테이블에 과함 (수십 ns vs 수 ns).

10.4 선택 가이드

Rust 에서는 BuildHasher 를 커스텀하여 바꿈. Go 는 불가능 (표준 해시 고정).

11. 동시성 — Concurrent Hash Table

11.1 Java ConcurrentHashMap

Java 8 의 구현:

• CAS 기반 lock-free read.
• Segment per bucket 이 아닌 bin-level lock (fine-grained).
• TreeBin 은 synchronized.

거대한 맵에서도 수천 스레드 동시 접근 가능.

11.2 Go sync.Map

Go 표준. 설계 의도: "읽기 많음, 쓰기 드묾" 시나리오 전용.

• 두 개의 맵 (read-only atomic map + dirty map) 운용.
• 일반 map + RWMutex 보다 빠를 수 있음 (제한적).
• 동시성 시나리오가 맞지 않으면 오히려 느림.

11.3 DashMap (Rust)

샤딩 기반: 내부적으로 N개 샤드, 각 샤드가 별도 RwLock. 키 해시로 샤드 선택. Arc<Mutex<HashMap>> 보다 훨씬 빠름.

11.4 Lock-free 진정판

• Cliff Click 의 NonBlockingHashMap: 완전 lock-free, 복잡함.
• Folly ConcurrentHashMap (Facebook): SIMD + CAS.

12. 실전 튜닝 포인트

12.1 예상 크기 미리 알려주기

Map<String, Integer> map = new HashMap<>(expectedSize, 0.75f);
// resize 5-6회 대신 초기부터 적절한 크기

let mut map = HashMap::with_capacity(1000);

# Python 은 직접 api 없음, dict comprehension 이 유사
d = dict.fromkeys(keys, 0)

12.2 해시 가능한 키 설계

• equals 와 hashCode 일관성: equals 가 같다면 hashCode 도 같아야.
• immutable key: 키 해시가 변하면 조회 실패.
• 균등 분포: int 타입을 바로 hashCode() 로 쓰면 하위 비트 편향 → Java 의 재섞기가 이 때문.

12.3 커스텀 해시

성능 병목이면 기본 해시 교체:

use fxhash::FxBuildHasher;
type FastMap<K, V> = HashMap<K, V, FxBuildHasher>;

단, 외부 입력 키 면 보안 해시 유지.

12.4 해시 vs BTreeMap

정렬 필요 / 범위 조회 / 매우 작은 데이터면 B-Tree 기반이 더 나을 수 있음:

• 캐시 지역성.
• 정렬 자동.
• Rust BTreeMap, C++ std::map.

12.5 프로파일링

- Java: JProfiler, async-profiler + flame graph
- Python: yappi, py-spy
- Rust: flamegraph, perf

"해시 계산이 CPU 의 X%" 를 측정. 5% 이하면 해시 함수는 병목 아님.

13. 마치며 — 간단해 보이는 자료구조의 깊이

hashmap.get("key") 한 줄 뒤에는:

• 1953년 Luhn 의 IBM 메모 (최초 해시 아이디어).
• 1957년 Peterson 의 오픈 어드레싱.
• 1986년 Celis 의 Robin Hood.
• 2003년 Crosby & Wallach 의 hash flooding 경고.
• 2012년 SipHash.
• 2017년 Google Swiss Table.
• 2024년 Go 1.24 의 Swiss Table 채택.

70년 연구의 결정체가 매 조회에 작동한다. 다른 언어에서 다른 구현을 쓰는 이유는 다음과 같다:

• Java: 하위 호환 + 트리 폴백.
• C++: 표준의 iterator stability 제약.
• Python: compact + ordered + SipHash.
• Rust: 보안 최우선 + Swiss Table.
• Go: 단순성 → 성능으로.

각각 다른 가치관을 담고 있다.

다음 글에서는 가비지 컬렉션 알고리즘 — mark-and-sweep 에서 ZGC 의 1ms 일시정지까지 — 를 파볼 예정이다. 왜 Java 의 GC 튜닝이 매번 복잡한지, Go 가 왜 긴 시간 STW 를 견뎌왔다가 현대 GC 로 전환했는지, V8 의 generational 철학이 어떻게 실제 앱 성능에 영향을 주는지.

참고 자료

• Donald Knuth — "The Art of Computer Programming, Volume 3" (해시 테이블 고전).
• Celis, Larson, Munro — "Robin Hood Hashing" (SWAT 1986).
• Crosby & Wallach — "Denial of Service via Algorithmic Complexity Attacks" (USENIX Security 2003).
• Aumasson & Bernstein — "SipHash: a fast short-input PRF" (INDOCRYPT 2012).
• Matt Kulukundis — "Designing a Fast, Efficient, Cache-friendly Hash Table, Step by Step" (CppCon 2017).
• Abseil design notes: https://abseil.io/about/design/swisstables
• Rust hashbrown design: https://github.com/rust-lang/hashbrown
• Go 1.24 map release notes.
• Raymond Hettinger — "Compact Dicts" Python 제안 이메일 (2012).
• "Performance Engineering of Software Systems" (MIT 6.172) — Hash Table 렉처.