Hash collision

같은 버킷에 모이면 전략이 조회 비용을 결정

해시 함수는 위치를 계산하고, 충돌 해결 정책은 같은 위치에 온 키를 다시 찾을 수 있게 저장한다.

1. key "apple", "grape"처럼 비교할 원본 키

2. hash % bucketCount 항상 같은 숫자 인덱스로 변환

0empty

1apple + grape 충돌

2kiwi

Chaining 버킷 1 안에 리스트로 이어 붙인다. 삭제 경로가 단순하다.

Open addressing 버킷 1이 차 있으면 다음 빈 슬롯을 탐사한다.

Rehash 충돌과 부하율이 커지면 버킷 수를 늘려 다시 배치한다.

판단 기준: 입력 분포, 삭제 빈도, 부하율 임계값을 함께 봐야 평균 O(1)이 실제로 유지된다.