유니버설 해싱

수학과 컴퓨팅에서 유니버설 해싱(임의화된 알고리즘이나 데이터 구조에서)은 일정한 수학적 특성을 가진 해시함수 계열(아래 정의 참조)에서 임의로 해시함수를 선택하는 것을 말한다.이것은 비록 데이터가 적에 의해 선택되더라도, 예상 시 적은 수의 충돌을 보장한다.많은 보편적인 가정이 알려져 있으며(해싱 정수, 벡터, 문자열) 그들의 평가는 종종 매우 효율적이다.유니버설 해싱은 예를 들어 해시 테이블, 무작위화된 알고리즘, 암호학의 구현에 있어서 컴퓨터 과학에서 수많은 용도를 가지고 있다.

소개

일부 유니버스 $U{\displaystyle }$ ${\displaystyle U}$의 키를 $m{\displaystyle }$ ${\displaystyle m}$ 빈$([{\displaystyle \mathrm{m}}$ ${\displaystyle ]}$=${\displaystyle }${ 0${\displaystyle }$,${\displaystyle }$… ,${\displaystyle }$m${\displaystyle }$- ${\displaystyle 1\}}$ ${\displaystyle [m]=\{0,\dots,m-1\})$에 매핑하려고 한다고 가정해 보십시오.$$알고리즘은 사전에 알려져 있지 ${\displaystyle 않은}$S = ${\displaystyle n}${\$displaystyle$ $S$$\subseteq$}의$$ 일부 데이터 $세트{\displaystyle }$ S$$will U {\$displaystyle$S =$n}$을 처리해야 한다.일반적으로 해싱의 목표는 적은 수의 충돌(동일한 빈에 착륙하는$$ $S{\displaystyle }$ ${\displaystyle S}$의 키)을 얻는 것이다.상대방은 정확히 Bin의 사전 $이미지$로 S ${\displaystyle S}$을(를) 선택할 수 있기 때문에 $U{\displaystyle }$ ${\displaystyle U}$의 크기가 $m{\displaystyle }$ ${\displaystyle \cdot n}$ ${\displaystyle m\cdot$ n$}$보다 크면$$ 결정론적 해시함수는 적대적 설정에서 어떤 보증도 제공할 수 없다$.$이것은 모든 데이터 키가 같은 빈에 착륙하여 해싱을 무용지물로 만든다는 것을 의미한다.더욱이 결정론적 해시함수는 재해시를 허용하지 않는다: 때때로 입력 데이터가 해시함수에 좋지 않은 것으로 판명되어 해시함수를 변경하고자 한다.

이러한 문제에 대한 해결책은 해시함수 계열에서 임의로 함수를 선택하는 것이다.$함수{\displaystyle }$ H${\displaystyle }$=${\displaystyle }${ ${\displaystyle h}$: ${\displaystyle U}$→${\displaystyle }$[ ${\displaystyle m}$ ${\displaystyle$ H$=\{h:$$U\to [m]\}}$ is called a universal family if, ${\displaystyle \forall x,y\in U,~x\neq y:~~\Pr _{h\in H}[h(x)=h(y)]\leq {\frac {1}{m}}}$.

$즉{\displaystyle }$, 해시함수 $h{\displaystyle }$ ${\displaystyle h}$을 H ${\displaystyle H}$에서 임의로 추출할$$$$ 때 우주의 어떤 두 키라도 최대 $1{\displaystyle \mathrm{}}$/ ${\displaystyle m}$ ${\displaystyle h}$에서 확률과 충돌하는 것이다$.$ 이것은 해시함수가 모든 키에 진정으로 무작위 해시 코드를 할당했을 때 우리가 예상할 수 있는 충돌 확률이다.때때로, 충돌 $확률{\displaystyle }$ O${\displaystyle }$( ${\displaystyle 1}$ / m$){\displaystyle O (1/m)}$을(를) 허용하도록 정의가 완화된다$.$이 개념은 1977년 카터와 웨그먼에^[1] 의해 도입되었으며, 컴퓨터 공학에서 수많은 응용 프로그램(예: 참조)을 찾아냈다.충돌 확률에 대한 < ${\displaystyle \epsilon <1}$의 상한선이 있다면, 우리는 $ϵ{\displaystyle }$ ${\displaystyle \epsilon }-$alremost$$ Universality가 있다고 말한다.

많은, 그러나 전부는 아니지만, 보편적인 가정들은 다음과 같은 더 강한 통일된 차이점 속성을 가지고 있다.

${\displaystyle \forall x,y\in U,~x\neq y}$, when ${\displaystyle h}$ is drawn randomly from the family ${\displaystyle H}$, the difference ${\displaystyle h(x)-h(y)~{\bmod {~}}m}$ is uniformly distributed in ${\displaystyle [m]}$.

보편성의 정의는 충돌을 카운트하는 $h{\displaystyle }$( ${\displaystyle x}$)${\displaystyle }$- ${\displaystyle h}$( ${\displaystyle y}$)${\displaystyle }$= ${\displaystyle 0}$ $[\displaystyle h(x)-h(y)=0$의 여부에만 관련된다는 점에 유의하십시오.균일차 특성이 더 강하다.

(Similarly, a universal family can be XOR universal if ${\displaystyle \forall x,y\in U,~x\neq y}$, the value ${\displaystyle h(x)\oplus h(y)~{\bmod {~}}m}$ is uniformly distributed in ${\displaystyle [m]}$ where ${\displaystyle \oplus }$ is the bitwise exclusive또는 운영.$이것$은 m ${\displaystyle m}$이(가) 2의 검정력일$$ 경우에만 가능하다.)

An even stronger condition is pairwise independence: we have this property when ${\displaystyle \forall x,y\in U,~x\neq y}$ we have the probability that ${\displaystyle x,y}$ will hash to any pair of hash values ${\displaystyle z_{1},z_{2}}$ is as if they were perfectly random: ${\displaystyle P}$${\displaystyle (}$ ${\displaystyle h}$( ${\displaystyle x}$)${\displaystyle }$= ${\displaystyle z}$ ${\displaystyle 1}$ ${\displaystyle {}_{}}$ h${\displaystyle }$( y${\displaystyle }$)${\displaystyle }$= z ${\displaystyle {2\mathrm{}}_{}}$)${\displaystyle }$= 1${\displaystyle }$/ ${\displaystyle {m\mathrm{}}^{}}$ ${\displaystyle 2{}^{}}$ ${\$ 쌍의 독립성을 강한 보편성이라고 부르기도 한다.

또 다른 재산은 통일성이다.우리는 모든 해시 값이 동일하게 될 가능성이 있는 경우 패밀리가 균일하다고 말한다: $모든{\displaystyle }$ 해시 값 $z{\displaystyle }$ ${\displaystyle z}$에 ${\displaystyle \mathrm{대해}P}$(${\displaystyle h}$($x)=z)=1/m}.$ 보편성은 균일성을 의미하지 않는다$.$그러나 강한 보편성은 획일성을 내포하고 있다.

균일한 거리 특성을 가진 패밀리를 주어진다면, 해시함수에${\displaystyle }$[${\displaystyle m}$] ${\displaystyle [m]$의 값과 함께 균일하게 분포된 랜덤 상수를 추가함으로써 쌍방향 독립적이거나 강력한 범용 해시 패밀리를 생산할 수 있다.(비슷하게, $m{\displaystyle }${\$displaystym m}$이 2의 힘이라면, 우리는 쌍방향 독립성을 얻을 수 있다.배타적 또는 균일하게 분포된 랜덤 상수를 사용하여 XOR 범용 해시 패밀리).상수에 의한 변화는 어플리케이션(예: 해시 테이블)에서 때로는 무관하기 때문에, 균일한 거리 속성과 쌍방향 독립성을 신중하게 구분하지 않는 경우도 있다.^[3]

일부 애플리케이션(예: 해시 테이블)의 경우 해시 값의 최소 중요 비트도 범용적이 되는 것이 중요하다.가족이 강하게 보편적일 때 이것은 보장된다: $H{\displaystyle }$ ${\displaystyle H}$이(가) $m{\displaystyle }$= ${\displaystyle 2^{}}$ ${\displaystyle L{\mathrm{}}^{}}$ ${\$${\displaystyle {{=}^{}}^{}}$$2^{L}}}$을(를) 가진 강력한 보편적 가족이라면$,$ 모든 $h$ ∈ ${\displaystyle h$${\bmod{2$$^{L$$'}}}$ $함수들$로 이루어진 가족도 강하게 보편적이다$$.${\displaystyle L^{}}$ ${\displaystyle {\prime }^{}}$ ${\displaystyle \le }$ ${\displaystyle L}$ ${\displaystyle$ L$'\leq$ L$\}.$ 불행히도 (미리) 보편적인 가정은 그렇지 않다.예를 들어 ID함수 $h{\displaystyle (x}$ )${\displaystyle }$= ${\displaystyle x}$ ${\displaystyle$ h$(x)=x}$로 이루어진 패밀리는 분명히 보편적이지만$$, 함수 $h{\displaystyle (}$ ${\displaystyle x}$)${\displaystyle }$= x ${\displaystyle {mod{}^{}}^{}}$ ${\displaystyle 2{\mathrm{}}^{}}$ L ${\displaystyle {{\prime }^{}}^{}}$ ${\$의 패밀리는 보편화되지$$ 않는다.

UMAC와 Poly1305-AES 및 몇 가지 다른 메시지 인증 코드 알고리즘은 범용 해싱을 기반으로 한다.^[4][5]그러한 애플리케이션에서 소프트웨어는 해당 메시지에 대한 고유한 noce에 기초하여 모든 메시지에 대해 새로운 해시 함수를 선택한다.

몇몇 해시 테이블 구현은 범용 해싱에 기초한다.그러한 애플리케이션에서, 일반적으로 소프트웨어는 "너무 많은" 키들이 충돌했다는 것을 인지한 후에만 새로운 해시함수를 선택한다. 그 때까지, 동일한 해시함수를 계속해서 사용한다. (다이나믹 퍼펙트 해싱과 같은 일부 충돌 해결방안은 충돌이 있을 때마다 새로운 해시함수를 선택한다.뻐꾸기 해싱과 2-선택 해싱과 같은 다른 충돌 해결 방식은 새로운 해시 함수를 선택하기 전에 여러 번의 충돌을 허용한다.정수, 벡터 및 문자열에 대해 가장 빨리 알려진 범용 및 강하게 알려진 범용 해시함수에 대한 조사가 에 수록되어 있다.^[6]

수학적 보증

$n{\displaystyle }$ ${\displaystyle n}$ 키의$$$$ 고정 세트 $S{\displaystyle }$ ${\displaystyle S}$에 대해 범용 패밀리를 사용하면 다음과 같은 속성이 보장된다.

1. $S{\displaystyle }$ ${\displaystyle S}$의 고정 $x{\displaystyle }$ ${\displaystyle x}$에 대해$$빈 $h{\displaystyle }$ (${\displaystyle x}$) ${\displaystyle h(x)}$에서 예상되는 키 수는 $n{\displaystyle }$/ ${\displaystyle m}$ ${\displaystyle n/m}$입니다$.$ 체인을 통해 해시 테이블을 구현할 때 이 숫자는 키 $x{\displaystyle }$ ${\displaystyle x}$와 관련된 작업의 예상 실행 시간에 비례합니다.$$ (예: 쿼리, 삽입 또는 삭제).
2. The expected number of pairs of keys ${\displaystyle x,y}$ in ${\displaystyle S}$ with ${\displaystyle x\neq y}$ that collide (${\displaystyle h(x)=h(y)}$) is bounded above by ${\displaystyle n(n-1)/2m}$, which is of order ${\displaystyle O(n^$${2}/m)}$. When the number of bins, ${\displaystyle m}$ is chosen linear in ${\displaystyle n}$ (i.e., is determined by a function in ${\displaystyle \Omega (n)}$), the expected number of collisions is ${\displaystyle O(n)}$. When hashing into ${\displaystyle n^{2}}$ bins, there are no colli적어도 반 정도는 확률로 체온을 만들어 낼 수 있다.
3. 최소 $t{\displaystyle }$ ${\displaystyle t}$ 키가$$ 들어 있는 빈의 예상 키 수는 ${\displaystyle \mathrm{2n}}$/${\displaystyle }$( ${\displaystyle \mathrm{t}}$- 2${\displaystyle }$( ${\displaystyle n}$/ ${\displaystyle m}$)${\displaystyle }$+ ${\displaystyle 1}$) ${\displaystyle 2n/(t-2(n/m)+1)}$로 제한된다$.$^[7]따라서, 각 빈의 용량이 평균 크기의 3배(${\displaystyle }$= ${\displaystyle 3n}$/ m $[\displaystyle t=3n/m})$까지 캡을 씌운 경우,$$ 넘치는 빈의 총 키 수는 최대 $O{\displaystyle }$( ${\displaystyle m}$) ${\displaystyle O(m)}$이다$.$이것은 충돌 확률을${\displaystyle }1{\displaystyle \mathrm{}}$ / ${\displaystyle m}${\$displaystyle 1$/m$}$로 제한한 해시 패밀리를 가지고 있을 뿐이다$.$ 더 약한 정의를 사용하고, $O{\displaystyle }$ (${\displaystyle 1}$/ ${\displaystyle m}$) ${\displaystyle O (1/m)}$로 제한한다면$,$ 이 결과는 더 이상 사실이 아니다.^[7]

위의 보증은 $고정{\displaystyle }$ 세트 S ${\displaystyle S}$에 대한 보류를 보장하므로 데이터 세트가 상대방에 의해 선택되면 보류를 보장한다$.$그러나 상대방은 알고리즘의 해시함수 무작위 선택 이전에(또는 독립적으로) 이 선택을 해야 한다.상대가 알고리즘의 무작위 선택을 관찰할 수 있다면, 무작위성은 아무런 목적도 되지 않으며, 상황은 결정론적 해싱과 동일하다.

두 번째와 세 번째 보장은 일반적으로 재탕과 함께 사용된다.예를 들어, 일부 $O{\displaystyle }$(${\displaystyle n}$) ${\displaystyle O(n)}$번의$$ 충돌을 처리하기 위해 무작위화된 알고리즘을 준비할 수 있다.너무 많은 충돌을 관찰하면 패밀리에서$$ 다른 $임의{\displaystyle }$ h ${\displaystyle$ h$}$을(를) 선택하고 반복한다.보편성은 반복 횟수가 기하학적 랜덤 변수임을 보장한다.

시공

컴퓨터 데이터는 하나 이상의 기계어로 표현될 수 있기 때문에 일반적으로 기계어("integers"), 기계어의 고정 길이 벡터("string") 및 가변 길이 벡터("string")의 세 가지 도메인 유형에 대해 해시 함수가 필요하다.

해싱 정수

이 절은 기계 단어에 맞는 해싱 정수의 경우를 말하며, 따라서 곱하기, 덧셈, 나누기 등과 같은 조작은 값싼 기계 수준 지시사항이다.우주를 해시할 때는 { ${\displaystyle 0},{\displaystyle }$…,${\displaystyle U}$- ${\displaystyle 1}$ ${\displaystyle \}}$ ${\displaystyle \{0,\dots,$ U $-1\}$이(가) 되도록 하라$.$

카터와 웨그만의^[1] 원래 제안은 프라임 p${\displaystyle }p{\displaystyle }$ ${\displaystyle U}$ $displaystyle p\geq$U$}$을(를) 선택하고 정의하는$$ 것이었다.

${\displaystyle h_{a,b}(x)=(ax+b)~{\bmod{~}p)~{\bmod}$

$여기$서${\displaystyle ,}$ a , ${\displaystyle b}$ ${\displaystyle a,b}$은(는${\displaystyle )}$ ${\displaystyle 0}$ 0 ${\displaystyle a\neq$ 0$\}$의 정수 $modulo{\displaystyle }$ p ${\displaystyle p}$을(이는 선형 결합 생성기의 단일 반복)로 랜덤하게 선택된다$$.

$H{\displaystyle }$=${\displaystyle }${ h ${\displaystyle a_{}}$ ,${\displaystyle b_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle$ H$=\{h_{a,b}\}\}}}}$이(가) 범용 패밀리임을 확인하려면 $h{\displaystyle (}$ ${\displaystyle x}$)${\displaystyle }$= ${\displaystyle h(}$ ${\displaystyle y}$) ${\displaystyle h(x)=h(y)}$이(가)가 있을 때만 고정된다는 점에 유의하십시오$$.

${\displaystyle ax+b\equiv ay+b+i\cdot m{\pmod{pmod}}$

for some integer ${\displaystyle i}$ between ${\displaystyle 0}$ and ${\displaystyle (p-1)/m}$. Since ${\displaystyle p\geq U }$, if ${\displaystyle x\neq y}$ their difference ${\displaystyle x-y}$ is nonzero and has an inverse modulo ${\displaystyle p}$. Sol${\displaystyle a}$ $수익률$에 대한 경쟁

${\displaystyle a}$ ${\displaystyle \equiv }$ ${\displaystyle i}$ ${\displaystyle \cdot m}$ ${\displaystyle \cdot }$( ${\displaystyle x}$- y${\displaystyle {}^{}}$)${\displaystyle {}^{}}$- 1${\displaystyle {}^{}}$( ${\displaystyle mod}$ p${\displaystyle }$) ${\$cdot m\$cdot (x-y)^{-1}{\pmod{$pmod$\{$$p}}}}.$

$p{\displaystyle }$${\displaystyle }$- ${\displaystyle 1}$ ${\displaystyle p-1}($$a{\displaystyle }$=$$ {\$displaystyle a=0}$ 제외$$) 및 $허용$되는 범위 내에서 i ${\$$displaystyle$ $i$$}을(를)$ 변화시키면서 우측에 $0$이 아닌$$ 값을 선택할 수 있다$$$.$따라서 충돌 확률은

${\displaystyle \lfloor }$( ${\displaystyle \mathrm{p}}$- 1${\displaystyle }$)${\displaystyle }$/ ${\displaystyle m}$ ${\displaystyle \rfloor }$/ (${\displaystyle p}$- ${\displaystyle 1}$) $≤$(${\displaystyle }$( ${\displaystyle p}$- ${\displaystyle 1}$)${\displaystyle }$/ ${\displaystyle m}$)${\displaystyle }$/ (${\displaystyle \mathrm{p}}$- 1${\displaystyle }$)${\displaystyle }$= ${\displaystyle 1}$/ m$$($p-1)/m\llfloor /(p-1)\leq (p-1)=1/m$

$H{\displaystyle }$ ${\displaystyle H}$을(를) 볼 수 있는 또 다른 방법은 통계적 거리 개념을 통한 보편적 가족이다$$.차이 $h{\displaystyle }$( ${\displaystyle x}$)${\displaystyle }$- ${\displaystyle h}$( ${\displaystyle y}$) ${\displaystyle h(x)-h(y)}$을(를) 다음과$$ 같이 쓰십시오.

${\displaystyle h}$( ${\displaystyle x}$)${\displaystyle }$- ${\displaystyle h}$( ${\displaystyle y}$) ${\displaystyle \equiv }$(${\displaystyle a}$( x${\displaystyle }$- ${\displaystyle y}$ ) ${\displaystyle m}$ p${\displaystyle }$) ${\displaystyle \{}$ ( ${\displaystyle mod}$m )$${\$displaystyle$ h$(x)-h$(y$)\equiv (a$(x-y$)~{\bmod{~}{\pmod{mod$

Since ${\displaystyle x-y}$ is nonzero and ${\displaystyle a}$ is uniformly distributed in ${\displaystyle \{1,\dots ,p-1\}}$, it follows that ${\displaystyle a(x-y)}$ modulo ${\displaystyle p}$ is also uniformly distributed in ${\displaystyle \{1,\dots ,p-$$1$${\displaystyle }$(${\displaystyle h}$( ${\displaystyle x}$)${\displaystyle }$- ${\displaystyle h}$( ${\displaystyle y}$)${\displaystyle mod}$ ${\displaystyle m}$ ${\displaystyle$ ($h(x)-h(y))$의 분포$~{\bmod{~}m}$은(는) 따라서 거의 균일하며, 표본 간${\displaystyle }$확률의$$ 차이가 ±${\displaystyle 1}$ / $[\displaystyle \pm$\pm 1/$p}$이다.그 결과, 균일한 가족에 대한 통계적 거리는 $O{\displaystyle }$( ${\displaystyle m}$/ ${\displaystyle p}$) ${\displaystyle O(m/p)}$이며$,$ 이 값은 $p{\displaystyle }$ ${\displaystyle \gg }$ ${\displaystyle m}$ ${\displaystyle p\g m$일 때 무시할 수 있다.

단순 해시함수의 패밀리

${\displaystyle h_{a}(x)=(ax~{\bmod {~}p)~{\bmod {~}$

약:Pr{h(y)은())=h}≤ 2/m{\displaystyle \Pr\{h_{}())=h_ᆳ(y)\}\leq 2/m}모든 x에 ≠ y{\displaystyle x\neq y}.[1]게다가, 이 분석 거의, 카터, Wegman은[1]은 Pr ≥{h(m+1)는(1)=h}는 꽉 낀다 2/(m− 1){\displaystyle \Pr\{h_{a보편적인가}(1)=h$_{a}(m+1)\}\geq$ ${\displaystyle 2}$$/(m-1$) 언제든지$$ $({\displaystyle p}$- ${\displaystyle 1}$) ${\displaystyle m}$= 1 ${\displaystyle (p-1)~{\bmod{~}m=1$

모듈식 산술 방지

해싱 정수를 위한 기술의 상태는 1997년 디테즈펠빙거 등이 설명한 곱셈 교대제다.^[8]모듈식 산술을 피함으로써, 이 방법은 훨씬 실행하기 쉽고, 또한 실제에서 현저하게 더 빨리 실행된다(대개 최소^[9] 4배수).이 계획은 빈의 수가 $2$의 검정력,${\displaystyle }$m = ${\displaystyle {2M}^{}}$ ${\$ m$=2^{M}$라고 가정한다$.$ $w{\displaystyle }$ ${\displaystyle$ w$}$을(를) 시스템$$ 워드의 비트 수로 한다.그런 다음 해시함수는 홀수 의 인 < w ${\displaystyle a$$<2^{w$$}}}$에 대해 파라메트레이션된다.${\displaystyle h_{}}$ (${\displaystyle {}_{}x}$) ${\$$displaystyle$ $h_{a}(x)}$을$($를) 평가하려면 x ${\displaystyle x}$을$($를) {\$displaystyle a$$}$ ${\displaystyle {modulo}^{}}$ $2w$ {\$displaystystyle$2^{w$$$}}}$과(를)로 곱한$$ 다음 해시 코드로 유지하십시오.수학적 표기법에서는 다음과 같다.

${\displaystyle h_{a}(x)=(a\cdot x\,\,\\bmod {\,2}}^{w}\,\\mathrm {div} \,\,\,2^{w-M}})$

그리고 그것은 C와 같은 프로그래밍 언어로 구현될 수 있다.

${\displaystyle h_{a}(x)=}$ (size_t) (a*x) >> (w-M)

This scheme does not satisfy the uniform difference property and is only ${\displaystyle 2/m}$-almost-universal; for any ${\displaystyle x\neq y}$, ${\displaystyle \Pr\{h_{a}(x)=h_{a}(y)\}\leq 2/m}$.

To understand the behavior of the hash function, notice that, if ${\displaystyle ax{\bmod {2}}^{w}}$ and ${\displaystyle ay{\bmod {2}}^{w}}$ have the same highest-order 'M' bits, then ${\displaystyle a(x-y){\bmod {2}}^{w}}$ has either all 1's or all 0's as its hi가장 높은 순서 M 비트(${\displaystyle x}$ ${\displaystyle {mod}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$ ${\displaystyle w^{}}$ ${\$ 또는$$$$ ${\displaystyle y}$ ${\displaystyle {mod}^{}}$ 2 ${\displaystyle {w\mathrm{}}^{}}$ ${\$$x{\displaystyle }$ -${\displaystyle y}$ ${\displaystyle x-y}$의 최하위 세트 비트가 ${\displaystyle w}$- c ${\displaystyle w-c}$ 위치에 나타난다고$$ 가정합시다$.$ ${\displaystyle a}$는 랜덤 홀수 ${\displaystyle \mathrm{정수}}$이고 홀수 정수는 $Z{\displaystyle {}_{}}$ ${\displaystyle {2{\mathrm{}}^{}}_{}}$ {\$displaystysty$ $Z_{2^{w$에 invers를 가지므로 $a{\displaystyle }$(${\displaystyle x}$ ${\displaystyle -}$ y ${\displaystyle )}$ ${\displaystyle {mod}^{}}$ 2 $.$$a$$($$x-y){\bmod{2}}^{w}}}$은(는$)$ $위치상{\displaystyle \mathrm{중요도}}$가 가장$$낮은 설정 $비트$를 $가진$ w {\$displaystyle$ $w}$ -bit$$ 정수 간에 균일하게 분포한다$.$그 확률은 이 비트들은 모두 0또는 모두 1의 있기 때문에 대부분의 2/2M=2/m{\displaystyle 2/2^{M}=2/m}. 반면에, 만약 c<>M{\displaystyle c&lt을 말한다.M},()− y)모드의 고차 M비트 2w{\displaystyle a(x-y){\bmod{2}}^{w}},서, 그 확실하다 둘 다 0과 1의 함유하고 있다.${\displaystyle h(x)\neq h(y)}$. Finally, if ${\displaystyle c=M}$ then bit ${\displaystyle w-M}$ of ${\displaystyle a(x-y){\bmod {2}}^{w}}$ is 1 and ${\displaystyle h_{a}(x)=h_{a}(y)}$ if and only if bits ${\displaystyle w-1,\dots ,w-M+1}$$$확률 $1{\displaystyle \mathrm{}}$/ ${\displaystyle 2{\mathrm{}}^{}}$ ${\displaystyle M^{}}$- 1${\displaystyle {}^{}}$= ${\displaystyle 2}$/ ${\displaystyle 2}$ / m ${\displaystyle$1$/2^{M-1}=2/m}$과(와) 함께 발생하는 {\$displaystyle$ w-1$,\ldots,$w-M+1}도 1이다$.$

$이{\displaystyle {}^{}}$은 ${\displaystyle x^{}}$= ${\displaystyle 2^{}}$w - M$$- ${\displaystyle 2^{}}$ {\$displaystyle x=2$^{$w-M-2$} ${\displaystyle \mathrm{및}}$ ${\displaystyle y}$ = 3$$x {\$displaystyle y=3x$}의 예에서 알 수 있듯이 빡빡하다$.$진정한 '유니버설' 해시함수를 얻으려면 곱셈-add-shift 체계를 사용할 수 있다.

${\displaystyle h_{a,b}(x)=(ax+b){{2}}^{w}\,\mathrm {div}\,2^{w-M}}}$

C형 프로그래밍 언어로 구현될 수 있는 것은

${\displaystyle h_{a,b}(x)=}$ (size_t) (a*x+b) >> (w-M)

b<>로{\displaystyle}, b{\displaystyle b}, Pr{h, 이러한 선택을<>와 함께 있는{\displaystyle}된 이상한 양의 정수입니다.;2w{\displaystyle a<, 2^{w}}와 b{\displaystyle b}된 음이 아닌 정수;2w− M{\displaystyle b<, 2^{w-M}}.. b()))${\displaystyle h_{}}$ ${\displaystyle a_{}}$, ${\displaystyle b{}_{}}$( y${\displaystyle }$) ${\displaystyle \}}$ ${\displaystyle \le }$ ${\displaystyle 1}$/ m ${\displaystyle \Pr\{h_{a,b}(x)=h_{a,b}(y)\}\}\leq 1/m},$ $모든$ x${\displaystyle y}$y (${\displaystyle 모드{\mathrm{}}^{}}$ 2 ${\displaystyle w^{}}$)$${\$displaystystyle x\not \e{\pmod{2^{{$2^{$w$^[10]이것은 영어 논문의 오역과는 약간 다르지만 중요한 차이가 있다.^[11]

해싱 벡터

이 절은 기계어의 고정 길이 벡터 해싱과 관련이 있다.입력을 벡터 $x{\displaystyle \stackrel{\text{'}}{}}$=${\displaystyle }$( ${\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$,${\displaystyle }$…${\displaystyle }$, ${\displaystyle x_{}}$ ${\displaystyle {\mathrm{k}}_{}}$- 1${\displaystyle {}_{}}$) ${\displaystyle {\bar{x}=(x_{0},\dots,x_{k-1}}}}$의 k$$ ${\displaystyle w}$비트의$$$$ $정수{\displaystyle }$)로 해석하십시오.$H{\displaystyle }$ ${\displaystyle H}$이(가) 균일한 차이 속성을 가진 범용 가족이라면, 다음 가족(카터 및 웨그먼으로^[1] 돌아가기)도 균일한 차이 속성(따라서 보편적임)을 갖는다.

${\displaystyle h({\bar {x}})=\left(\sum _{i=0}^{k-1}h_{i}(x_{i})\right)\,{\bmod {~}}m}$, where each ${\displaystyle h_{i}\in H}$ is chosen independently at random.

$m{\displaystyle }$ ${\displaystyle m}$이(가)^[12] 2의 검정력인$$ 경우, 1이 합계를 배타적으로 대체하거나 또는

실제로 이중정밀 산수를 이용할 수 있다면, 이것은 해시함수의 곱셈-시프트 해시 패밀리로 인스턴스화된다.^[13]각각 ${\displaystyle \mathrm{2w}}$ ${\displaystyle 2w}$비트에$$ 임의의 홀수 정수의$$ $벡터{\displaystyle \stackrel{}{}}$ ${\displaystyle {a\mathrm{}}_{}}$=${\displaystyle }$( ${\displaystyle {}_{}}$,${\displaystyle }$…${\displaystyle }$, ${\displaystyle k_{}}$- ${\displaystyle 1_{}}$)$${\$displaystyle {\a}=(a_{0},\dots ,a_{k-1}}})$로 해시 함수를 초기화하십시오.${\displaystyle \mathrm{그런}}$ 다음 빈 수가${\displaystyle }M$에 $대해$ m${\displaystyle }$= ${\displaystyle {2M}^{}}$ ${\$인 경우 ${\displaystyle M\leq w$ :

${\displaystyle h_{\bar {a}}({\bar {x}})=\left({\big (}\sum _{i=0}^{k-1}x_{i}\cdot a_{i}{\big )}~{\bmod {~}}2^{2w}\right)\,\,\mathrm {div} \,\,2^{2w-M}}$.

승수를 절반으로 줄일 수 있는데, 실제로는 대략 2배의 속도상승으로 해석된다.^[12]각각 ${\displaystyle \mathrm{2w}}$ ${\displaystyle 2w}$비트에$$ 임의의 홀수 정수의$$ $벡터{\displaystyle \stackrel{}{}}$ ${\displaystyle {a\mathrm{}}_{}}$=${\displaystyle }$( ${\displaystyle {}_{}}$,${\displaystyle }$…${\displaystyle }$, ${\displaystyle k_{}}$- ${\displaystyle 1_{}}$)$${\$displaystyle {\a}=(a_{0},\dots ,a_{k-1}}})$로 해시 함수를 초기화하십시오.다음 해시 패밀리는 보편적이다.^[14]

${\displaystyle h_{\bar {a}}({\bar {x}})=\left({\Big (}\sum _{i=0}^{\lceil k/2\rceil }(x_{2i}+a_{2i})\cdot (x_{2i+1}+a_{2i+1}){$$\Big )}{\bmod{~2}}^{2w}\오른쪽)\,\,\,\\mathrm {div}\,\,\,2^{2w-M$

이중정밀 연산을 사용할 수 없는 경우, 입력 내용을 반음절(${\displaystyle w\mathrm{}}$ /${\displaystyle }$2$${\$displaystyle w/2}$ -bit$$ 정수)의 벡터로 해석할 수 있다.그런 다음 알고리즘은 $\lceil {\displaystyle }$ ${\displaystyle k}$/ ${\displaystyle 2\mathrm{}}$ ${\displaystyle \rceil }$ ${\displaystyle \lceil k/2\rceil }$ 곱을$$ 사용하게 되는데 여기서 $k{\displaystyle }$ ${\displaysty k}$은 벡터 내의 반 단어 수입니다.따라서 알고리즘은 입력 단어당 하나의 곱셈의 "속도"로 실행된다.

또한 해싱 정수의 비트를 바이트 벡터로 해석하여 해싱 정수에 동일한 체계를 사용할 수 있다.이 변종에서 벡터 기법은 표 해싱으로 알려져 있으며, 곱셈 기반의 범용 해싱 체계에 대한 실질적인 대안을 제공한다.^[15]

고속에서도 강한 보편성이 가능하다.^[16]${\displaystyle \mathrm{2w}}$ ${\displaystyle 2w}$비트에서$$ 임의 정수의$$ $벡터{\displaystyle \stackrel{}{}}$ a${\displaystyle }$=${\displaystyle }$(${\displaystyle 0_{}{}_{}}$,${\displaystyle }$…${\displaystyle }$k${\displaystyle {}_{}}$) ${\displaystyle {\a}=(a_{0},\dots ,a_{k})$로 해시함수를 초기화하십시오.계산

${\displaystyle h_{\bar {a}}({\bar {x}})^{\mathrm {strong} }=(a_{0}+\sum _{i=0}^{k-1}a_{i+1}x_{i}{\bmod {~}}2^{2w})\,\,\mathrm {div} \,\,2^{w}}$.

$결과$는 w ${\displaystyle w}$비트에서$$ 매우 보편적이다.실험 결과,${\displaystyle }w{\displaystyle }$ = ${\displaystyle 32}${\$displaystyle w=32}$에 대해 최근 Intel 프로세서에서 바이트당 0.2 CPU 사이클로 실행되는 것으로 밝혀졌다$.$

해싱 현

기계어의 가변 크기 벡터를 해싱하는 것을 말한다.문자열의 길이가 작은 숫자로 경계가 될 수 있다면 위에서부터 벡터 솔루션을 사용하는 것이 좋다(개념적으로 0으로 경계가 되는 것을 0으로 패딩한다).필요한 공간은 문자열의 최대 길이지만, $h{\displaystyle }$( ${\displaystyle s}$) ${\displaystyle h(s)}$을 평가하는 시간은 $s{\displaystyle }$ ${\displaystyle s}$의 길이에 불과하다$$$.$ 문자열에서 0이 금지되는 한, 해시함수를 평가할 때 0 패딩은 보편성에 영향을 주지 않고 무시할 수 있다.^[12]문자열에서 0이 허용되는 경우 패딩 전에 모든 문자열에 0이 아닌 가상 문자(예: 1)를 추가하는 것이 가장 좋을 수 있다는 점에 유의하십시오. 이렇게 하면 보편성이 영향을 받지 않도록 보장할 수 있다.^[16]

$이제{\displaystyle \stackrel{}{}}$ x${\displaystyle \stackrel{}{\text{'}}}$=${\displaystyle }$( x ${\displaystyle {0\mathrm{}}_{}}$,${\displaystyle }$…${\displaystyle }$, ${\displaystyle {}_{}}$ ${\displaystyle {\ell }_{}}$) ${\displaystyle {\x}=(x_{0},\dots,x_{\ell }}}}$을(를) 해시하려고 한다고 가정해 보십시오$.$ $여기$서 {$${\$displaysty \ell}$에 대한 선한 바운드는 선입자를 알 수 없다$$.에 의해 제안된 범용 패밀리는 문자열 $x{\displaystyle }$ ${\displaystyle x}$을 다항식 모듈로의 계수로$$ 대한다.$x{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\displaystyle {}_{}}$[ ${\displaystyle u}$ ${\displaystyle ]}$ ${\displaystyle x_{i}\in [u$인 경우 $p{\displaystyle }$ ${\displaystyle \ge }$ ${\displaystyle max}${${\displaystyle u,}$ ${\displaystyle m}$ ${\displaystyle \}}$ ${\displaystyle p\geq \max\{u,m\}}$을 prime으로 설정하고 다음을 정의하십시오$$.

${\displaystyle h_{a}({\bar {x}})=h_{\mathrm {int} }\left({\big (}\sum _{i=0}^{\ell }x_{i}\cdot a^{\ell -i}{\big )}{\bmod {~}}p\right)}$, where ${\displaystyle a\in [p]}$ is uniformly random and ${\dis$$playstyle h_{\mathrm{int}}}}}}$은(는) 범용 패밀리 매핑 정수 도메인${\displaystyle }$[${\displaystyle p}$]${\displaystyle }$[${\displaystyle m}$ ${\displaystyle ]}$ ${\displaystyle [p]\mapsto [m]}$에서 임의로 선택된다$.$

위의 모듈식 산술의 특성을 이용하여 다음과 같이 큰 문자열의 큰 숫자를 생성하지 않고 연산할 수 있다.^[17]

유인트 해시하다(끈 x, 인트로 a, 인트로 p)  유인트 h = 이니셜_VALUE  을 위해 (유인트 i=0 ; i < x.길이 ; ++i)   h = ((h*a) + x[i]) 모드의 p  돌아오다 h 

이 Rabin-Karp 롤링 해시는 선형 합성 생성기를 기반으로 한다.^[18]위 알고리즘은 곱셈 해시함수라고도 한다.^[19]실제로 많은 프로그래밍 언어에서 mod(Max-Int-Value + 1)와 같기 때문에 단순히 정수가 넘치도록 허용함으로써 mod 연산자와 p 매개변수를 모두 피할 수 있다.아래 표는 인기 있는 구현의 일부에 대해 h 및 a를 초기화하기 위해 선택한 값을 보여준다.

2개의 $문자열{\displaystyle \stackrel{}{}}$ x x${\displaystyle ,\stackrel{}{}y}$의$${\$displaystyle {\x},{\bar${y}을$$(를) 고려하여$$longer {\$displaystyle \ell}$을(를) 긴 문자열의 길이로$$ 한다. 분석을 위해 짧은 문자열은 개념적으로 최대 길이 $length{\displaystyle }$ ${\displaystyle \ell$ \ell$$}. $h{\displaystyle {}_{}}$ ${\displaystyle {\mathrm{in}}_{}}$ ${\displaystyle {\mathrm{t}}_{}}$ ${\$을 적용하기 전에 충돌.$int$$}{{\displaystyle a}$이(가) x - $''''-'[\${y$}}}$ 계수를 가진 다항식의 루트임을$$ 암시한다$.$이 다항식에는 최대 $\ell {\displaystyle }${\$displaystyle \ell}$뿌리$$ $modulo{\displaystyle }$p {\$displaystyle$p}이$($가) 있으므로 충돌 $확률$은 최대 ${\displaystyle p}$/$$p {\$displaystyle \ell$ /p$\}.$ ${\displaystyle {무작위\mathrm{}}_{}}$ h $t$ {\$displaystystystyle h_{\mathrm{$int}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}을 통한 충돌 확률은 총 충돌 확률을 $1{\displaystyle \frac{\mathrm{}}{}\frac{\mathrm{mathrmp로<img\; alt="h\_\{\{\backslash mathrm\; \{int\}\}\}"\; aria-hidden="true"\; class="mwe-math-fallback-image-inline"\; src="https://wikimedia.org/api/rest\_v1/media/math/render/svg/94da7db0089c130af810f29ed4531ba2f074fed2"\; style="vertical-align:\; -0.671ex;\; width:3.582ex;\; height:2.509ex;"\; papago-attr-id="460">}}{}}$${\displaystyle {\frac{1}{m}+{\frac {\ell}{p$따라서 $prime{\displaystyle }$ p ${\displaystyle$ p$}$이(가$$) 해시된 문자열 길이에 비해 충분히 크면, 패밀리는 유니버설(통계적 거리)에 매우 가깝다.

알 수 없는 길이의 문자열을 고정 길이의 해시 값으로 해시하는 데 사용되는 해시함수의 다른 보편적 패밀리에는 라빈 지문과 부즈하시가 있다.

모듈식 산술 방지

모듈식 산술의 계산 페널티를 완화하기 위해, 세 가지 트릭을 실제에 사용한다.^[12]

1. 한 사람은 메르센의 프라임과 같은 2의 파워에 근접하기 위해$$$프라임{\displaystyle }$ p {\$displaystyle p}$를 선택한다.이를 통해 산술모듈로 $p{\displaystyle }$ ${\displaystyle p}$을(를) 분할 없이 구현할 수$$ 있다(추가 및 변속과 같은 더 빠른 연산 사용).예를 들어, 현대의 $아키텍처$에서는${\displaystyle }$p = ${\displaystyle 2^{}61}$ - 1 ${\displaystyle p=2^{61}-1$로 작업할$$수 있는 반면, x ${\displaystyle i_{}}$ ${\$s는 32비트 값이다.
2. 벡터 해싱을 블록에 적용할 수 있다.예를 들어, 하나는 문자열의 각 16단어 블록에 벡터 해싱을 적용하고, 문자열 해싱을 $\lceil {\displaystyle }$ ${\displaystyle k}$/ ${\displaystyle 16}$ ${\displaystyle \rceil }$ ${\displaystyle \lceil k/16\rceil }$ 결과에$$ 적용한다.느린 문자열 해싱은 실질적으로 작은 벡터에 적용되기 때문에, 이것은 본질적으로 벡터 해싱만큼 빠를 것이다.
3. 산술모듈로 $[\$ 2$^{w}]$를 분할 없이 구현할$$ 수 있도록(비트 마스킹의 더 빠른 연산 사용) 2를 디비저로 선택한다.NH 해시함수 패밀리는 이러한 접근법을 취한다.

참고 항목

• K 독립 해싱
• 롤링 해싱
• 표 해싱
• 민자독립
• 유니버설 단방향 해시함수
• 저점수열
• 퍼펙트 해싱

참조

추가 읽기

• Knuth, Donald Ervin (1998). The Art of Computer Programming, Vol. III: Sorting and Searching (3rd ed.). Reading, Mass; London: Addison-Wesley. ISBN 0-201-89685-0.

외부 링크

• 개방형 데이터 구조 - 섹션 5.1.1 - 곱셈 해싱, 팻 모린