해시 테이블 조사

Question

3 가지 종류의 프로빙을 사용하여 프로젝트에 대한 해시 테이블을 구현하고 있습니다. 지금 저는 선형으로 작업하고 있습니다.

선형 프로빙의 경우 프로빙이 어떻게 작동하는지 알고 있고 강사는 스텝 크기를 1로 설정하려고 함을 암시합니다. 문제는 중복이 허용되지 않는다는 것입니다. 그래서 삽입하기 전에 값을 "검색"해야합니다. 그러나 테이블이 모든 셀이 "점유"되었거나 "삭제 된"지점에 익숙하다면 어떻게 될까요? 그런 다음 특정 키를 검색하여 테이블에 없는지 확인하려면 전체 테이블을 검색해야합니다. 즉, 검색 연산 (그리고 확장 연산, 삽입 연산)은 O (n)입니다.

그건 옳지 않은 것처럼 보이고, 나는 오해를했다고 생각합니다.

테이블이 적어도 절반은 비어 있어야하고 정의 된 수의 요소 만 조사하므로 이차 탐색과 동일한 문제가 발생하지 않아도된다는 것을 알고 있습니다. 그리고 이중 해싱의 경우, 어떻게 삽입 할 키가 존재하지 않는지 증명하기 위해 테이블을 검색해야하기 때문에 이것이 어떻게 작동하는지 잘 모르겠습니다. 그러나 세포 중 어느 것도 "결코 점유하지 않으면"검색을 중지하는 방법을 어떻게 알 수 있습니까?

So : 테이블의 모든 항목이 과거에 사용 된 열린 해싱에서 요소를 검색하기 위해 O (n) 개의 프로브가 필요합니까? (중복이 허용되지 않는 경우 삽입하십시오)?

Answer 1

선형 탐색의 이러한 측면을 잘못 이해하면 I도 마찬가지입니다. 해시 테이블이 거의 가득 차면 삽입 당 O (n) 방향으로 성능이 저하된다는 것에 동의합니다. 모든 세부 사항은 Don Knuth's 1963 analysis을 참조하십시오.

이 문제의 첫 번째 분석은 1913 년에 수학자 Ramanujan이 실제로 수행 한 것으로 놀랐습니다. 그 결과는 "선형 프로빙 해싱을위한 요소의 총 변위 즉, 건설 비용 가득 찬 테이블은 N^(3/2) 정도입니다. " (here 참조)

실제로 삽입이 느린 문제는 거의 완전 해시 테이블의 중요한 문제라고 생각하지 않습니다. 중요한 문제는 다른 삽입을 전혀 할 수없는 지점에 도달한다는 것입니다.

따라서 이론적 또는 실험적으로 리사이징을위한 최적의로드 팩터를 선택한 상태에서 해시 테이블의 실제 구현에는 해시 테이블의 크기를 조정하기위한 전략이 있어야합니다. 실험을 사용하면 선형 해싱의 성능이 클러스터를 피하는 방식으로 해시 테이블에서 항목을 균등하게 분산시키는 해시 함수의 기능에 매우 민감 할 수 있으므로 성능을 특히 중요하게 만듭니다. 테이블에 삽입 할 항목.