Hash Tables & Collision Strategies

1. Overview

해시 테이블과 충돌 전략(Hash Tables & Collision Strategies)은 어떤 키(Key)를 던지더라도 O(1) 평균 시간에 그 값(Value)을 꺼내는, 현대 소프트웨어 시스템에서 가장 광범위하게 쓰이는 자료구조의 내부 엔진을 해부합니다.

학습자는 키를 배열 인덱스로 변환하는 **해시 함수(Hash Function)의 설계 원칙(균등 분포, 눈사태 효과)**을 뜯어봅니다. 나아가 두 개의 키가 같은 인덱스로 충돌할 때 버킷(Bucket)을 연결 리스트로 연결하는 **분리 연쇄(Separate Chaining)**와, 충돌 시 빈 슬롯을 탐색하는 **개방 주소법(Open Addressing, Linear/Quadratic/Double Hashing)**의 메모리 물리학을 해부하여, Python dict, Java HashMap, Redis 내부 해시 테이블의 실제 동작을 통달하는 역량을 확보합니다.

2. Scope & Boundaries

In-Scope

• 해시 함수 설계 (Hash Function Design): 나눗셈법(Division Method), 곱셈법(Multiplication Method), 암호학적 해시(SHA-256, 비역가능성), 눈사태 효과(Avalanche Effect), MurmurHash/xxHash.
• 충돌 해결 (Collision Resolution): 분리 연쇄(Separate Chaining, 연결 리스트/RB Tree), 개방 주소법(Linear/Quadratic Probing, Double Hashing).
• 부하 계수와 재해시 (Load Factor & Rehashing): 부하 계수(α = n/m), Java HashMap α=0.75 임계값, 재해시(Rehashing) 분할 상환 O(1).
• 현대 해시맵 최적화 (Modern HashMap Internals): Python dict 오픈 어드레싱, Java 8+ HashMap 충돌 많으면 체인 → RB Tree 전환, Robin Hood Hashing.

Out-of-Scope

• 암호학 해시 함수의 보안 응용: MD5 취약점, SHA 패밀리의 충돌 저항성(Collision Resistance) $\rightarrow$ 07. Security Engineering 영역.
• 블룸 필터(Bloom Filter): 해시를 이용한 확률적 자료구조 $\rightarrow$ 04-02-04. Probabilistic Data Structures 영역.

Boundaries

• Hash Table vs. BST (Ordered Map): 해시 테이블은 O(1) 평균 탐색이지만 키의 순서(Order)를 보존하지 않아 "a" ~ "z" 범위 탐색이 O(n)입니다. BST/RB Tree(std::map)는 O(log n) 탐색이지만 In-order 순서를 보장하여 범위 탐색이 O(log n + k)입니다. 순서/범위 쿼리가 없으면 해시 테이블, 있으면 BST를 선택합니다.

3. Counterexample

• 해시 함수 편향과 모든 충돌 (Hash Bias Attack): 나쁜 해시 함수 h(k) = k % 10을 써서 키가 [10, 20, 30, 40, 50]이라면 모두 같은 버킷(0번)에 충돌하여, O(1) 탐색이 O(n) 선형 탐색으로 퇴화합니다. 더 심각하게는 공격자가 해시 함수를 알고 의도적으로 모든 키를 같은 버킷으로 보내는 **해시 충돌 DoS 공격(Hash Flooding Attack)**이 가능합니다. Python 2 이전 버전의 해시 함수 취약점이 이를 이용했습니다. 솔트(Salt)를 넣은 해시(SipHash-1-3, Python 3 기본)로 대응해야 합니다.
• 부하 계수 무시와 체인 붕괴 (Load Factor Neglect): Java HashMap을 new HashMap(16) 고정 버킷 크기로 만들고 10만 개의 키를 삽입하는 코드. 부하 계수(n/m)가 6250에 달하면 각 버킷의 체인 길이가 평균 6250으로 폭증해 탐색이 O(6250) = O(n/m) 선형 탐색으로 퇴화합니다. Java HashMap의 기본 설정(initialCapacity=16, loadFactor=0.75)을 무시하고 자동 재해시를 막는 이 코드는 의도치 않은 O(n) 탐색 성능 파괴를 낳습니다.

4. Prerequisites

• 배열과 모듈러 연산 (Basic): 해시 함수가 키를 h(k) = k % m 형태로 배열 인덱스로 변환하는 기초 산술이 필요합니다. (04-01-01 Arrays)
• 연결 리스트 (Recommended): 분리 연쇄(Separate Chaining)에서 각 버킷이 연결 리스트로 구성되는 내부 구조 이해가 필요합니다. (04-01-02 Linked Lists)

5. Learning Map

6. Learning Topics

Basic

Core Topic 01: 키를 인덱스로 변환하는 주문, 해시 함수 설계 (Hash Function Physics)

