해시맵 내부 Deep Dive — Swiss Table, Robin Hood, Open Addressing, SIMD 완전 정복 (2025)

TL;DR

• 해시맵은 평균 O(1) 조회를 제공하는 자료구조. 모든 언어에 내장(Python dict, Java HashMap, Rust HashMap, C++ unordered_map).
• 두 가지 충돌 처리: 체이닝(각 버킷이 링크드 리스트) vs 개방 주소법(충돌 시 다음 슬롯 탐색). 현대는 개방 주소법이 대세.
• std::unordered_map은 느리다: 표준이 포인터 안정성을 요구 → 노드별 힙 할당 → 매 조회가 캐시 미스. Abseil, F14 같은 대안이 2-3배 빠름.
• Robin Hood Hashing: "부자에게서 가난한 자에게" — 탐사 거리가 긴 키가 짧은 키를 밀어냄. 분산 감소로 worst case 개선.
• Swiss Table (Google, 2017): 각 슬롯에 1바이트 control byte → SIMD로 16 슬롯을 한 명령어로 비교. Rust hashbrown, abseil flat_hash_map의 기반.
• Hopscotch: 각 키가 고정 범위(hop range) 내에 있어야 함. 삭제가 간단, 캐시 친화적.
• Cuckoo Hashing: 두 해시 함수, 두 테이블. O(1) worst case lookup.
• 해시 함수: SipHash(안전, 기본), xxHash/wyhash(빠름, 안전 아님), FNV/Murmur(레거시).
• Hash flooding DDoS: 동일 해시 값으로 공격자가 최악 케이스 유발. SipHash + random key로 방어.

1. 해시맵의 기본

1.1 인터페이스

insert(key, value)
lookup(key) → value or not_found
delete(key)

대부분 언어의 Map, Dict, HashMap, unordered_map의 공통 API.

1.2 목표

• 평균 O(1) 시간 복잡도.
• 메모리 효율.
• 캐시 친화적.
• worst case 예측 가능.

이상적으론 O(1)이지만 실제론 해시 함수, 충돌, 캐시, 메모리 할당이 모두 성능에 영향.

1.3 기본 구조

Hash Function
  key → int

Hash Table (array)
  ┌────┬────┬────┬────┬────┬────┬────┐
  │    │ A  │    │ B  │    │ C  │    │
  └────┴────┴────┴────┴────┴────┴────┘
    0    1    2    3    4    5    6

해시 함수로 키를 정수로 변환, 테이블 크기로 mod 해서 인덱스. 그 위치에 값 저장.

1.4 충돌

두 키가 같은 인덱스로:

hash("apple") % 7 = 3
hash("grape") % 7 = 3  → 충돌!

이것을 어떻게 처리하느냐가 해시맵 설계의 핵심.

1.5 Load Factor

load_factor = num_entries / num_slots

• 0.5: 여유, 빠르지만 메모리 낭비.
• 0.75: 일반적 (Java 기본).
• 0.9+: 빡빡, 충돌 많음.

Load factor가 threshold를 넘으면 rehash — 더 큰 테이블로 재구성.

2. 체이닝 (Separate Chaining)

2.1 구조

각 슬롯이 링크드 리스트:

Slot 0: → null
Slot 1: → (apple, 1) → (crane, 3) → null
Slot 2: → (bat, 2) → null
Slot 3: → null

충돌 시 그 슬롯의 리스트 끝에 append.

2.2 동작

Insert:

1. 해시 계산.
2. 슬롯 찾기.
3. 리스트 끝에 append.

Lookup:

1. 해시 계산.
2. 슬롯의 리스트 순회하며 키 비교.

Delete:

1. 해시 계산.
2. 리스트에서 노드 찾아 제거.

2.3 장점

• 구현 단순.
• 삭제 용이 (노드 하나만 떼어냄).
• Load factor 1 초과 가능 — 단지 리스트가 길어짐.
• 포인터 안정성: 노드는 메모리에 고정 → 외부 포인터 유효.

2.4 단점

