개방 주소법 해시 테이블에서 삭제 표시가 누적되고 적재율도 임계값을 넘었다. 평균 탐색 시간을 회복하기 위한 조치로 가장 적절한 것은?

1. 1

   더 큰 테이블로 확장한 뒤 활성 키를 재해싱한다

   정답 근거확장 후 활성 키만 재해싱하면 적재율과 tombstone을 함께 낮춰 탐사 길이를 줄이므로 정답이다.
2. 2

   삭제 표시를 모두 일반 키로 바꾼다

   오답 이유삭제 표시를 일반 키로 바꾸면 존재하지 않는 항목이 검색 결과에 나타나고 탐사도 더 막힌다.
3. 3

   해시 함수를 제거하고 순차 검색만 한다

   오답 이유순차 검색으로 바꾸면 해시의 평균 상수 시간 장점을 포기하고 O(n) 탐색이 된다.
4. 4

   모든 충돌 키를 같은 버킷에 고정한다

   오답 이유모든 충돌 키를 같은 위치에 몰면 클러스터링이 극대화되어 탐사 비용이 악화된다.