• Why to Learn: 해시 함수의 품질(균등 분포, 빠른 계산, 눈사태 효과)이 해시 테이블 성능의 80%를 결정하므로, 좋은 함수와 나쁜 함수의 차이를 설계 원칙 수준에서 꿰기 위함입니다.
• What to Learn:
  • Concepts: 균등 분포(Uniform Distribution), 눈사태 효과(Avalanche Effect), 나눗셈법(h=k%m, m은 소수), 곱셈법(h=floor(m*(k*A mod 1)), A≈0.618).
  • Skills: 버킷 수(m)을 소수로 선택하는 이유, 문자열 해시(Polynomial Rolling Hash).
  • Tools: Python hash(), Java Object.hashCode().
• How to Learn:
  • 1단계: 나쁜 해시: h(k) = k % 100. 키가 100의 배수면 모두 버킷 0에 충돌. 좋은 해시: m을 97(소수)로 h(k) = k % 97. 소수를 쓰면 키가 m의 배수일 때 집중 현상을 방어하는 이유(소수와 임의 수의 최대공약수=1)를 해부합니다.
  • 2단계: 문자열 해시: h("abc") = (97*31² + 98*31¹ + 99*31⁰) % m. 다항식 롤링 해시에서 31(소수)을 기저로 쓰면 "abc"와 "bac" 같은 애너그램이 다른 해시값을 가지는 눈사태 효과를 뜯어봅니다.
• Implement: 파이썬 poly_hash(s, base=31, mod=10**9+7) 구현. "abc", "bac", "cab" 의 해시값이 모두 다름을 증명. h(k) = k % 100 (나쁜 함수)와 h(k) = k % 97 (좋은 함수)로 [100, 200, 300, 97, 194] 키 분포 비교 출력.

Recommended

Core Topic 02: 충돌 버킷의 리스트 연장, 분리 연쇄 (Separate Chaining)

• Why to Learn: 대부분의 고급 언어(Java HashMap, Python 3.6 이전 dict)의 기본 충돌 해결 방식인 분리 연쇄의 내부 메모리 구조와, 부하 계수(Load Factor) α=0.75 임계값의 수학적 근거를 장악하기 위함입니다.
• What to Learn:
  • Concepts: 버킷(Bucket) 배열, 체인(Chain = 연결 리스트), 부하 계수(α=n/m), 탐색 O(1+α), 재해시(Rehashing) 분할 상환 O(1).
  • Skills: 재해시 시 모든 키를 새 테이블에 재삽입하는 비용 분석, 최악 케이스(모든 키 동일 버킷).
  • Tools: Java HashMap 소스 코드 분석.
• How to Learn:
  • 1단계: 버킷 수 m=5, 키 [11, 22, 3, 44, 55, 16] 삽입. 11%5=1, 22%5=2, 3%5=3, 44%5=4, 55%5=0, 16%5=1(11과 충돌). 버킷 1에 [11→16] 체인이 생기는 Chaining 역학을 해부합니다.
  • 2단계: 재해시 트리거: n/m > 0.75가 되는 순간, m을 2배로 늘린 새 테이블을 만들어 모든 키를 재삽입. 이 재해시 비용이 O(n)이지만 분할 상환으로 1회 삽입 평균 비용이 O(1)로 수렴하는 수학을 뜯어봅니다.
• Implement: 파이썬 HashTable 클래스(Separate Chaining). _bucket_size=8, _load_factor=0.75 기본값. put(k,v), get(k), delete(k) + _rehash() 구현. 100개 삽입 후 _bucket_size가 자동으로 팽창하는 과정 로그와, get() 성공/실패 케이스 검증.

Practical

Core Topic 03: 빈 방 찾기의 물리학, 개방 주소법 (Open Addressing)

• Why to Learn: 파이썬 3.6+ dict와 std::unordered_map 일부 구현에서 채택한 개방 주소법의 캐시 지역성 장점과, 군집화(Clustering) 문제, 삭제 시 "묘비(Tombstone)" 처리의 필요성을 꿰기 위함입니다.
• What to Learn:
  • Concepts: 선형 탐색(Linear Probing, 1차 군집화), 이차 탐색(Quadratic Probing, 2차 군집화), 이중 해시(Double Hashing), 삭제 묘비(Tombstone).
  • Skills: 탐색 시 묘비를 건너뛰고 계속 탐색, 삽입 시 묘비 자리 재사용.
  • Tools: Python dict 내부 오픈 어드레싱 구조.
• How to Learn:
  • 1단계: Linear Probing 군집화: 버킷 5번이 꽉 차면 6번을 시도, 6번도 꽉 차면 7번...처럼 선형으로 탐색하는 Linear Probing. 연속적으로 꽉 찬 슬롯들(Cluster)이 커질수록 다음 삽입이 더 긴 탐색을 하는 1차 군집화(Primary Clustering) 문제를 해부합니다.
  • 2단계: 삭제 묘비: Linear Probing에서 중간 슬롯을 그냥 비우면, 그 뒤 슬롯들을 탐색할 때 빈 슬롯을 만나 "없다"고 오판합니다. 삭제된 슬롯에 DELETED 묘비(Tombstone) 마커를 남겨 탐색을 계속하게 하는 역학을 뜯어봅니다.