• 캐시 미스: 매 lookup이 리스트 순회 → 각 노드가 힙에 분산 → 캐시 line 충돌.
• 메모리 오버헤드: 노드마다 next 포인터 (8 바이트).
• 할당 비용: 매 insert가 malloc.

2.5 std::unordered_map

C++ 표준이 강제하는 "레퍼런스 안정성"(반복자 무효화 제한) → 체이닝 기반 구현 강제 → 느림.

실측: abseil flat_hash_map (open addressing)이 2-3배 빠름.

GCC/Clang의 std::unordered_map은 역사적 유물에 가깝다.

2.6 Java HashMap

Java는 체이닝 기본이지만 개선:

• 한 슬롯의 체인이 8개 이상이 되면 red-black tree로 전환.
• 공격자가 의도적으로 충돌을 만들어도 최악 O(log n) 보장.
• Java 8(2014) 도입.

3. 개방 주소법 (Open Addressing)

3.1 아이디어

"충돌 시 같은 배열 내 다른 슬롯을 찾아 넣는다."

포인터 없음. 모든 것이 배열에.

3.2 Linear Probing

hash(key) = i
if slot[i] is empty: 넣기
else: slot[i+1], slot[i+2], ... 차례로 확인

hash("apple") = 3

Slot: 0 1 2 3 4 5 6
      . . . A . . .

hash("grape") = 3  → slot 3 full
              → try slot 4 → empty → 넣기

Slot: 0 1 2 3 4 5 6
      . . . A G . .

3.3 장점

• 캐시 친화: 인접 슬롯이 같은 캐시 라인.
• 메모리 효율: 포인터 없음, 오버헤드 적음.
• 빠른 insert/lookup (load factor 낮을 때).

3.4 단점

• Primary clustering: 연속된 채워진 슬롯들이 더 자라는 경향. 긴 probing 체인.
• Delete 어려움: 빈 슬롯을 만들면 이후 탐사 중단 → 데이터 손실. Tombstone 또는 재배치 필요.
• Load factor 1 초과 불가: 배열이 차면 rehash 필수.

3.5 Quadratic Probing

Linear 대신 제곱 step:

slot[i], slot[i+1], slot[i+4], slot[i+9], slot[i+16], ...

Primary clustering 완화. 하지만 secondary clustering 발생 (같은 초기 슬롯의 키들이 같은 경로).

Python dict의 초기 구현이 유사한 기법.

3.6 Double Hashing

두 해시 함수 h1, h2:

slot[i], slot[i + h2(k)], slot[i + 2*h2(k)], ...

h2(k)가 키마다 달라서 clustering 거의 없음. 하지만 각 probe가 서로 다른 위치 → 캐시 미스.

4. Robin Hood Hashing

4.1 문제 정의

Linear probing의 문제: 탐사 거리의 분산이 크다.

일부 키는 제 자리에서 찾음 (distance 0), 다른 키는 수십 슬롯 떨어져 있음. 평균은 O(1)이지만 P99가 나쁘다.

4.2 아이디어

"부자에서 가난한 자로" — 탐사 거리가 긴 키(부자)가 짧은 키(가난한 자)를 밀어내어 자기 자리 차지.

insert("grape") — hash→3, 거리 0으로 원함
slot[3] has "apple" — 거리 0 (부자)
grape가 linear probe
slot[4] has "banana" — 거리 2 (더 부자!)
→ grape가 banana를 밀어내고 slot[4] 차지
→ banana가 다시 probe 시작 (거리 3부터)
...

4.3 효과

전체 작업량은 같지만 탐사 거리의 분산이 극적으로 감소. 모든 키가 비슷한 거리를 가짐.

결과:

• P99 lookup이 예측 가능.
• 빠른 미싱 감지 — 탐사 중 현재 distance보다 가난한 슬롯을 만나면 즉시 "없음" 반환.

4.4 구현

각 슬롯이 probe distance를 기록:

struct Slot {
    Key key;
    Value value;
    u8 distance;   // 본래 위치에서 얼마나 멀리
};

Insert 알고리즘:

probe_distance = 0
while True:
    slot = table[index]
    if slot.empty: slot = (key, value, probe_distance); return
    if slot.distance < probe_distance:
        swap(slot, (key, value, probe_distance))
    index = (index + 1) % table_size
    probe_distance += 1

