Hash health

평균 O(1) 조건

체이닝과 오픈 어드레싱 모두 충돌이 쌓이면 탐색 길이가 늘어납니다. 삽입 수, 삭제 표식, 최대 탐사 거리를 함께 기록해야 재해싱 시점을 잡을 수 있습니다.

운영 중 같이 보는 지표

load factor 6 / 8 = 0.75

임계값을 넘기면 충돌 전이라도 버킷을 늘립니다.

tombstone ratio 2 / 8 = 0.25

삭제 표식이 많으면 빈 칸처럼 보여도 탐사 비용은 계속 남습니다.

chaining

한 버킷에만 키가 몰리면 평균 조회 시간이 빠르게 무너집니다.

probing

선형 탐사에서는 연속 점유 구간이 길어지는지 먼저 확인합니다.

rehash

버킷 수가 바뀌면 모든 키의 인덱스를 다시 계산해야 합니다.