Hash Table

키를 해시 함수로 변환하여 배열 인덱스에 매핑, 평균 O(1) 조회·삽입·삭제를 달성하는 자료구조.

핵심 메커니즘

key → hash(key) % capacity → bucket index
"name" → 1027364 % 16 → 3 → bucket[3]

해시 함수 요건: 결정론적, 균등 분포, 빠른 계산.

충돌 해결

Chaining: 버킷을 연결 리스트로. 최악 O(n), 로드 팩터 유연.

Open Addressing: 충돌 시 다음 빈 슬롯 탐색 (Linear/Quadratic/Double Hashing). 캐시 지역성 좋음.

로드 팩터 α = n / capacity
α > 0.75 → rehashing (capacity 2배 확장, 모든 원소 재삽입)

실무 함의

• Python dict, Java HashMap의 내부 구현
• 키가 가변 객체면 해시 충돌 보장 없음 → 불변 객체를 키로
• 해시 충돌 공격: 악의적 입력으로 모두 같은 버킷 → O(n) 저하 → SipHash 같은 무작위화 해시 사용

연결 노트

• ZK-Big-O-Complexity — 평균 O(1)이 최악과 다른 드문 케이스
• ZK-Consistent-Hashing — 분산 해시: 노드 추가/제거 시 최소 재분배
• ZK-LLM-Tokenization — 어휘집(Vocabulary)은 토큰↔ID 해시 테이블로 구현