오픈 어드레싱

오픈 어드레싱 또는 폐쇄 해싱은 해시 테이블에서 충돌 분해능의 한 방법이다.이 방법을 사용하면 대상 레코드가 발견되거나 사용되지 않는 어레이 슬롯이 발견될 때까지 어레이의 대체 위치(프로브 시퀀스)를 검색하거나 검색하여 해시 충돌이 해결되며, 이는 표에 이러한 키가 없음을 나타낸다.^[1]잘 알려진 프로브 시퀀스에는 다음이 포함된다.

선형 프로빙

프로브 간격이 고정되어 있는 경우 - 종종 1로 설정된다.

이차 프로빙

프로브 사이의 간격이 2차적으로 증가하는 경우(일반적으로, 지수는 2차 함수로 설명됨).

이중 해싱

각 레코드에 대해 프로브 간격이 고정되지만 다른 해시 함수에 의해 계산되는 경우.

이러한 방법들 간의 주요 트레이드오프들은 선형 탐색이 캐시 성능이 가장 뛰어나지만 클러스터링에 가장 민감한 반면, 이중 해싱은 캐시 성능이 낮지만 사실상 클러스터링이 없는 반면, 2차 탐구는 두 영역 모두 중간이다.이중 해싱은 또한 다른 형태의 프로빙보다 더 많은 연산이 필요할 수 있다.

홉스코치 해싱, 로빈 후드 해싱, 마지막 선착순 해싱 및 뻐꾸기 해싱과 같은 일부 오픈 어드레싱 방법은 새 키를 넣을 공간을 확보하기 위해 배열의 기존 키를 이리저리 이동시킨다.이것은 프로빙에 기초한 방법보다 더 나은 최대 검색 시간을 제공한다.^{[2][3][4][5][6]}

오픈 어드레싱 해시 테이블의 성능에 중요한 영향을 미치는 것은 부하 계수, 즉 어레이에서 사용되는 슬롯의 비율이다.부하율이 100%로 증가함에 따라 주어진 키를 찾거나 삽입하는 데 필요할 수 있는 프로브의 수가 급격하게 증가한다.테이블이 가득 차면 프로빙 알고리즘이 종료되지 않을 수도 있다.해시함수가 좋더라도 부하인자는 통상 80%로 제한된다.해시함수가 불량할 경우 특히 가장 간단한 선형 어드레싱 방법으로 상당한 클러스터링을 생성하여 매우 낮은 부하 계수에서도 성능이 저하될 수 있다.일반적으로 가장 개방적인 어드레싱 방법을 사용하는 일반적인 부하 계수는 50%인 반면, 개별 체인은 일반적으로 최대 100%까지 사용할 수 있다.

예시 유사 코드

다음은 해시함수가 좋으면 효과적인 공통 접근방식인 선형 프로빙과 단일 슬롯스텝이 있는 오픈 어드레싱 해시 테이블의 구현이다.각 조회, 설정 및 제거 기능은 공통 내부 함수 find_slot를 사용하여 지정된 키를 포함하거나 포함해야 하는 배열 슬롯을 찾는다.

레코드 쌍 { 키, 값 } var 쌍 어레이 슬롯[0..num_snum-1]

find_module(key) i := 해시(key) modulo num_num_dump // 함수 우리가 키를 찾거나 빈 슬롯을 찾을 때까지 검색한다.(점포)와 (점포[i] 중에키 ≠ 키 ) i = (i + 1) modulo num_module return i

슬롯[i]이(가) // 키가 테이블 반환 슬롯[i]에 있는 경우 함수 조회 i := find_lights(키)값이 아님 // 키가 테이블 반환에 없음: 찾을 수 없음

set(키, 값) i := find_light(키) 슬롯[i]이 사용 중인 경우 // 우리는 키 슬롯[i]을 찾았다.value = 테이블이 거의 가득 찬 경우 값 반환(주1) i = find_built(key) 슬롯[i]을 더 크게 재구성하십시오.키 = 키 슬롯[i]value = value

노트 1

테이블을 재구축하려면 더 큰 배열을 할당하고 이전 배열의 모든 요소를 새로운 더 큰 배열에 삽입하기 위해 설정된 작업을 반복적으로 사용해야 한다.예를 들어 이전 어레이 크기를 두 배로 늘려 어레이 크기를 기하급수적으로 늘리는 것이 일반적이다.

slot[i]가 비어 있는 경우 함수 제거(key) i := find_lights(key) // 키가 테이블 j := i 루프 마크 슬롯[i]이 비어 있는 r2: (주2) j : (j+1) modulo num_inits가 비어 있는 경우 := 해시[j].key) modulo num_slots         // determine if k lies cyclically in (i,j]         //      i.k.j           //  ....j i.k.  or   .k..j i...          if ( (i<=j) ? ((i<k)&&(k<=j)) : ((i<k)  (k<=j)) )             goto r2;         slot[i] := slot[j]         i := j

주2

클러스터의 모든 레코드에 대해, 자연 해시 위치와 현재 위치 사이에 빈 슬롯이 없어야 한다(엘스 룩업이 레코드를 찾기 전에 종료됨).이 시점에서, 가성 문자에서는,i클러스터의 후속 레코드에 대해 이 속성을 무효화할 수 있는 빈 슬롯. j그 이후의 기록이야 k레코드가 있는 원시 해시j충돌이 없다면 자연스럽게 해시 테이블에 착륙할 것이다.이 테스트는 다음 날짜의 기록이j이제 다음과 같이 클러스터의 필수 속성과 관련하여 유효하지 않은 위치가 지정됨i공석이다

또 다른 제거 기법은 슬롯을 삭제된 것으로 표시하는 것이다.그러나 이는 결국 삭제된 레코드를 제거하기 위해 테이블을 재구축해야 한다.위의 방법들은 O(1) 기존 기록의 갱신과 제거를 제공하며, 테이블 크기의 높은 물 표시가 커지면 때때로 재구축한다.

위의 O(1) 제거 방법은 단일 슬롯 스텝으로 선형적으로 프로빙된 해시 테이블에서만 가능하다.한 번의 작업으로 많은 레코드를 삭제해야 하는 경우, 삭제 및 추후 재구축을 위해 슬롯을 표시하는 것이 더 효율적일 수 있다.

참고 항목

• 게으른 삭제 - 열린 주소 지정을 사용하여 해시 테이블에서 삭제하는 방법.

참조