ユニバーサルハッシュ

数学とコンピューティングにおいて、ユニバーサル ハッシュ(ランダム化アルゴリズムまたはデータ構造内)とは、特定の数学的特性 (下記の定義を参照) を持つハッシュ関数のファミリーからハッシュ関数をランダムに選択することを指します。これにより、データが敵対者によって選択された場合でも、期待される衝突の数が少なくなることが保証されます。ユニバーサル ファミリーは多数知られており (整数、ベクトル、文字列のハッシュ用)、その評価は非常に効率的であることがよくあります。ユニバーサル ハッシュは、ハッシュ テーブル、ランダム化アルゴリズム、暗号化の実装など、コンピューター サイエンスでさまざまな用途に使用されています。

あるユニバースのキーをビン（ というラベルが付けられている）にマッピングするとします。アルゴリズムは、事前にわからないキーのデータ セットを処理する必要があります。通常、ハッシュの目標は、衝突の数を少なくすることです（そのユニバースのキーが同じビンに入る）。 の場合、決定論的ハッシュ関数は敵対的な設定で何の保証も提供できません。敵対者はビンの原像に正確になることを選択する可能性があるためです。つまり、すべてのデータ キーが同じビンに入るため、ハッシュは役に立たなくなります。さらに、決定論的ハッシュ関数では、再ハッシュは許可されません。入力データがハッシュ関数に適さないことが判明する場合（衝突が多すぎるなど）があり、ハッシュ関数を変更したい場合があります。 ${\displaystyle U}$${\displaystyle m}$${\displaystyle [m]=\{0,\dots ,m-1\}}$${\displaystyle S\subseteq U}$${\displaystyle |S|=n}$${\displaystyle S}$${\displaystyle |U|>m\cdot n}$${\displaystyle S}$

これらの問題の解決策は、ハッシュ関数の族から関数をランダムに選択することです。関数の族は、次の場合、ユニバーサル族と呼ばれます。 ${\displaystyle H=\{h:U\to [m]\}}$${\displaystyle \forall x,y\in U,~x\neq y:~~|\{h\in H:h(x)=h(y)\}|\leq {\frac {|H|}{m}}}$

言い換えると、ハッシュ関数がから一様にランダムに抽出された場合、宇宙の任意の 2 つの異なるキーが衝突する確率は最大で になります。これは、ハッシュ関数がすべてのキーに真にランダムなハッシュ コードを割り当てた場合に予想される衝突確率とまったく同じです。 ${\displaystyle 1/m}$${\displaystyle h}$${\displaystyle H}$

時には、定義が定数倍緩和され、衝突確率のみが要求されることもあります。この概念は1977年にCarterとWegman ^[1]によって導入され、コンピュータサイエンスの分野で数多くの応用が見られました（例えば[ ^2]を参照）。 ${\displaystyle O(1/m)}$${\displaystyle \leq 1/m}$

衝突確率の上限が である場合、ほぼ普遍性があると言えます。たとえば、普遍族はほぼ普遍性があります。 ${\displaystyle \epsilon <1}$${\displaystyle \epsilon}$${\displaystyle 1/m}$

すべてではありませんが、多くの普遍族は次のようなより強い均一差分特性を持ちます。

${\displaystyle \forall x,y\in U,~x\neq y}$が家族からランダムに抽出された場合、その差は内で均一に分布します。${\displaystyle h}$${\displaystyle H}$${\displaystyle h(x)-h(y)~{\bmod {~}}m}$${\displaystyle [m]}$

普遍性の定義は、衝突を数えるかどうかのみに関係していることに注意してください。均一差分プロパティの方が強力です。 ${\displaystyle h(x)-h(y)=0}$

(同様に、 がビット単位の排他的論理和演算である場合、ユニバーサル ファミリは XOR ユニバーサルになることができます。これは、 が 2 の累乗である 場合にのみ可能です。)${\displaystyle \forall x,y\in U,~x\neq y}$${\displaystyle h(x)\oplus h(y)~{\bmod {~}}m}$${\displaystyle [m]}$${\displaystyle \oplus}$${\displaystyle m}$

