해시는 빠르지만 충돌 처리 정책까지 설계해야 한다
키를 버킷 번호로 바꾼 뒤, 같은 버킷에 몰릴 때의 저장 규칙이 성능을 결정한다.
key"apple" 같은 입력 키를 받는다.
→
hash % buckets항상 같은 버킷 인덱스를 계산한다.
→
bucket같은 위치에 여러 키가 오면 충돌이다.
Chaining버킷 안 리스트로 이어 붙인다. 삭제가 비교적 단순하다.
Open Addressing다음 빈 슬롯을 탐사한다. 삭제 표식과 군집을 관리해야 한다.
Rehash부하율이 커지면 버킷 수를 늘려 충돌 비용을 낮춘다.
판단 기준: 충돌이 몰리는 입력, 삭제 빈도, 부하율 임계값을 함께 봐야 평균 O(1)을 유지할 수 있다.