• Implement: 파이썬 OpenAddressHashTable 클래스(Linear Probing). EMPTY=None, DELETED="TOMBSTONE_DELETED" 상수. put(k,v): 충돌 시 (h(k)+i) % m 탐색. get(k): DELETED 건너뜀, EMPTY에서 탐색 종료. delete(k): DELETED 마커 설치. 삽입→삭제→조회 시나리오로 묘비 없이 오판 vs 묘비 있어 정확 탐색 비교 증명.

Advanced

Core Topic 04: 부자 살리고 빈자 채우기, 현대 해시맵 최적화 (Modern HashMap & Robin Hood)

• Why to Learn: Java 8의 HashMap이 충돌 많은 버킷에서 O(n) 체인 탐색 지옥을 탈출하기 위해 자동으로 RB Tree로 전환하는 하이브리드 설계와, 탐색 분산의 극한을 달성하는 Robin Hood Hashing의 현대 실무 최적화를 장악하기 위해서입니다.
• What to Learn:
  • Concepts: Java 8 HashMap 체인 → RB Tree 전환(버킷 크기 8 임계값), Robin Hood Hashing(빈자 자리에 부자 위치 기부), 오픈 어드레싱의 변위(Displacement) 균등화.
  • Skills: 해시 테이블 성능 프로파일링, 충돌 분포 분석.
  • Tools: Java HashMap 소스코드 TREEIFY_THRESHOLD=8.
• How to Learn:
  • 1단계: Java 8 RB Tree 전환: 같은 버킷의 체인 길이가 8을 넘으면 자동으로 연결 리스트를 RB 트리로 교체. 이후 해당 버킷의 탐색이 O(n)에서 O(log n)으로 개선되고, 체인이 6 이하로 줄어들면 다시 리스트로 전환(Untreeify)하는 하이브리드 전략을 해부합니다.
  • 2단계: Robin Hood Hashing: 새 키 삽입 시, 현재 슬롯의 기존 키보다 내가 더 먼 곳에서 왔다면(Displacement 비교) 기존 키를 쫓아내고 내가 차지합니다(부자는 가까운 자리, 빈자는 먼 자리 원칙). 이를 통해 최대 변위 분산이 균등해져 탐색 최악 케이스를 단축하는 역학을 뜯어봅니다.
• Implement: RobinHoodHashTable 파이썬 클래스. _displacement(key, slot) = 현재 슬롯이 key의 원래 해시 버킷에서 얼마나 멀리 왔는지 계산. 삽입 시 현재 슬롯 원소의 displacement < 새 원소 displacement면 교체 + 밀려난 원소 재삽입. 일반 Linear Probing과 Robin Hood의 탐색 시 평균/최대 프로브 횟수 비교 로그 출력.

7. Terminology

8. References

Primary

• [P2] SWEBOK v4.0 - Computing Foundations / Data Structures (Hash) — Structural basics.
• [P1] CS2023 - SDF/Fundamental Data Structures (Hashing) — Core requirements.

Secondary

• [Introduction to Algorithms (CLRS)] Cormen — Hashing and probe analysis.
• [The Art of Computer Programming, Vol 3] Knuth — Search and hashing depth.

Industry

• [Google: MurmurHash & CityHash] — High-performance industry hash functions.
• [Java Docs: HashMap Internals (Bins and Trees)] — Real-world resizing strategy.

9. Final Checklist

Primary

• 특정 키 값으로부터 고정된 배열 인덱스를 도출하는 '해시 연산'의 물리적 결정론을 설명 가능한가? (P1)
• '충돌(Collision)'이 발생했을 때 데이터가 소실되지 않고 물리적으로 보존되는 '해결 회로'를 입증할 수 있는 가? (P1)

Secondary

• 해시 테이블의 성능이 $O(1)$에서 $O(n)$으로 퇴화하는 물리적 임계 상황(Load factor/Bad hash)을 수리적으로 소통 가능한가?
• '체이닝' 방식이 '선형 조사법'보다 메모리 낭비는 심하지만 왜 삽입/삭제 로직은 더 단순한지 물리적 트레이드-오프를 도출할 수 있는 가?

Industry

• 실시간 금융 시스템 구축 시, 해시 테이블 리사이징으로 인한 'Latency Spike'를 방지하기 위한 '분할 리해싱(Incremental Rehashing)' 전략을 제안할 수 있는 가? (SFIA)
• 분산 시스템 환경에서 노드 추가/제거 시 데이터 재배치를 최소화하는 '일관된 해싱(Consistent Hashing)'의 물리적 원리를 기술할 수 있는 가?