해시 테이블의 평균 O(1)이 무너지는 경우는?

키가 한 버킷으로 몰릴 때다. 평균 O(1)은 해시가 고르게 흩어진다는 전제 위의 값이다. 그 전제가 깨지면 최악 O(n)으로 간다. 완화는 충돌한 것을 어떻게 담느냐와 언제 늘리느냐 두 갈래다.

자바 HashMap은 둘을 함께 쓴다. 앞쪽은 이미 몰린 뒤의 방어고, 뒤쪽은 몰리기 전의 예방이다.

몰리는 이유는 둘이다. 해시 함수가 나빠서 자연히 겹치거나, 누군가 일부러 겹치게 만들거나. 뒤쪽이 해시 충돌 공격인데, 사용자 입력이 그대로 키가 되는 자리에서는 실제 공격 벡터가 된다.

늘리는 것 자체에도 값이 있다. 리사이즈는 모든 키를 다시 배치하므로 그 한 번이 무겁다. 분할 상환하면 평균은 O(1)이지만 평균이 지연을 보장하지는 않는다 — 응답 시간이 중요한 경로에서는 이 한 번이 튀는 지점으로 나타난다.

나머지 연산 대신 비트 마스크를 쓸 수 있어서다. 대신 하위 비트만 보게 되므로 해시를 한 번 더 섞어야 한다.