Hash Tables & Collision Strategies

1. Overview

해시 테이블 및 충돌 전략(Hash Tables & Collision Strategies, HCS)은 이론적 한계인 $O(1)$의 검색 속도를 현실 세계에 구현하기 위한 '키-주소 사상 물리학'의 정점입니다.

데이터가 어디 있는지 하나씩 뒤지는 대신, 데이터 자체가 자신의 주소를 계산해 내게 하는 것이 해싱의 본질입니다. 학습자는 임의의 길이를 고정된 주소로 바꾸는 **해시 함수(Hash Function)**의 수학적 설계를 배웁니다. 또한, 서로 다른 두 데이터가 우연히 같은 주소를 가리키는 **물리적 충돌(Collision)**을 해결하기 위해 체인을 길게 늘어뜨리는 Chaining과, 빈방을 찾아 옆으로 이동하는 Open Addressing의 수리적 트레이드-오프를 심도 있게 다룹니다. 이를 통해 현대 검색 엔진과 데이터베이스 인덱스의 두뇌 역할을 하는 고속 저장 기술을 확보합니다.

2. Scope & Boundaries

In-Scope

• Hash Function Design: 균등 분산(Uniform distribution)을 위한 수학적 기법과 결정론적 물리 속성
• Collision Resolution Methods: Separate Chaining vs. Linear/Quadratic Probing vs. Double Hashing
• Load Factor Physics: 테이블이 찰수록 급격히 떨어지는 성능 지표($\alpha$)와 동적 리사이징(Rehashing)
• Hash Map/Set ADT: 해싱을 이용한 고수준 집합 및 사전 자료구조의 수리 모델

Out-of-Scope

• 암호화용 해시 알고리즘(SHA, MD5)의 상세 복잡도 (10-02-XX 암호학 영역으로 위임)
• 특정 언어 라이브러리의 해시 테이블 내부 소스 코드 구현 상세

Boundaries

• HCS vs. BST: 둘 다 검색을 다루지만, BST가 '순서 보존 검색'에 집중한다면 HCS는 순서를 포기하고 '즉각적 접근($O(1)$)'에만 모든 물리 역량을 집중하여 구분합니다.

3. Counterexample

• 단순히 "빠른 딕셔너리"라 설명하는 것은 HCS 학습이 아닙니다. 해시 함수의 결과가 특정 범문(Pattern)으로 쏠릴 때 왜 검색 성능이 **$O(n)$**으로 폭락하는지 'Clustering' 현상의 물리적 전개를 수리적으로 증명할 수 있어야 하며, 테이블의 **부하율(Load Factor)**이 0.7을 넘을 때 왜 메모리를 2배로 쓰더라도 리사이징을 강행해야 하는지 물리적 지연(Latency) 관점에서 입증하지 못한다면 HCS의 본질적인 리스크 관리를 놓친 것입니다.

4. Prerequisites

• Arrays, Strings & Memory Layout (Basic): 배열 인덱스 접근 기초가 필수입니다. (04-01-01 ASL)
• Linked Lists & Pointer Logic (Recommended): Chaining 구현을 위한 연결 기반 이해가 권장됩니다. (04-01-02 LPL)

5. Learning Map

1. The Mapping Formula: 무한한 입력값을 유한한 배열 주소로 비틀어 가두는 해시 수학을 익힙니다.
2. The Conflict Physics: 좁은 공간에 둘이 몰릴 때 발생하는 물리적 충돌의 필연성을 인식합니다.
3. The Buffer Strategy: 충돌한 데이터를 옆 칸에 둘지, 별도 사슬에 달지 결정하는 전략을 배웁니다.
4. Resizing the World: 데이터가 넘쳐나기 전, 땅(Table)을 넓혀 성능을 다시 $O(1)$로 수렴시키는 기술을 완성합니다.

6. Learning Topics

Basic

Core: 해시 함수의 기본 요건 (Hash Functions)

• Why to Learn: 좋은 해시 함수가 없으면 해시 테이블은 그저 무거운 배열일 뿐이기 때문입니다.
• What to Learn:
  • Determinism: 같은 키는 항상 같은 물리 주소를 뱉어야 하는 일관성
  • Efficiency: 함수 계산 자체가 $O(1)$ 내에 번개처럼 끝나야 하는 속도성
  • Collision Resistance: 우연히 주소가 겹치는 확률을 최소화하는 수학적 기하학(Modulo/Prime)
