같은 의미의 키는 같은 hash와 equality를 가진다.
해시는 위치 계산보다 충돌 이후의 관리가 핵심
키 규칙을 맞추고, 충돌 방식을 고르고, 부하율과 최악 입력을 계속 측정해야 조회 비용이 무너지지 않는다.
체이닝은 버킷 안에, 탐사는 다음 슬롯에 저장한다.
load factor와 최대 탐사 거리를 숫자로 제한한다.
편향 입력에서 긴 버킷과 클러스터링을 따로 측정한다.
Separate chaining
삭제가 많고 구현 안정성이 중요할 때 유리
긴 버킷 주의
Open addressing
연속 배열 접근이 좋지만 tombstone이 비용으로 남음
군집 주의
Rehash / reserve
삽입 수를 알면 미리 늘리고, 기준 초과 시 재배치
일괄 비용
마지막 점검
hash 계산과 같은 키 판단이 서로 모순되지 않는가.
원소 수를 알면서 확장 비용을 방치하지 않는가.
특정 패턴에서 O(n)에 가까워지는 구간을 찾았는가.
삽입 수를 알면 reserve로 재해시 비용을 줄인다.
std::unordered_map<int, int> freq;
freq.reserve(values.size());
for (int x : values) ++freq[x];