さらに強い条件は、ペアワイズ独立性です。つまり、 がハッシュする確率が、ハッシュ値の任意のペアが完全にランダムであるかのようになる場合に、この特性があります 。ペアワイズ独立性は、強い普遍性と呼ばれることもあります。 ${\displaystyle \forall x,y\in U,~x\neq y}$${\displaystyle x,y}$${\displaystyle z_{1},z_{2}}$${\displaystyle P(h(x)=z_{1}\land h(y)=z_{2})=1/m^{2}}$

もう一つの特性は均一性です。すべてのハッシュ値が等しく起こり得る場合、つまり任意のハッシュ値に対してである場合、そのファミリーは均一であると言えます。普遍性は均一性を意味するわけではありません。ただし、強い普遍性は均一性を意味します。 ${\displaystyle P(h(x)=z)=1/m}$${\displaystyle z}$

均一距離特性を持つハッシュ族が与えられた場合、ハッシュ関数に の値を持つ均一分布ランダム定数を追加することで、ペアワイズ独立または強力ユニバーサルハッシュ族を作成できます。（同様に、が2の累乗である場合、均一分布ランダム定数との排他的論理和を実行することで、XORユニバーサルハッシュ族からペアワイズ独立性を実現できます。）定数によるシフトはアプリケーション（ハッシュテーブルなど）では無関係な場合があるため、均一距離特性とペアワイズ独立性を慎重に区別しないことがあります。^[3]${\displaystyle [m]}$${\displaystyle m}$

