해시 테이블 : 주소 지정 및 요소 제거 열기

Question

해시 테이블에서 공개 주소 지정을 이해하려고하지만 문학에서 대답하지 않은 질문이 하나 있습니다. 2 차 프로빙이 사용되는 경우 해시 테이블의 요소 삭제와 관련됩니다. 그런 다음 제거 된 요소가 센티넬 요소로 대체됩니다. 그런 다음 get() 작업은 추가 작업이 필요하다는 것을 알고 add() 메서드는 찾은 첫 번째 센티넬을 덮어 씁니다. 그러나 이미 해시 테이블에 있지만 탐색 경로의 센티넬 뒤에있는 키가있는 요소를 추가하려면 어떻게됩니까? 이미 인스턴스에있는 값을 테이블에있는 동일한 키로 덮어 쓰는 대신에 add() 메서드는 센티넬을 덮어 씁니다. 그런 다음 해시 테이블에 동일한 키가있는 여러 요소가 있습니다. 메모리가 필요하고 해시 테이블에서 요소를 제거하면 그 중 첫 번째 요소 만 제거되므로 요소가 여전히 테이블에서 발견 될 수 있습니다 (즉, 제거되지 않음).

그래서 센티널 요소를 교체하기 전에 삽입하려는 요소의 키에 대해 전체 프로빙 경로를 검색해야하는 것 같습니다. 나는 무엇인가 내려다보고 있냐? 이 문제는 실제로 어떻게 처리됩니까?

Answer 1

하지만 해시 테이블에 있지만 프로빙 경로에 감시 뒤에 이미 을하는 키 요소를 추가 할 경우 어떻게됩니까? 이미 테이블에있는 동일한 키 을 사용하여 인스턴스의 값을 덮어 쓰는 대신에 add() 메소드가 의 전치사를 덮어 씁니다.

add()

는 빈 요소를 발견까지 나중에 지적, 프로빙 경로의 감시 (들) 후 모든 요소를 ​​확인할 수 있습니다. 프로빙 경로에서 새 요소를 찾을 수없고 그 위에 센티넬 요소가있는 경우 첫 번째 센티널 슬롯을 사용하여 새 요소를 저장할 수 있습니다.

http://www.algolist.net/Data_structures/Hash_table/Open_addressing (HashMap.java)에 해시 테이블 구현이 있습니다. 그 put() 메서드는 정확하게 이것을합니다. (충돌 해결은 참조 스 니펫에서 선형 프로빙이지만 알고리즘의 관점에서 볼 때 중요한 차이는 아니라고 생각합니다.)

많은 제거 작업을 수행 한 후에는 너무 많은 감시 요소가있을 수 있습니다. 표. 이에 대한 해결책은 가끔 해시 테이블을 다시 작성하는 것입니다 (항목 수와 감시 요소 수에 따라 다름). 이 작업은 감시 요소를 제거합니다.

또 다른 접근법은 엘리먼트를 제거 할 때 프로빙 경로에서 센티널 (DELETED) 엘리먼트를 제거하는 것입니다. 실질적으로,이 경우에는 테이블에 센티넬 요소가 없습니다. 무료 및 OCCUPIED 슬롯 만 있습니다. 그것은 비쌀 수 있습니다.

그래서 하나가 감시 요소를 교체하기 전에 삽입하고자하는 요소의 키를 전체 프로빙 경로를 검색 할 필요가 있다고 보인다.

예, 그렇습니다. 빈 요소를 찾을 때까지 검색해야합니다.

이 문제는 실제로 어떻게 처리됩니까?

실제 해시 테이블 구현에 대해 너무 많이 알지 못합니다. 오픈 소스 프로젝트의 인터넷에서 많은 내용을 볼 수 있습니다.방금 Java에서 Hashtable 및 HashMap 클래스를 확인했습니다. 둘 다 열린 주소 대신 연결을 사용합니다.

Answer 2

늦게 답변을 드려 죄송합니다. 그러나 Java는 오픈 주소가있는 해시 테이블의 예가 java.util.IdentityHashMap입니다.

또한 GNU Trove Project을 사용할 수 있습니다. 그것의지도는 그것의 overview page에 설명 된대로 열려있는 해시 테이블을 모두 열려 있습니다.