Hash Table: 해시 기반 딕셔너리

Hash Table, 해시 테이블, Hash Map, 해시 맵

정의

Hash Table 은 해시 함수로 키를 배열 인덱스에 매핑하여 평균 O(1) 삽입/탐색/삭제를 제공합니다.

충돌 해결

Chaining

각 버킷에 연결 리스트/트리 저장. 최악 O(N).

Open Addressing

• Linear probing: (h + i) mod m
• Quadratic probing: (h + i²) mod m
• Double hashing: (h1 + i·h2) mod m

Load factor ~0.5-0.7 유지, 넘으면 rehash.

언어별 구현

언어	자료형	내부
C++	unordered_map	chaining
Java	HashMap	chaining + tree (수 많으면)
Python	dict	open addressing (compact + insertion-ordered)
Go	map	chaining
Rust	HashMap	SipHash (기본), open addressing

함정

• 최악 O(N): 적대적 입력 대비 랜덤화 해시 (SipHash, aHash)
• iteration 순서: Python 3.7+ 는 삽입 순서 보장, 다른 언어는 임의

참고

• BST (정렬 필요 시 대체)
• Bloom Filter (근사 존재 확인)