• How to Learn:
  • 무작위 문자열 100개를 직접 짠 Modulo 해시 함수에 넣어보고, 주소값이 얼마나 한쪽으로 쏠리는지 분포도 작성 실습
  • 소수(Prime Number)를 해시 테이블 크기로 썼을 때 왜 충돌이 줄어드는지 수리적 증명
• Implement: 입력 문자열의 각 문자에 특정 상수를 곱해 합산하는 기초 해시 함수(Polynomial rolling)

Recommended

Core: 폐쇄 주소법과 체이닝 (Separate Chaining)

• Why to Learn: 자바나 파이썬 등 대중적인 언어들이 물리적 충돌을 처리하는 가장 유연한 방식이기 때문입니다.
• What to Learn:
  • Bucket Array: 각 주소가 데이터 자체가 아닌 '리스트의 시작점'이 되는 구조
  • List Insertion Physics: 충돌 시 리스트의 맨 앞에 붙여 $O(1)$ 삽입을 유지하는 법
  • Performance Decay: 한 바구니에 사슬이 너무 길어질 때 발생하는 검색 지연 분석
• How to Learn:
  • 10개의 주소를 가진 테이블에 50개의 데이터를 체이닝 방식으로 넣으며, 평균 사슬 길이와 지연 시간의 관계 도출 실습
  • 체이닝 구조에서 데이터를 삭제할 때의 포인터 끊기 물리 시퀀스 추적
• Implement: 이중 연결 리스트를 버킷으로 사용하는 충실한 ChainedHashTable

Practical

Core: 개방 주소법과 조사 전략 (Open Addressing)

• Why to Learn: 캐시 지역성을 극대화하여 실제 하드웨어에서 체이닝보다 더 빠른 속도를 내기 위해서입니다.
• What to Learn:
  • Linear Probing: 충돌 시 바로 옆 빈방으로 $1, 2, 3..$ 순차적으로 이동하는 물리 경로
  • Primary Clustering: 데이터들이 특정 구역에 뭉쳐서 눈덩이처럼 충돌이 커지는 현상
  • Quadratic & Double Hashing: 뭉침을 방지하기 위해 이동 거리를 제곱으로 늘리거나 제2의 해시를 쓰는 기법
• How to Learn:
  • Linear Probing 테이블에서 중간 데이터를 지웠을 때 발생하는 '연결 끊김(Gap)' 오류를 직접 재현하고 더미(Delete marker)의 물리적 필요성 인식 실습
  • $0.5$ 이상의 부하율에서 Linear Probing의 실패 횟수 급증 현상 실계산
• Implement: 보조 해시 함수를 이용해 충돌을 피하는 DoubleHashingTable

Advanced

Core: 동적 리사이징과 완벽한 해싱 (Advanced Hashing)

• Why to Learn: 데이터가 수억 개로 불어나도 처음의 속도를 물리적으로 유지하는 시스템을 만들기 위함입니다.
• What to Learn:
  • Rehashing Physics: 새 테이블 할당 후 모든 기존 데이터를 새로운 주소로 다시 상장(Mapping)하는 무거운 연산
  • Perfect Hashing: 데이터 집합을 미리 알 때 충돌이 $0$이 되도록 함수를 2단계로 층 쌓기(Two-level) 하는 법
  • Cuckoo Hashing: 두 개의 함수를 써서 충돌 시 기존 데이터를 다른 곳으로 쫓아내는 지능형 물리 이동
• How to Learn:
  • 리사이징 시점에 발생하는 '일시적 멈춤(Latency spike)' 현상을 대용량 데이터 삽입 시나리오로 측정 실습
  • 가상 메모리 관리나 라우터 테이블에서 Perfect Hashing이 물리적으로 어떻게 응용되는지 분석
• Implement: 부하율이 0.75에 도달하면 자동으로 크기를 2배 늘리고 재배치하는 자가 확장 해시 맵

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)'의 물리적 원리를 기술할 수 있는 가?