리스트에서 제거해도 다른 키의 조회 경로가 유지된다.
삭제가 많으면 체이닝, 배열 성능은 오픈 어드레싱
같은 평균 O(1)이라도 삭제 방식, 캐시 지역성, 분포 편향에 따라 실패 지점이 다르다.
기준
Chaining버킷 안 리스트
Open addressing배열 안에서 이동
삭제 빈도
그냥 비우면 뒤쪽 키를 찾지 못하므로 삭제 표식이 필요하다.
메모리와 캐시
버킷별 리스트 구조 때문에 추가 메모리와 분산 접근이 생긴다.
슬롯을 연속으로 훑어 캐시 지역성이 좋을 수 있다.
편향 분포
한 버킷이 길어지면 그 버킷 조회가 선형으로 늘어난다.
연속 점유 구간이 길어져 실패 검색도 멀리 간다.
많으면 체이닝을 우선 검토한다.
중요하면 오픈 어드레싱을 검토하되 tombstone 정책을 둔다.
두 전략 모두 편향 입력과 재해시 기준이 필요하다.