4.5 성능

• Insert: 평균 O(1), 하지만 일부 swap 발생.
• Lookup: 평균 O(1). 탐사 중 current_dist > slot.dist면 즉시 없음(miss 속도 ↑).
• P99 개선: linear의 최대 10+ probe에서 Robin Hood는 3-5.

4.6 사용

• 많은 현대 해시맵이 변형을 사용.
• Rust의 hashbrown (내부 std)은 Swiss Table + Robin Hood idea.
• Emil Mikulas의 tsl::robin_map (C++).

5. Hopscotch Hashing

5.1 아이디어

각 키는 자신의 원래 해시 슬롯에서 H개 이내의 슬롯에 있어야 한다 (H = 4 또는 8).

H = 4
hash(k) = i

k는 slot[i], slot[i+1], slot[i+2], 또는 slot[i+3] 중 하나에만 존재 가능.

각 슬롯에 hop information (bitmap)을 저장: "내 원래 슬롯의 이웃 중 어디에 있는지".

5.2 Insert

1. Linear probe로 빈 슬롯 찾기.
2. 그 슬롯이 원래 위치에서 H 이내면 그대로.
3. H 이상 떨어져 있으면 백트래킹: 가까운 슬롯의 키를 뒤로 밀어내서 공간 확보.

5.3 Lookup

원래 슬롯의 hop bitmap을 보고 H개 이하만 체크. 매우 빠름 (H회 비교).

5.4 장점

• Lookup이 극도로 캐시 친화적 — H 슬롯만 체크, 같은 캐시 라인.
• Delete가 단순.
• Worst case 제한.

5.5 단점

• 높은 load factor에서 insert 실패 가능.
• 복잡한 backtracking.

주류는 아니지만 흥미로운 설계.

6. Cuckoo Hashing

6.1 개념

두 개의 해시 함수, 두 개의 테이블 (또는 한 테이블의 두 위치):

T1[h1(k)] 또는 T2[h2(k)] 중 하나에 k

Lookup: 두 위치만 체크. Worst case O(1) 보장.

6.2 Insert

1. T1[h1(k)]가 비어있으면 넣기.
2. 차 있으면 기존 키를 밀어내고 그 위치 차지.
3. 밀려난 키는 자신의 다른 해시 위치로 이동 시도.
4. 또 다른 키를 밀어냄.
5. 반복... 체인이 너무 길면 rehash.

"뻐꾸기(Cuckoo)"는 다른 새의 알을 밀어내는 행동에서 유래.

6.3 특성

• Lookup O(1) worst case: 두 위치만.
• Insert 기대 O(1): 가끔 긴 체인.
• Load factor ~0.5 제한: 넘으면 rehash 빈번.
• Concurrent 친화적: 두 독립 테이블.

6.4 응용

• BPF maps (Linux kernel의 hash type).
• 데이터베이스 인덱스 일부.
• Cuckoo filter (Bloom filter 대안).

7. Swiss Table — Google의 혁명

7.1 배경

Google이 2017년 CppCon에서 발표. Matt Kulukundis의 talk: "Designing a Fast, Efficient, Cache-friendly Hash Table".

목표: abseil의 flat_hash_map — std::unordered_map의 대체.

7.2 핵심 아이디어

1. Open addressing with linear probing. 2. 각 슬롯에 1바이트 metadata (control byte). 3. SIMD로 16 control bytes 동시 비교.

7.3 Control Byte

각 슬롯은 두 부분:

• Data: (key, value) pair.
• Control byte (1 byte):
  • 0x80 (bit 7 set): 비어 있음 또는 deleted.
  • 0x00-0x7F (bit 7 clear): 해시의 top 7 bits.

7.4 Group

슬롯들을 16개씩 그룹화. 각 그룹의 16 control bytes가 연속 메모리.

┌──────────────────────────────────────┐
│ 16 Control Bytes (16 bytes)          │
├──────────────────────────────────────┤
│ 16 Entries (key-value pairs)         │
└──────────────────────────────────────┘

