2선 해싱

2-선택 체인이라고도 하는 2-선택 해싱은 "두 개의 해시함수를 가진 해싱으로 키가 추가되는 해시 테이블의 변형이다. 키는 적은 (충돌) 키로 배열 위치에 놓인다. 키를 버킷에 보관하지 않는 한 일부 충돌 해결 방법이 필요하다. 성공적인 검색의 평균 사례 비용은 $O{\displaystyle }$( 2${\displaystyle }$+${\displaystyle }$( ${\displaystyle \mathrm{m}}$- 1${\displaystyle }$)${\displaystyle }$/ n )${\displaystyle$ O$(2+(m-1)/n)}$이며$,$ 여기서 $m{\displaystyle }$ ${\displaystyle m}$은 키 수이고 n ${\displaystyle n}$은 $어레이{\displaystyle }$ 크기입니다. 가장 많은 충돌은 개연성이 높은 ${\displaystyle {\mathrm{로그}}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle \ln +}$ n +$$(${\displaystyle m}$/ n${\displaystyle }$) {\$displaystyle \log _${2}\$ln$ n$+\theta$($m/n$)}이다."^[1]

작동 방식

2-선택 해싱은 해시함수로 동작할 것으로 예상되는 2개의 해시함수₁ h(x)와₂ h(x)를 활용한다(즉, 우주의 정수를 지정된 범위로 매핑). 두 해시함수는 독립적이어야 하며 서로 상관관계가 없어야 한다. 해시함수가 두 개 있으면 키 x는 각각의 출력값인 h₁(x)와 h₂(x)를 기준으로 최대 두 개의 잠재적 위치를 저장할 수 있다. 두 개의 해시함수가 있지만, 두 개의 해시함수가 그 테이블의 위치에 매핑되는 테이블은 하나뿐이라는 점에 유의해야 한다.

실행

이 경우에 해싱 구현의 가장 중요한 기능은 삽입과 검색이다.

• 삽입: 두 해시함수의 값을 삽입할 때 삽입할 객체에 대해 계산한다. 그런 다음 개체는 더 적은 개체가 포함된 버킷에 배치된다. 버킷의 크기가 같으면 기본 위치는 h₁(x) 값이다.
• 검색: 효과적인 검색은 두 버킷(h₁(x)과 h(x₂)가 매핑된 버킷 위치)을 모두 검색하여 원하는 값을 검색한다.

퍼포먼스

모든 해시 테이블이 그렇듯이 성능은 가장 큰 버킷을 기반으로 한다. 사용된 값과 해시함수를 기준으로 버킷 크기가 큰 경우가 있지만 이는 드물다. 따라서 두 개의 해시함수를 가지며, 따라서 한 값에 대해 두 개의 가능한 위치를 가지면 대형 버킷이 발생할 가능성이 훨씬 더 낮다.

2-선택 해싱을 사용하는 동안 예상되는 버킷 크기는 θ(log(n))이다. 이러한 개선은 "두 가지 선택의 힘"이라고 알려진 무작위화된 개념에 기인한다.

두 개의 해시함수를 사용하면 단일 해시함수에 비해 상당한 이점을 얻을 수 있다. 해시함수의 추가 해시함수는 최대치를 상수인자로만 감소시키는 등 3개 이상의 해시함수를 사용할 경우 개선은 거의 없다(기대 순서 통계에는 변화가 없다).^[2]

어떤 사람들은 일부 CPU 캐시에 있는 양방향 왜곡 연관 캐시라고 불리는 2-선택 해싱의 유형을 추천한다.^[3]

2-좌측 해싱(동일한 크기의 n/2 해시 테이블 2개를 사용하고, 키를 왼쪽 해시 테이블에 넣어 비대칭적으로 타이를 해결함)은 충돌이 적어 n 크기의 큰 해시 테이블 1개를 사용하는 2-선택 해시보다 성능이 우수하다.^{[4][full citation needed]}

참조

이 문서에는 NIST 문서의 공용 도메인 자료가 포함되어 있다.

추가 읽기

• Azar, Yossi; Broder, Andrei Z.; Karlin, Anna R.; Upfal, Eli (23–25 May 1994), "Balanced Allocations (extended abstract)" (PDF), Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94, Montréal, pp. 593–602, CiteSeerX 10.1.1.38.5375, doi:10.1145/195058.195412, ISBN 0897916638, S2CID 1014349
• Azar, Yossi; Broder, Andrei Z.; Karlin, Anna R.; Upfal, Eli (1999), "Balanced Allocations" (PDF), SIAM J. Comput., 29 (1): 180–200, doi:10.1137/S0097539795288490