이차 프로빙

이 글은 검증을 위해 인용구가 추가로 필요하다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선할 수 있도록 도와주십시오. 공급되지 않은 재료는 도전하여 제거할 수 있다. 출처 찾기: "Quadratic Probing" – 뉴스 · 신문 · 책 · 학자 · JSTOR (1919년 9월) (이 템플릿 메시지를 제거하는 방법과 시기 학습)

2차 프로빙은 해시 테이블의 해시 충돌을 해결하기 위한 컴퓨터 프로그래밍의 오픈 어드레싱 방식이다.2차 프로빙은 원래 해시 인덱스를 취하여 열린 슬롯이 발견될 때까지 임의 2차 다항식의 연속 값을 추가하는 방식으로 작동한다.

2차 프로브를 사용한 예시 순서는 다음과 같다.

${\displaystyle H+1^{2},H+2^{2},H+3^{2},H+4^{2},...,H+k^{2}}$

2차 탐침은 면역성은 없지만 선형 탐침으로 발생할 수 있는 클러스터링 문제를 피하는 것이 좋기 때문에 오픈 어드레싱 테이블에서 보다 효율적인 알고리즘이 될 수 있다.그것은 또한 참조의 지역성을 보존하기 때문에 좋은 메모리 캐슁을 제공하지만, 선형 프로빙은 더 큰 지역성을 가지고 있고, 따라서 캐시 성능이 더 좋다.^{[dubious – discuss][citation needed]}

이차 함수

h(k)를 [0, m-1]의 정수에 요소 k를 매핑하는 해시함수로 하고 여기서 m은 테이블의 크기다.함수에 의해 값 k에 대한 i^th 프로브 위치가 제공되도록 함

${\displaystyle h(k,i)=h(k)+c_{1}i+c_{2}i^{2}{\pmod{m}}}}$

여기서₂ c ≠ 0(c₂ = 0이면 h(k,i)는 선형 프로브로 분해된다.주어진 해시 테이블의 경우 c와₁ c의₂ 값은 일정하게 유지된다.

예:

• If ${\displaystyle h(k,i)=(h(k)+i+i^{2}){\pmod {m}}}$, then the probe sequence will be ${\displaystyle h(k),h(k)+2,h(k)+6,...$$}$
• m = 2의ⁿ 경우, [0, m-1]의 i에 대한 h(k,i) 값이 모두 구별되므로 상수에₁ 대한 좋은 선택은 c = c = 1₂/2이다.$이렇게$ 하면 프로브 시퀀스가$$$h{\displaystyle }$( ${\displaystyle k}$)${\displaystyle }$, $h$( $k$)${\displaystyle }$+ 1${\displaystyle }$, ${\displaystyle \mathrm{h}}$ (${\displaystyle k}$)${\displaystyle }$+ ${\displaystyle 3}$, $h$($k$)${\displaystyle }$+ 6${\displaystyle }$,${\displaystyle }$.${\displaystyle }$. . .$$. . . . . $.$ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .값이 1, 2, 3, ...씩 증가하는$$}($$삼각형 숫자).
• 프라임 m > 2의 경우, c와₁ c의₂ 대부분의 선택은 [0, (m-1)/2]의 i에 대해 h(k,i)를 구별하게 할 것이다.이러한₁ 선택에는₂ c = c = 1/2, c₁ = 1₂ 및 c = 0₁₂, c = 1이 포함된다.그러나 주어진 요소에 대한 m/2 구별되는 프로브만 있을 뿐, 부하계수가 1/2을 초과할 때 삽입이 성공한다는 것을 보장하기 위한 다른 기법이 필요하다.
• For ${\displaystyle m=n^{p}}$, where m, n, and p are integer greater or equal 2 (degrades to linear probe when p = 1), then ${\displaystyle h(k,i)=(h(k)+i+ni^{2}){\pmod {m}}}$ gives cycle of all distinct probes.$루프$로 계산할 수 있다: h${\displaystyle }$( k${\displaystyle }$, ${\displaystyle 0}$)${\displaystyle }$= ${\displaystyle h}$ (${\displaystyle }$k${\displaystyle }$) ${\displaystyle h(k,0)=h(k$,0)=h(k,0$)=$$h{\displaystyle (}$k,${\displaystyle i}$+ ${\displaystyle 1)}$= (${\displaystyle k,}$ i${\displaystyle ,}$ 1) =${\displaystyle }$(${\displaystyle h,}$ k )${\displaystyle }$+${\displaystyle \mathrm{n}}$ +${\displaystyle }$1${\displaystyle (모드}$ m${\displaystyle }$)${\$2in$+n$+n+n+n+$n+$$n$+1)${\pmod{m}}$
• 임의의 m에 대해 2차 프로빙을 사용한 전체 사이클은 계산 프로브 $지수$인 h ( k ,${\displaystyle i}$)${\displaystyle }$= ${\displaystyle h}$(${\displaystyle k}$)${\displaystyle }$+${\displaystyle }$(${\displaystyle }$i ${\displaystyle {2\mathrm{}}^{}}$+ ${\displaystyle i}$)${\displaystyle }$/ 2${\displaystyle }$( ${\displaystyle \mathrm{mod}}$ r ${\displaystyle o}$ ${\displaystyle u}$ ${\displaystyle d}$ ${\displaystyle U}$ ${\displaystyle \mathrm{p}}$ 2${\displaystyle }$( m${\displaystyle }$) ${\$2)를 반올림하여 달성할 수 있다$.$${\pmod {roundUp2(m$ , ${\displaystyle h(k,i)=m}$일 때 반복을 건너뛰십시오최대 ( )- m< / $(\displaystyle roundUp2(m)-m<m/2} 생략$ 반복이 있으며, 이러한 반복은 메모리를 지칭하지 않기 때문에 대부분의 현대 프로세서에서 빠르게 작동한다.반올림 m은 다음을 통해 계산할 수 있다.

uint64_t 반올림2(uint64_t v){  v--;  v = v >> 1;  v = v >> 2;  v = v >> 4;  v = v >> 8;  v = v >> 16;  v = v >> 32;  v++;  돌아오다 v; } 

제한 사항

교대 부호

If the sign of the offset is alternated (e.g. +1, −4, +9, −16, etc.), and if the number of buckets is a prime number ${\displaystyle p}$ congruent to 3 modulo 4 (e.g. 3, 7, 11, 19, 23, 31, etc.), then the first ${\displaystyle p}$ offsets will be unique (modulo ${\displaystyle p}$).^{[further explanation needed]}$즉$, 0 ~ $p{\displaystyle }$- ${\displaystyle 1}$의$$순열이 얻어지고$$$,$ 따라서 $적어도$ 하나 이상의 자유 버킷이 존재하는 한 항상 무료 버킷을 발견하게 된다.

참조

외부 링크

• 자습서/Quadratic 프로빙