7.5 SIMD Lookup

Lookup 과정:

1. hash(key) 계산.
2. 상위 57 bits로 그룹 index.
3. 하위 7 bits로 control byte와 비교할 값 (h2).
4. 해당 그룹의 16 control bytes 로드.
5. SSE2 _mm_cmpeq_epi8: 16 bytes와 h2를 한 번에 비교 → 16-bit mask.
6. Mask에서 1인 비트만 체크 (보통 1-2개).
7. 해당 슬롯의 key와 실제 비교.

// C++ 의사코드
__m128i ctrl_group = _mm_loadu_si128((__m128i*)&ctrl[group_idx]);
__m128i h2_vec = _mm_set1_epi8(h2);
__m128i cmp = _mm_cmpeq_epi8(ctrl_group, h2_vec);
uint16_t mask = _mm_movemask_epi8(cmp);

while (mask) {
    int slot = __builtin_ctz(mask);  // 비트 위치
    if (entries[group*16 + slot].key == key) {
        return &entries[group*16 + slot].value;
    }
    mask &= mask - 1;  // 다음 bit
}

16개 슬롯을 SIMD 한 명령어로 필터링. 대부분 경우 실제 key 비교는 1회만.

7.6 삽입과 Tombstone

Insert:

1. SIMD로 empty slot 찾기 (control byte = 0x80).
2. 찾으면 삽입. Control byte를 hash의 top 7 bits로.

Delete:

1. Control byte를 0xFE (deleted marker)로.
2. Lookup 시 건너뛰되 탐사는 계속.
3. 주기적으로 rehash하면서 tombstone 제거.

7.7 성능

abseil flat_hash_map 벤치마크:

• Lookup hit: std::unordered_map 대비 2-3x 빠름.
• Lookup miss: 3-5x 빠름 (SIMD로 빠른 miss).
• Insert: 1.5-2x.
• 메모리: 약간 더 많음 (control bytes + alignment).

7.8 사용처

• abseil flat_hash_map, flat_hash_set: 공식 Google C++ 라이브러리.
• Rust hashbrown: std::collections::HashMap의 내부 (2018+).
• Google 내부: 거의 모든 C++ 해시맵.
• Rocksdb, ClickHouse, DuckDB 등 이름 있는 프로젝트.

8. F14 — Facebook

8.1 배경

Facebook (Meta)의 Folly 라이브러리 일부. Nathan Bronson의 2018 작품.

목표: Swiss Table과 유사하지만 더 나은 trade-off.

8.2 아이디어

Swiss Table: 16 slots per group (SSE2). F14: 14 slots per group + 2 bytes metadata per group.

왜 14? AMD/Intel 구 CPU에서도 작동하도록 SSE2(128-bit = 16 bytes) 내에 metadata + "chunk" bitmap 포함.

8.3 구현

3가지 variant:

• F14ValueMap: 표준 open addressing.
• F14NodeMap: unordered_map 호환 (포인터 안정성).
• F14VectorMap: 벡터 같은 순서 유지.

각자 다른 use case에 최적화.

8.4 성능

Swiss Table과 비슷 또는 약간 더 빠름 (워크로드에 따라). Facebook의 서비스들이 대량 사용.

8.5 사용

• Folly: Facebook 인프라 전반.
• RocksDB 내부에 일부.

9. Rust HashMap (hashbrown)

9.1 역사

