해시 분산과 충돌 해결

키의 동등성 결정

hash가 같다고 같은 키는 아니며, equal 비교가 최종 판단을 맡는다.

비슷한 문자열이나 정수 패턴이 한 버킷에 몰리면 평균 성능이 떨어진다.

많은 삽입이 예상되면 reserve로 bucket 확장을 미리 잡아 iterator 무효화와 비용을 줄인다.

Separate chaining

버킷 안 리스트 충돌한 원소를 같은 버킷의 구조에 보관한다.

버킷이 길어지면 느려진다.

Open addressing

다음 빈 칸 탐색 충돌 시 다른 슬롯을 규칙적으로 찾는다.

삭제 처리와 클러스터링을 조심한다.

Reserve

재해시 감소 삽입 수를 알면 미리 버킷을 늘려 비용을 줄인다.

메모리 사용량은 늘 수 있다.

Custom key

hash와 equality 짝 사용자 정의 키는 같은 의미의 값이 같은 hash/equal 규칙을 가져야 한다.

둘 중 하나만 맞으면 안 된다.

중복 기준 두 키가 같다는 기준과 hash 계산 기준이 서로 맞는가.

대량 삽입 원소 수를 알면서 reserve 없이 반복 삽입하지 않는가.

최악 입력 특정 패턴 입력에서 충돌이 몰려 O(n)에 가까워지지 않는가.

std::unordered_map<int, int> freq;
freq.reserve(values.size());
for (int x : values) ++freq[x];