해시 테이블에서 지연 삭제

Question

제 구현에서는 충돌 해결을 위해 선형 또는 2 차 탐색을 사용하여 지연 제거를 사용합니다. 삽입의 경우 지연 삭제 된 항목을 발견하면이를 삽입 할 항목으로 바꿉니다. 이러한 방식의 단점이나 부정확성은 무엇입니까 (선형 또는 2 차 또는 2 중 해시 충돌 해결을 위해)? 그것은 공간을 절약하지 않습니까?

Answer 1

공개 주소가 지정된 해시 테이블의 문제점은 특히 항목이 매우 동적 인 경우 성능이 시간이 지남에 따라 저하된다는 것입니다.

예를 들어 간단한 선형 조사 목록을 고려해 볼 수 있습니다. 해시 슬롯 1에서 3 회의 충돌이 발생하면 슬롯 1, 2, 3이 사용됩니다. 2가 삭제되면 슬롯 3에서 항목을 여전히 찾을 수 있도록 "전에 사용되었습니다"로 표시해야합니다. 특정 사용 패턴을 사용하면 해시 테이블이 선형 검색 시간이 점점 더 늘어나는 지점으로 저하되므로 다시 효력을 발휘하려면 값 비싼 재촉이 필요합니다.

많은 수의 항목을 삽입/삭제할 때 클로즈드 주소가 지정된 해시 테이블은 성능이 일정 해집니다. 그러나 포인터로 주변을 둘러 봐야하기 때문에 캐시 친화적이지 않습니다.

거의 일정한 키가있는 경우 공개 주소 지정으로 이동하고, 그렇지 않으면 가까운 주소의 해시 테이블을 고려하십시오.

특정 문제의 경우 뻐꾸기 해싱과 같은 다른 개념을 살펴볼 수도 있습니다.

Answer 2

선형 검색 개방형 해시 테이블에서 지연 제거를 수행 할 필요가 없습니다. 단단한 삭제는 테이블을 줄이는 일없이 일정한 시간 내에 간단히 수행 할 수 있습니다. 수년간 Wikipedia 해쉬 테이블 페이지에 의사 코드가있었습니다. 더 이상이없는 이유는 모르겠지만, 여기에 고유 주소는 때로 돌아 : Old Wikipedia Hash Table page, 여기에 사용자의 편의를 위해이 의사 코드는 다음과 심판이에도

function remove(key) 
i := find_slot(key) 
if slot[i] is unoccupied 
    return // key is not in the table 
j := i 
loop 
    j := (j+1) modulo num_slots 
    if slot[j] is unoccupied 
     exit loop 
    k := hash(slot[j].key) modulo num_slots 
    if (j > i and (k <= i or k > j)) or 
     (j < i and (k <= i and k > j)) (note 2) 
     slot[i] := slot[j] 
     i := j 
mark slot[i] as unoccupied 

있다

~ real code 페이지로 이동하십시오. 나는 이것이 삽입과 정확히 동일한 성능 특성을 가지고 있다고 생각하며 엔트리가 추가되지 않은 것처럼 테이블을 양호한 상태로 복원한다.

위의 방법은 상각 시간이 아닌 상수 시간이기 때문에이 삭제 방법은 많이 사용 된 '삭제 표시 및 간혹 모든 것을 다시 표시'보다 좋습니다. '삭제 된 항목 표시'방법에서 추가 및 삭제하는 백만 개의 항목이있는 해시 테이블이있는 경우 가끔 추가 또는 삭제하는 것이 이전 및 이후의 항목보다 백만 배 더 오래 걸릴 수 있습니다. 좋은 성능 특성.