Rust 1.0 (2015): 자체 구현 HashMap. Robin Hood + SipHash. Rust 2018+: hashbrown crate (Amanieu d'Antras)로 교체. Swiss Table 기반.

9.2 hashbrown

• Swiss Table 알고리즘.
• Rust 특화 최적화.
• Zero-cost: 컴파일러 인라이닝 덕분.

9.3 해시 함수

Rust의 기본 해시: SipHash-1-3.

• 안전 (hash flooding 방어).
• 빠르지 않음 (~4 ns/hash on modern CPU).

대안 해시:

• ahash: 매우 빠름, 해시 품질 좋음.
• fxhash: rustc 내부 사용. 매우 빠름, 약함.
• fnv: 작은 키에 빠름, 품질 중간.

use rustc_hash::FxHashMap;
let mut map: FxHashMap<String, u32> = FxHashMap::default();

경고: FxHash는 untrusted input에 취약. DDoS 위험.

9.4 API

let mut scores = HashMap::new();
scores.insert("alice", 100);

if let Some(score) = scores.get("alice") {
    println!("{}", score);
}

// Entry API — 가장 idiomatic
scores.entry("bob").or_insert(0) += 1;

entry()가 RAII 스타일 mutation을 허용.

10. Python dict

10.1 진화

Python 2: 단순 open addressing. Python 3.6+ (2016): PEP 468 — insertion order 보장. 내부가 두 배열로.

10.2 현재 구조

Indices: [ -1, -1, 2, -1, 0, 1, -1, -1 ]
Entries: [ (hash_a, "alice", 100),
           (hash_b, "bob",   90),
           (hash_c, "carol", 95) ]

• Indices: 해시 → entries 배열 인덱스.
• Entries: 실제 항목, insertion order.

Lookup: 해시 → indices[i] → entries[i]. 순회는 entries를 순서대로.

이점:

• 순서 보존: 프로그래머 기대대로.
• 메모리 효율: indices만 작은 정수로 압축.
• 캐시 친화: entries는 연속.

10.3 Perturbation

충돌 시 linear probe 대신 복잡한 perturbation:

i = (5*i + 1 + perturb) % mask
perturb >>= 5

perturb가 hash의 상위 비트를 섞어서, linear probe보다 cluster 저항성 증가.

10.4 Small Dict Optimization

작은 dict (8 entries 이하)는 compact dict로 더 효율적.

10.5 Python dict 성능

"Python은 느리다"는 일반론과 달리 dict는 매우 빠름. CPython 자체의 속성 조회, 모듈 조회, 클래스 메서드 조회가 모두 dict 기반 — 성능이 인터프리터 전체에 영향.

11. 해시 함수

11.1 Non-Cryptographic

성능 중심:

• FNV-1a: 간단, 빠름. 품질 중간. 작은 키에 좋음.
• Murmur3: 좋은 품질, 빠름. 2011 표준.
• xxHash: 매우 빠름 (수 GB/s). 큰 키에 우수.
• CityHash / FarmHash: Google. 빠르고 품질 좋음.
• wyhash: 최신, xxHash 수준 속도 + 품질.

11.2 Cryptographic

• SipHash: Aumasson & Bernstein 2012. 안전 + 합리적 속도 (~1 GB/s). 해시맵 특화.
• Blake3: 매우 빠름 (~10 GB/s multi-threaded), 암호학적 안전. 일부 해시맵에서도 사용.

11.3 선택 기준

용도:

• 일반 Rust/Go HashMap: SipHash (기본). 안전.
• 알려진 입력, 고성능: ahash, xxHash, wyhash.
• 암호학: Blake3, SHA-256.

11.4 Hash Flooding DDoS

공격자가 모두 같은 해시 값으로 매핑되는 키들을 제출 → 단일 버킷에 몰림 → O(n) 성능 → CPU 소진.

예: "apple", "grape" 같은 여러 문자열이 모두 hash=0이 되도록 설계.

방어:

1. 랜덤 시드: 프로세스 시작 시 랜덤 key. SipHash + random key.
2. 안전 해시: SipHash는 key 없으면 깨기 어려움.
3. O(log n) fallback: Java HashMap이 tree로 전환.
4. Load factor 제한: 급격한 rehash로 재분산.

2011년 Java/PHP/Python이 모두 이 공격을 당함. 이후 모두 SipHash 또는 유사 기법 도입.

12. 캐시 효과

12.1 현대 CPU의 현실

• L1 cache: ~1 ns, 32 KB.
• L2 cache: ~3 ns, 256 KB.
• L3 cache: ~10 ns, 수 MB.
• Main memory: ~100 ns.

캐시 미스는 성능의 적.

12.2 Chaining의 문제

Bucket → Node1 → Node2 → Node3

각 노드가 다른 캐시 라인. Lookup 시마다:

1. Bucket 로드.
2. Node1 포인터 → 다른 캐시 라인 로드 (cache miss).
3. Node1.next → 또 다른 캐시 라인.
4. 반복.

100+ ns per lookup.

12.3 Open Addressing의 이점

Slot[i], Slot[i+1], Slot[i+2], ...

같은 캐시 라인. Linear probe는 sequential access → prefetcher 도움.

20-30 ns per lookup.

12.4 Metadata Separation

Swiss Table의 영리함: metadata를 entries와 분리.

[control bytes: 16 bytes]  ← 한 캐시 라인에 16 metadata
[entries: key-value pairs] ← 다른 캐시 라인

Miss 판별에 entries 캐시 로드 불필요. Miss가 매우 빠름.

12.5 Prefetch

큰 해시맵에서 lookup 전 prefetch:

__builtin_prefetch(&table[hash(key) % size]);
// ... 다른 작업 ...
// 이제 해당 슬롯이 캐시에 있음

연속 lookup 시 유용. 수동 최적화.

13. 벤치마크

13.1 공정 비교의 어려움

해시맵 벤치마크는 workload 의존적:

• Hit vs miss 비율.
• 키 크기 및 분포.
• Table load factor.
• Delete 빈도.
• Insertion order.

"X가 Y보다 빠르다"는 말은 context 없이 의미 없음.

13.2 대략적 순위

랜덤 integer keys, 50% hit rate, load factor 0.75:

Rank   Impl                    Lookup ns  Insert ns
1      abseil flat_hash_map         15        35
2      F14ValueMap                  16        37
3      hashbrown (Rust std)         18        40
4      tsl::robin_map               22        55
5      boost::unordered_map         25        60
6      std::unordered_map           55        90

std가 2-4배 느림. "근본부터 다르다"는 수준.

13.3 실측의 함정

• Small data: 해시 함수 오버헤드 지배 → 어떤 맵도 비슷.
• Large data: 캐시 행동이 지배 → 개방 주소법 승리.
• 복잡한 key: equality 비교 비용 증가.
• String keys: 해시가 O(length) → 다른 고려사항.

14. 실무 선택 가이드

14.1 언어별 기본

• C++: std::unordered_map 피하라. Abseil, Folly, tsl 사용.
• Rust: 기본 HashMap 충분. 보안 위험 없으면 FxHashMap 또는 ahash.
• Go: 내장 map. 내부는 Swiss Table과 유사.
• Java: HashMap 표준. 특수 상황엔 Guava ImmutableMap, Koloboke.
• Python: 내장 dict. 순서 보존 + 성능 모두 좋음.
• JavaScript: V8의 Map이 매우 빠름. 문법 그대로.

14.2 특수 상황

동시성:

• Java: ConcurrentHashMap.
• C++: folly::ConcurrentHashMap, junction 라이브러리.
• Go: sync.Map (별로), 또는 shard 해서 mutex 감싸기.
• Rust: dashmap, evmap.

불변:

• Clojure, Scala의 persistent hash map.
• Rust의 im crate.
• C++: immer.

메모리 제약:

• boost::flat_map (작은 항목 수).
• Trie 계열 (공통 prefix 있는 경우).

14.3 튜닝 팁

1. 초기 크기 힌트: HashMap::with_capacity(n) — rehash 방지.
2. Load factor 조정: 0.75가 기본, 메모리 많으면 0.5로 낮춰서 충돌 감소.
3. 해시 함수 변경: untrusted input 아니면 xxHash/FxHash로 속도 ↑.
4. Key를 hashable 자체로: String 대신 &str 또는 Cow<str>.
5. 작은 key 최적화: integer key가 string보다 훨씬 빠름.

15. 학습 리소스

논문/발표:

• "Designing a Fast, Efficient, Cache-friendly Hash Table" — Matt Kulukundis, CppCon 2017.
• "Robin Hood Hashing" — Pedro Celis, 1986 (원저).
• "Cuckoo Hashing" — Pagh & Rodler, 2001.
• "Hopscotch Hashing" — Herlihy et al., 2008.

소스 코드:

• abseil flat_hash_map.
• Rust hashbrown.
• Facebook Folly F14.
• CPython Objects/dictobject.c.

책:

• "Introduction to Algorithms" (CLRS) — 기본 이론.
• "The Art of Multiprocessor Programming" — concurrent hash maps.

블로그:

• Andreas Fredriksson: "Memory-Friendly Hash Tables".
• Malte Skarupke의 hash map 관련 포스트들.
• sdnr1 (Emil Mikulas)의 tsl 라이브러리 문서.

16. 요약 — 한 장 정리

┌─────────────────────────────────────────────────────┐
│             Hash Map Cheat Sheet                     │
├─────────────────────────────────────────────────────┤
│ 기본:                                                  │
│   Hash function + table                              │
│   Collision handling                                 │
│   Load factor                                        │
│   Resize (rehash)                                    │
│                                                       │
│ Chaining:                                             │
│   각 버킷이 linked list                                │
│   단순, delete 쉬움                                    │
│   캐시 미스 많음 ← 단점                               │
│   std::unordered_map, Java HashMap                   │
│                                                       │
│ Open Addressing:                                      │
│   충돌 시 다음 슬롯                                     │
│   Linear / Quadratic / Double                        │
│   캐시 친화                                            │
│   Delete 까다로움 (tombstone)                         │
│                                                       │
│ Robin Hood:                                           │
│   긴 distance가 짧은 distance 밀어냄                   │
│   분산 감소                                            │
│   P99 개선                                            │
│   Emil Mikulas tsl::robin_map                        │
│                                                       │
│ Hopscotch:                                            │
│   H개 이내의 이웃만                                    │
│   Hop bitmap                                         │
│   Cache 극도로 친화                                    │
│                                                       │
│ Cuckoo:                                               │
│   두 해시 함수, 두 테이블                              │
│   Lookup O(1) worst case                             │
│   Load factor ~0.5 제한                              │
│                                                       │
│ Swiss Table (Google 2017):                            │
│   Open addressing                                     │
│   16 slots per group                                 │
│   1 byte control per slot                            │
│   SIMD로 16 bytes 동시 비교                           │
│   Abseil flat_hash_map                               │
│   Rust hashbrown                                     │
│   2-3x std 성능                                      │
│                                                       │
│ F14 (Facebook):                                       │
│   14 slots + 2 byte metadata                         │
│   Swiss Table 변형                                    │
│   Folly F14ValueMap/NodeMap/VectorMap                │
│                                                       │
│ 해시 함수:                                             │
│   - SipHash: 안전, 기본 (Rust std)                    │
│   - xxHash: 매우 빠름, 안전 아님                       │
│   - FNV/Murmur: 레거시                                │
│   - ahash, wyhash: 최신 빠름                          │
│                                                       │
│ Hash Flooding:                                        │
│   공격자가 동일 hash 키 제출                           │
│   SipHash + random seed 방어                         │
│   Java는 tree fallback                               │
│                                                       │
│ 캐시:                                                  │
│   Chaining → many cache miss                         │
│   Open addressing → sequential, prefetch             │
│   Swiss Table → metadata 분리 → fast miss           │
│                                                       │
│ 언어별 기본:                                           │
│   C++: unordered_map (느림) → abseil/F14 권장         │
│   Rust: HashMap (Swiss Table)                        │
│   Go: map (Swiss Table-like)                        │
│   Python: dict (compact + order)                     │
│   Java: HashMap (chaining + tree)                    │
│                                                       │
│ 튜닝:                                                  │
│   with_capacity (rehash 방지)                        │
│   Fast hash for trusted input                        │
│   SIMD 해시맵 선택                                    │
│   Small key 우선                                     │
└─────────────────────────────────────────────────────┘

17. 퀴즈

이 글이 도움이 됐다면 다음 포스트도 확인해 보세요:

• "CPU Cache & Memory Hierarchy Performance" — 캐시 최적화의 기반.
• "Bloom Filter & Probabilistic Data Structures" — 해시 기반 다른 자료구조.
• "Consistent Hashing & Virtual Nodes" — 분산 시스템의 해시.
• "Python GIL & CPython Internals" — Python dict가 인터프리터에 미치는 영향.