一部のアプリケーション (ハッシュ テーブルなど) では、ハッシュ値の最下位ビットもユニバーサルであることが重要です。族が強ユニバーサルである場合、これは保証されます。 が の強ユニバーサル族である場合、すべての の関数で構成される族も の強ユニバーサルです。残念ながら、同じことは (単なる) ユニバーサル族には当てはまりません。たとえば、恒等関数で構成される族は明らかにユニバーサルですが、関数で構成される族はユニバーサルではありません。 ${\displaystyle H}$${\displaystyle m=2^{L}}$${\displaystyle h{\bmod {2^{L'}}}}$${\displaystyle h\in H}$${\displaystyle L'\leq L}$${\displaystyle h(x)=x}$${\displaystyle h(x)=x{\bmod {2^{L'}}}}$

UMACやPoly1305-AES、その他のいくつかのメッセージ認証コードアルゴリズムは、ユニバーサルハッシュに基づいています。^{[4] [5]} このようなアプリケーションでは、ソフトウェアは、そのメッセージの一意のナンスに基づいて、すべてのメッセージに対して新しいハッシュ関数を選択します。

いくつかのハッシュ テーブル実装は、ユニバーサル ハッシュに基づいています。このようなアプリケーションでは、通常、ソフトウェアは「あまりにも多くの」キーが衝突したことに気付いた場合にのみ、新しいハッシュ関数を選択します。それまでは、同じハッシュ関数が何度も使用され続けます。(動的完全ハッシュなどの一部の衝突解決方式では、衝突が発生するたびに新しいハッシュ関数を選択します。カッコウ ハッシュや2 選択ハッシュなどの他の衝突解決方式では、新しいハッシュ関数を選択する前に、いくつかの衝突を許可します)。整数、ベクトル、文字列に対する最速の既知のユニバーサル ハッシュ関数と強力にユニバーサルなハッシュ関数の調査は、にあります。^[6]

任意の固定キー セットに対して、ユニバーサル ファミリを使用すると、次のプロパティが保証されます。 ${\displaystyle S}$${\displaystyle n}$

1. 内の任意の固定値について、ビン内のキーの予想数は です。を連鎖させてハッシュ テーブルを実装する場合、この数はキーに関連する操作(クエリ、挿入、削除など) の予想実行時間に比例します。${\displaystyle x}$${\displaystyle S}$${\displaystyle h(x)}$${\displaystyle n/m}$${\displaystyle x}$
2. と衝突する内のキーのペアの期待数( ) は、 のオーダーであるによって上方に制限されます。ビンの数 がに線形に選択される場合(つまり、 内の関数によって決定される場合)、衝突の期待数は です。ビンにハッシュする場合、少なくとも半分の確率で衝突はまったく発生しません。${\displaystyle x,y}$${\displaystyle S}$${\displaystyle x\neq y}$${\displaystyle h(x)=h(y)}$${\displaystyle n(n-1)/2m}$${\displaystyle O(n^{2}/m)}$${\displaystyle m}$${\displaystyle n}$${\displaystyle \Omega (n)}$${\displaystyle O(n)}$${\displaystyle n^{2}}$
3. 少なくとも 個のキーを含むビン内のキーの期待数は、 個以上で制限されます。^[7]したがって、各ビンの容量が平均サイズ ( ) の 3 倍に制限されている場合、オーバーフローするビン内のキーの合計数は最大 個です。これは、衝突確率が 個以上で制限されるハッシュ ファミリでのみ当てはまります。 個以上で制限されるより弱い定義が使用される場合、この結果はもはや正しくありません。^[7]${\displaystyle t}$${\displaystyle 2n/(t-2(n/m)+1)}$${\displaystyle t=3n/m}$${\displaystyle O(m)}$${\displaystyle 1/m}$${\displaystyle O(1/m)}$

上記の保証は任意の固定セットに対して成り立つため、データセットが攻撃者によって選択された場合にも成り立ちます。ただし、攻撃者は、アルゴリズムによるハッシュ関数のランダム選択の前（またはそれとは独立して）にこの選択を行う必要があります。攻撃者がアルゴリズムのランダム選択を観察できる場合、ランダム性は役に立たず、状況は決定論的ハッシュと同じです。 ${\displaystyle S}$

2 番目と 3 番目の保証は、通常、再ハッシュと組み合わせて使用​​されます。たとえば、ランダム化アルゴリズムは、いくつかの衝突を処理するように準備される場合があります。衝突が多すぎる場合は、ファミリから別のランダムを選択して繰り返します。普遍性により、繰り返しの回数が幾何ランダム変数であることが保証されます。 ${\displaystyle O(n)}$${\displaystyle h}$

あらゆるコンピュータ データは 1 つ以上のマシン ワードとして表現できるため、一般に、マシン ワード (「整数」)、マシン ワードの固定長ベクトル、可変長ベクトル (「文字列」) の 3 種類のドメインに対してハッシュ関数が必要になります。

このセクションでは、マシンのワードに収まる整数をハッシュするケースについて説明します。したがって、乗算、加算、除算などの演算は、安価なマシンレベルの命令です。ハッシュされるユニバースを とします。 ${\displaystyle \{0,\dots ,|U|-1\}}$

^{カーターとウェグマン[1]}の当初の提案は、素数を選んで定義する ことだった。${\displaystyle p\geq |U|}$

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

ここで、は を法としてランダムに選択された整数です。(これは線形合同法ジェネレータの単一の反復です。) ${\displaystyle a,b}$${\displaystyle p}$${\displaystyle a\neq 0}$

が普遍的な族であることを確認するには、が成立する場合にのみ注意する必要がある。 ${\displaystyle H=\{h_{a,b}\}}$${\displaystyle h(x)=h(y)}$

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

との間の整数に対してである。 なので、の差が0 でなく を法として逆数を持つ場合である。を 解くと、${\displaystyle i}$${\displaystyle 0}$${\displaystyle (p-1)/m}$${\displaystyle p\geq |U|}$${\displaystyle x\neq y}$${\displaystyle x-y}$${\displaystyle p}$${\displaystyle a}$

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

（ は除外されているので）には可能な選択肢があり、許容範囲内で変化するが、右辺にはゼロ以外の値も考えられる。したがって衝突確率は ${\displaystyle p-1}$${\displaystyle a}$${\displaystyle a=0}$${\displaystyle i}$${\displaystyle \lfloor (p-1)/m\rfloor }$

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

普遍的な族を見るもう一つの方法は、統計的距離の概念を使うことです。差は次のように 書きます。${\displaystyle H}$${\displaystyle h(x)-h(y)}$

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

はゼロでなく、で一様分布しているので、を法として も で一様分布していることになります。 の分布は、サンプル間の確率の差を除いて、ほぼ一様です。 その結果、一様族への統計的距離は となり、 のときは無視できるようになります。 ${\displaystyle x-y}$${\displaystyle a}$${\displaystyle \{1,\dots ,p-1\}}$${\displaystyle a(x-y)}$${\displaystyle p}$${\displaystyle \{1,\dots ,p-1\}}$${\displaystyle (h(x)-h(y))~{\bmod {~}}m}$${\displaystyle \pm 1/p}$${\displaystyle O(m/p)}$${\displaystyle p\gg m}$

より単純なハッシュ関数のファミリー

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

は近似的に普遍的である:すべての に対して。^[1] さらに、この解析はほぼ厳密である: Carter と Wegman ^{[1] は、}の場合には常に であることが分かる。 ${\displaystyle \Pr\{h_{a}(x)=h_{a}(y)\}\leq 2/m}$${\displaystyle x\neq y}$${\displaystyle \Pr\{h_{a}(1)=h_{a}(m+1)\}\geq 2/(m+1)}$${\displaystyle (p-1)~{\bmod {~}}m=1}$

整数ハッシュの最新技術は、1997 年に Dietzfelbinger らによって説明された乗算シフト方式です。 ^[8]モジュラー演算を回避することで、この方法は実装がはるかに簡単になり、実際に大幅に高速化されます (通常、少なくとも 4 倍^[9] )。この方式では、ビンの数が 2 の累乗であると想定しています。をマシン ワードのビット数とします。次に、ハッシュ関数を奇数の正の整数(ビットのワードに収まる) に対してパラメーター化します。 を評価するには、 をモジュロで乗算し、上位ビットをハッシュ コードとして保持します。数学的表記では、これは次のようになります。 ${\displaystyle m=2^{M}}$${\displaystyle w}$${\displaystyle a<2^{w}}$${\displaystyle w}$${\displaystyle h_{a}(x)}$${\displaystyle x}$${\displaystyle a}$${\displaystyle 2^{w}}$${\displaystyle M}$

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

この方式は一様差分特性を満たさず、ほぼ普遍的であるに過ぎません。任意の に対して、です。 ${\displaystyle 2/m}$${\displaystyle x\neq y}$${\displaystyle \Pr\{h_{a}(x)=h_{a}(y)\}\leq 2/m}$

ハッシュ関数の動作を理解するには、と の最上位 'M' ビットが同じである場合、の最上位 M ビットがすべて 1 かすべて 0 のいずれかであることに注意してください (または が大きいかどうかによって決まります)。 の最下位セット ビットが の位置に現れると仮定します。はランダムな奇数整数であり、奇数整数はリング内に逆数を持つため、 は最下位セット ビットが の位置にある - ビット整数に均一に分布します。したがって、これらのビットがすべて 0 またはすべて 1 である確率は最大で です。一方、 の場合、 の上位 M ビットには 0 と 1 の両方が含まれるため、 であることが確実です。最後に、の場合、 のビットは 1 であり、ビットも 1 である場合に限り、これは の確率で発生します。 ${\displaystyle ax{\bmod {2}}^{w}}$${\displaystyle ay{\bmod {2}}^{w}}$${\displaystyle a(x-y){\bmod {2}}^{w}}$${\displaystyle ax{\bmod {2}}^{w}}$${\displaystyle ay{\bmod {2}}^{w}}$${\displaystyle x-y}$${\displaystyle w-c}$${\displaystyle a}$ ${\displaystyle Z_{2^{w}}}$${\displaystyle a(x-y){\bmod {2}}^{w}}$${\displaystyle w}$${\displaystyle w-c}$${\displaystyle 2/2^{M}=2/m}$${\displaystyle c<M}$${\displaystyle a(x-y){\bmod {2}}^{w}}$${\displaystyle h(x)\neq h(y)}$${\displaystyle c=M}$${\displaystyle w-M}$${\displaystyle a(x-y){\bmod {2}}^{w}}$${\displaystyle h_{a}(x)=h_{a}(y)}$${\displaystyle w-1,\ldots ,w-M+1}$${\displaystyle 1/2^{M-1}=2/m}$

この分析は厳密であり、例とで示されている。真に「普遍的な」ハッシュ関数を得るには、高次のビットを選択する乗算加算シフト方式を使用することができる。 ${\displaystyle x=2^{w-M-2}}$${\displaystyle y=3x}$

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

ここで、は となるランダムな正の整数、はとなるランダムな非負の整数です。これには、ビットの符号なし整数の算術演算が必要です。このバージョンの乗算シフトはDietzfelbingerによるもので、後にWoelfelによってより正確に分析されました。^[10]${\displaystyle a}$${\displaystyle a<2^{2w}}$${\displaystyle b}$${\displaystyle b<2^{2w}}$${\displaystyle 2w}$

このセクションでは、固定長のマシンワードのベクトルのハッシュについて説明します。入力をマシンワードのベクトル（それぞれ ビットの整数）として解釈します。が均一差分特性を持つ普遍的なファミリである場合、次のファミリ（Carter と Wegman ^[1]に遡る）も均一差分特性を持ちます（したがって普遍的です）。 ${\displaystyle {\bar {x}}=(x_{0},\dots ,x_{k-1})}$${\displaystyle k}$${\displaystyle w}$${\displaystyle H}$

${\displaystyle h({\bar {x}})=\left(\sum _{i=0}^{k-1}h_{i}(x_{i})\right)\,{\bmod {~}}m}$それぞれが独立してランダムに選択されます。${\displaystyle h_{i}\in H}$

が2の累乗である場合、合計を排他的論理和に置き換えることができる。 ^[11]${\displaystyle m}$

実際には、倍精度演算が利用可能な場合、これはハッシュ関数の乗算シフトハッシュファミリでインスタンス化されます。^[12]ハッシュ関数を、各ビットのランダムな奇数のベクトルで初期化します。次に、ビンの数が の場合: ${\displaystyle {\bar {a}}=(a_{0},\dots ,a_{k-1})}$${\displaystyle 2w}$${\displaystyle m=2^{M}}$${\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倍の速度向上に相当します。^[11]ハッシュ関数を各ビットのランダムな奇数ベクトルで初期化します。次のハッシュファミリはユニバーサルです。^[13]${\displaystyle {\bar {a}}=(a_{0},\dots ,a_{k-1})}$${\displaystyle 2w}$

${\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}\right)\,\,\mathrm {div} \,\,2^{2w-M}}$。

倍精度演算が利用できない場合は、入力をハーフワード (ビット整数) のベクトルとして解釈できます。その場合、アルゴリズムは乗算を使用します。ここで、 はベクトル内のハーフワードの数です。したがって、アルゴリズムは入力のワードごとに 1 回の乗算の「速度」で実行されます。 ${\displaystyle w/2}$${\displaystyle \lceil k/2\rceil }$${\displaystyle k}$

同じ方式は、整数のビットをバイトのベクトルとして解釈することで、整数のハッシュにも使用できます。このバリエーションでは、ベクトル手法はタブレーションハッシュと呼ばれ、乗算ベースのユニバーサルハッシュ方式の実用的な代替手段を提供します。^[14]

高速で強い普遍性も実現可能である。^[15]ハッシュ関数をビット上のランダムな整数のベクトルで初期化する。計算する ${\displaystyle {\bar {a}}=(a_{0},\dots ,a_{k})}$${\displaystyle 2w}$

${\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}}$。

この結果はビットに関して強力に普遍的です。実験的には、最近の Intel プロセッサで 1 バイトあたり 0.2 CPU サイクルで実行できることが分かりました。 ${\displaystyle w}$${\displaystyle w=32}$

これは、マシンワードの可変サイズのベクトルをハッシュすることを指します。文字列の長さが小さな数値で制限される場合、上記のベクトルソリューションを使用するのが最適です（概念的には、上限までベクトルをゼロで埋めます）。必要なスペースは文字列の最大長ですが、評価にかかる時間はの長さだけです。文字列でゼロが禁止されている限り、ハッシュ関数を評価するときにゼロパディングを無視しても、普遍性には影響しません。^[11]文字列でゼロが許可されている場合は、パディングの前にすべての文字列に架空の非ゼロ（たとえば、1）文字を追加するのが最善であることに注意してください。これにより、普遍性が影響を受けないことが保証されます。^[15]${\displaystyle h(s)}$${\displaystyle s}$

ここで、 をハッシュしたいとします。ここで、 の適切な境界は事前にはわかっていません。^[12]によって提案された普遍的な族は、 文字列を大きな素数を法とする多項式の係数として扱います。 の場合、を素数として定義します。 ${\displaystyle {\bar {x}}=(x_{0},\dots ,x_{\ell })}$${\displaystyle \ell }$${\displaystyle x}$${\displaystyle x_{i}\in [u]}$${\displaystyle p\geq \max\{u,m\}}$

${\displaystyle h_{a}({\bar {x}})=h_{\mathrm {int} }\left({\big (}\sum _{i=0}^{\ell }x_{i}\cdot a^{\ell -i}{\big )}{\bmod {~}}p\right)}$ここで、は一様ランダムであり、 は整数領域 をマッピングする普遍族からランダムに選択されます。${\displaystyle a\in [p]}$${\displaystyle h_{\mathrm {int} }}$${\displaystyle [p]\mapsto [m]}$

モジュラー算術の性質を利用すると、大きな文字列に対して大きな数値を生成することなく上記を計算することができる。^[16]

uint hash ( String x , int a , int p ) uint h = INITIAL_VALUE for ( uint i = 0 ; i < x . length ; ++ i ) h = (( h * a ) + x [ i ]) mod p return h      
	   
	        
		      
	 

このラビン・カープ・ローリング・ハッシュは線形合同法生成器に基づいています。^{[17]上記のアルゴリズムは}乗法ハッシュ関数 としても知られています。^[18]実際には、多くのプログラミング言語ではmod ( Max-Int-Value + 1) と同等であるため、整数のオーバーフローを許可するだけで、 mod演算子とパラメーターp を完全に回避できます。以下の表は、一般的な実装のいくつかでhと a を初期化するために選択された値を示しています。

2 つの文字列を考えて、長い方の長さを とします。解析では、短い方の文字列に概念的に長さ までゼロが埋め込まれます。を適用する前の衝突は、 が係数を持つ多項式の根であることを意味します。この多項式にはを法とする根が最大で 個あるため、衝突確率は最大で 個です。ランダムによる衝突の確率により、全体の衝突確率は になります。したがって、素数がハッシュされた文字列の長さに比べて十分に大きい場合、族はユニバーサルに非常に近くなります (統計的距離において)。 ${\displaystyle {\bar {x}},{\bar {y}}}$${\displaystyle \ell }$${\displaystyle \ell }$${\displaystyle h_{\mathrm {int} }}$${\displaystyle a}$${\displaystyle {\bar {x}}-{\bar {y}}}$${\displaystyle \ell }$${\displaystyle p}$${\displaystyle \ell /p}$${\displaystyle h_{\mathrm {int} }}$${\displaystyle {\frac {1}{m}}+{\frac {\ell }{p}}}$${\displaystyle p}$

長さが不明な文字列を固定長のハッシュ値にハッシュするために使用される他の汎用ハッシュ関数ファミリには、Rabin フィンガープリントやBuzhashなどがあります。

モジュラー演算の計算ペナルティを軽減するために、実際には3つのトリックが使用されています。^[11]

1. 素数は、メルセンヌ素数のように、2 の累乗に近いものを選択します。これにより、除算を使わずに (加算やシフトなどのより高速な演算を使用して) を法とする算術演算を実装できます。たとえば、最新のアーキテクチャでは を使用できますが、は 32 ビット値です。${\displaystyle p}$${\displaystyle p}$${\displaystyle p=2^{61}-1}$${\displaystyle x_{i}}$
2. ブロックにベクトル ハッシュを適用できます。たとえば、文字列の 16 ワード ブロックごとにベクトル ハッシュを適用し、その結果に文字列ハッシュを適用します。より遅い文字列ハッシュがかなり小さいベクトルに適用されるため、これは基本的にベクトル ハッシュと同じくらい高速になります。${\displaystyle \lceil k/16\rceil }$
3. 除数として 2 の累乗を選択すると、除算を行わずに算術モジュロを実装できます (ビット マスキングの高速演算を使用)。NHハッシュ関数ファミリはこのアプローチを採用しています。${\displaystyle 2^{w}}$

• K独立ハッシュ – ハッシュ関数のファミリー
• ローリングハッシュ – ハッシュ関数の種類Pages displaying short descriptions of redirect targets
• タブレーションハッシュ – 排他的論理和で計算されるハッシュ関数
• 最小独立性 – データマイニング技術Pages displaying short descriptions of redirect targets
• ユニバーサル一方向ハッシュ関数 - 衝突耐性ハッシュ関数の代替として提案された暗号におけるユニバーサルハッシュ関数の一種Pages displaying wikidata descriptions as a fallback
• 低矛盾シーケンス – 数学的シーケンスのタイプ
• 完全なハッシュ – 衝突のないハッシュ関数Pages displaying short descriptions of redirect targets

• ドナルド・アービン・クヌース(1998)。『コンピュータプログラミングの技法、第3巻：ソートと検索（第3版）』。マサチューセッツ州レディング、ロンドン：アディソン・ウェスレー。ISBN 0-201-89685-0。

• オープン データ構造 - セクション 5.1.1 - 乗法ハッシュ、Pat Morin