ハッシュ関数

ハッシュ関数は、任意のサイズのデータ​​を固定サイズの値にマッピングするために使用できる関数ですが、可変長出力をサポートするハッシュ関数もいくつかあります。^[1]ハッシュ関数によって返される値は、ハッシュ値、ハッシュコード、ハッシュダイジェスト、ダイジェスト、または単にハッシュと呼ばれます。^{[2]値は通常、}ハッシュテーブル と呼ばれる固定サイズのテーブルのインデックスに使用されます。ハッシュ関数を使用してハッシュテーブルをインデックスすることを、ハッシュ化または分散ストレージアドレス指定と呼びます。

ハッシュ関数とそれに関連するハッシュ テーブルは、データ ストレージおよび検索アプリケーションで使用され、1 回の取得につき短時間でほぼ一定の時間でデータにアクセスします。ハッシュ関数とそれに関連するハッシュ テーブルには、データまたはレコード自体に必要な合計スペースよりほんの少し大きいストレージ スペースが必要です。ハッシュは、計算とストレージ スペースを効率的に使用するデータ アクセス形式であり、順序付きリストや順序なしリスト、構造化ツリーの一定でないアクセス時間や、大きなキーや可変長キーの状態空間への直接アクセスでしばしば指数関数的に必要となるストレージ要件を回避します。

ハッシュ関数の使用は、キーと関数の相互作用の統計的特性に依存している。最悪の場合の動作は許容できないほど悪いがまれであり、平均的な場合の動作はほぼ最適である（衝突が最小限）。^{[3] ：527}

ハッシュ関数は、チェックサム、チェックディジット、フィンガープリント、非可逆圧縮、ランダム化関数、エラー訂正コード、暗号と関連しており、しばしば混同されます。これらの概念はある程度重複していますが、それぞれに独自の用途と要件があり、設計と最適化も異なります。ハッシュ関数は、主にデータの整合性の点でこれらの概念と異なります。ハッシュテーブルは非暗号ハッシュ関数を使用することがありますが、暗号ハッシュ関数はサイバーセキュリティでパスワードなどの機密データを保護するために使用されます。

ハッシュ テーブルでは、ハッシュ関数はキーを入力として受け取ります。キーはデータまたはレコードに関連付けられ、データ ストレージおよび取得アプリケーションでデータまたはレコードを識別するために使用されます。キーは、整数のように固定長の場合もあれば、名前のように可変長の場合もあります。場合によっては、キーはデータそのものです。出力は、データまたはレコード、またはそれらへのポインターを保持するハッシュ テーブルのインデックス付けに使用されるハッシュ コードです。

ハッシュ関数は、次の 3 つの機能を実行すると考えられます。

• ADDやXORなどのパリティ保存演算子を使用して、可変長キーをワードまたはその他の単位で折り返し、固定長（通常はマシンワード長以下）の値に変換します。
• 鍵のビットをスクランブルして、結果の値が鍵空間全体に均一に分散されるようにし、
• キー値をテーブルのサイズ以下のサイズにマップします。

優れたハッシュ関数は、2 つの基本的な特性を満たしています。計算が非常に高速であることと、出力値の重複 (衝突)が最小限に抑えられることです。ハッシュ関数は、その有効性のために好ましい確率分布を生成することにより、アクセス時間をほぼ一定に短縮します。テーブル負荷係数が高い場合、キー セットが異常な場合、ハッシュ関数の設計が不十分な場合、アクセス時間がテーブル内の項目数にほぼ比例する可能性があります。ハッシュ関数は、最悪のケースで最良のパフォーマンスを発揮するように設計でき、^{[注 1]}テーブル負荷係数が高い場合でも良好なパフォーマンスを発揮し、特殊な場合には、キーをハッシュ コードに完全に (衝突なしで) マッピングできます。実装は、パリティ保存ビット演算 (XOR および ADD)、乗算、または除算に基づいています。ハッシュ関数に必要な補助機能は、リンク リストなどの補助データ構造を使用する衝突解決方法、または空のスロットを見つけるためのテーブルの体系的なプローブです。

ハッシュ関数は、ハッシュ テーブルと組み合わせて、データ項目またはデータ レコードを保存および取得するために使用されます。ハッシュ関数は、各データまたはレコードに関連付けられたキーをハッシュ コードに変換し、ハッシュ テーブルのインデックス作成に使用されます。テーブルに項目を追加する場合、ハッシュ コードは空のスロット (バケットとも呼ばれる) をインデックス作成します。その場合、項目はそこにテーブルに追加されます。ハッシュ コードが満杯のスロットをインデックス作成する場合、何らかの衝突解決が必要です。新しい項目は省略される (テーブルに追加されない) か、古い項目と置き換わるか、指定された手順によってテーブルの他の場所に追加されます。その手順は、ハッシュ テーブルの構造によって異なります。連鎖ハッシュでは、各スロットはリンク リストまたはチェーンの先頭であり、スロットで衝突する項目はチェーンに追加されます。チェーンはランダムな順序で保持され、線形に検索されるか、シリアル順序で検索されるか、またはアクセスを高速化するために頻度による自己順序付けリストとして検索されます。オープン アドレス ハッシュでは、テーブルは占有スロットから指定された方法でプローブされます。通常は、線形プローブ、二次プローブ、または二重ハッシュによって、オープン スロットが見つかるか、テーブル全体がプローブされるまで (オーバーフロー) プローブされます。アイテムの検索は、アイテムが見つかるか、オープン スロットが見つかるか、テーブル全体が検索されるまで (アイテムがテーブルにない)、同じ手順で行われます。

ハッシュ関数は、低速メディアに保存された大規模なデータセットのキャッシュを構築するためにも使用されます。キャッシュは、衝突が発生した場合、古い方のアイテムを破棄するか書き戻すことで解決できるため、ハッシュ検索テーブルよりも一般的に単純です。^[4]

ハッシュ関数は、要素が集合のメンバーであるかどうかをテストするために使用される、空間効率の高い確率的データ構造であるブルーム フィルタの重要な要素です。

ハッシュの特殊なケースは、幾何ハッシュまたはグリッド法として知られています。これらのアプリケーションでは、すべての入力の集合はある種の距離空間であり、ハッシュ関数はその空間をセルのグリッドに分割するものと解釈できます。テーブルは多くの場合、2 つ以上のインデックス (グリッド ファイル、グリッド インデックス、バケット グリッドなどと呼ばれる) を持つ配列であり、ハッシュ関数はインデックスタプルを返します。この原理は、コンピュータ グラフィックス、計算幾何学、およびその他の多くの分野で、点の集合内で最も近いペア、形状のリスト内で類似の形状、画像データベース内で類似の画像を見つけるなど、平面または3 次元空間での多くの近接問題を解決するために広く使用されています。

ハッシュテーブルは連想配列や動的セットの実装にも使用されます。^[5]

優れたハッシュ関数は、予想される入力を出力範囲にわたって可能な限り均等にマッピングする必要があります。つまり、出力範囲のすべてのハッシュ値は、ほぼ同じ確率で生成される必要があります。この最後の要件の理由は、衝突の数(同じハッシュ値にマッピングされる入力のペア) が増加すると、ハッシュベースの方法のコストが急激に増加するためです。一部のハッシュ値が他のハッシュ値よりも発生する可能性が高い場合、検索操作の大部分で、衝突するテーブル エントリのより大きなセットを検索する必要があります。

この基準では、値が均一に分布していることのみが求められ、いかなる意味でもランダムであることは求められません。優れたランダム化関数は（計算効率に関する懸念を除けば）ハッシュ関数として一般的に適切な選択ですが、その逆は必ずしも真である必要はありません。

ハッシュ テーブルには、有効な入力のごく一部しか含まれないことがよくあります。たとえば、クラブの会員リストには、考えられるすべての名前の非常に大きなセットのうち、100 人程度の会員名しか含まれていない場合があります。このような場合、均一性基準は、考えられるすべてのエントリのグローバル セットだけでなく、テーブルで見つかる可能性のあるエントリのほぼすべての典型的なサブセットに当てはまる必要があります。

言い換えれば、典型的なm 個のレコードのセットがn 個のテーブル スロットにハッシュされる場合、バケットがm / n個を超えるレコードを受信する確率は無視できるほど小さくなるはずです。特に、m < nの場合、1 つまたは 2 個を超えるレコードを持つバケットはほとんどありません。 nがmよりはるかに大きい場合でも、少数の衝突は事実上避けられません。誕生日問題を参照してください。

キーが事前にわかっていてキー セットが静的である特殊なケースでは、絶対的な (または衝突のない) 均一性を実現するハッシュ関数が見つかることがあります。このようなハッシュ関数は完全であるといわれます。このような関数を構築するアルゴリズム的な方法はありません。そのような関数の検索は、マップされるキーの数と、それらがマップされるテーブル スロットの数の階乗関数です。非常に小さなキー セット以上で完全なハッシュ関数を見つけることは、通常、計算上不可能です。結果として得られる関数は、標準のハッシュ関数よりも計算が複雑になる可能性が高く、衝突数が最小になる統計特性の優れた関数に比べて、わずかな利点しかありません。ユニバーサル ハッシュ関数を参照してください。

ハッシュ関数をテストする場合、ハッシュ値の分布の均一性はカイ二乗検定によって評価できます。この検定は適合度の尺度です。つまり、バケット内のアイテムの実際の分布と、アイテムの期待される（または均一な）分布を比較します。式は次のとおりです。

${\displaystyle {\frac {\sum _{j=0}^{m-1}(b_{j})(b_{j}+1)/2}{(n/2m)(n+2m-1)}},}$

ここで、nはキーの数、mはバケットの数、b _{j は}バケットj内のアイテムの数です。

1 つの信頼区間内の比率 (0.95 ～ 1.05 など) は、評価されたハッシュ関数が予想される均一分布を持つことを示します。

ハッシュ関数には、適用時に均一な分布になる可能性を高める技術的な特性がいくつかあります。1 つは厳密なアバランシェ基準です。単一の入力ビットが補完されるたびに、各出力ビットが 50% の確率で変化します。この特性の理由は、キースペースの選択されたサブセットの変動性が低い場合があるためです。出力が均一に分散されるためには、たとえ 1 ビットであっても、変動性が低いと、出力の変動性 (つまり、テーブルスペース全体にわたる分布) が高くなる必要があります。各ビットは 50% の確率で変化する必要があります。なぜなら、一部のビットが変化に消極的であれば、キーはそれらの値の周りに集中するからです。ビットがあまりにも容易に変化しようとすると、マッピングは単一ビットの固定 XOR 関数に近づきます。この特性の標準的なテストは文献に記載されています。^[6] この基準の乗法ハッシュ関数への関連性は、ここで評価されます。^[7]

データの保存および取得アプリケーションでは、ハッシュ関数の使用は、検索時間とデータ保存スペースのトレードオフになります。検索時間が無制限であれば、非常にコンパクトな順序なし線形リストが最適な媒体になります。保存スペースが無制限であれば、キー値でインデックス可能なランダムアクセス可能な構造は非常に大きく、非常にまばらになりますが、非常に高速になります。ハッシュ関数は、潜在的に大きなキースペースを、キーの数に関係なく、限られた時間で検索可能な実行可能な量の保存スペースにマッピングするのに、限られた時間がかかります。ほとんどのアプリケーションでは、ハッシュ関数は、最小のレイテンシで、次に最小数の命令で計算可能である必要があります。

計算の複雑さは、必要な命令の数と個々の命令の待ち時間によって変わります。最も単純なのはビット単位の方法 (折りたたみ) で、次に乗算法、最も複雑 (最も遅い) なのは除算ベースの方法です。

衝突はまれであり、わずかな遅延を引き起こすものの、それ以外は無害であるため、通常は、より多くの計算を必要とするものの衝突を少ししか防げないハッシュ関数よりも、より高速なハッシュ関数を選択することが望ましいです。

除算ベースの実装は、ほぼすべてのプロセッサ マイクロアーキテクチャで除算に複数のサイクルが必要なため、特に懸念される可能性があります。定数による除算 (モジュロ) は、その定数のワード サイズの逆数による乗算に反転できます。これは、プログラマまたはコンパイラによって実行できます。除算は、一連のシフト減算とシフト加算に直接減らすこともできますが、必要なこのような操作の数を最小限に抑えることは困難な問題です。結果として生じる機械語命令の数は 12 を超え、パイプラインを圧倒する可能性があります。マイクロアーキテクチャにハードウェア乗算 機能ユニットがある場合は、逆数による乗算の方がおそらくより適切なアプローチです。

テーブル サイズn が2 の累乗でなくても、剰余や除算を実行する必要はありません。これらの計算はコストがかかることがあるためです。たとえば、n が2 ^bより大幅に小さいとします。区間[0, 2 ^b  − 1]で均一な疑似乱数生成関数P (key)を考えます。区間[0, n − 1]で均一なハッシュ関数はn P (key) / 2 ^bです。除算を (おそらくより高速な) 右ビット シフトで置き換えることができます。n P (key) >> b。

キーが繰り返しハッシュ化され、ハッシュ関数のコストが高い場合は、ハッシュ コードを事前に計算してキーとともに保存することで計算時間を節約できます。ハッシュ コードが一致するということは、キーが同一である可能性がほぼ確実です。この手法は、ボードの位置の 64 ビット ハッシュ表現を保存するゲーム プログラムの転置テーブルに使用されます。

ユニバーサルハッシュ方式は、任意の 2 つの異なるキーの衝突確率が1/ mとなるような関数のファミリーからハッシュ関数h を選択するランダム アルゴリズムです。ここで、m は、2 つのキーとは無関係に、必要な異なるハッシュ値の数です。ユニバーサル ハッシュは、入力データの分布に関係なく、ハッシュ関数のアプリケーションがランダム関数を使用している場合と同じように動作することを (確率的な意味で) 保証します。ただし、完全なハッシュよりも衝突が多くなり、専用ハッシュ関数よりも多くの操作が必要になる場合があります。

特定のテーブル サイズのみ、または特定の長さまでの文字列のみを許可するハッシュ関数、またはシードを受け入れることができないハッシュ関数 (つまり、二重ハッシュを許可するハッシュ関数) は、シードを受け入れるハッシュ関数よりも有用性が低くなります。^{[引用が必要]}

ハッシュ関数はさまざまな状況で応用できます。特に暗号化においては、注目すべき応用として次のようなものがあります。^[8]

• 整合性チェック: 異なるファイルのハッシュ値が同一であれば、それは等価性を意味し、ファイルの変更を検出するための信頼性の高い手段を提供します。
• キー導出: 入力を少し変更すると、ランダムに見える出力の変化が生じます。これは拡散特性として知られています。したがって、ハッシュ関数はキー導出関数に役立ちます。
• メッセージ認証コード(MAC): ハッシュ関数は、秘密キーを入力データと統合することにより、 HMACなどのデータの真正性を保証する MAC を生成できます。
• パスワードの保存: パスワードのハッシュ値ではパスワードの詳細が公開されないため、ハッシュされたパスワードをサーバー上に安全に保存することの重要性が強調されます。
• 署名: メッセージ全体ではなく、メッセージ ハッシュが署名されます。

ハッシュ プロシージャは決定論的である必要があります。つまり、与えられた入力値に対して、常に同じハッシュ値を生成する必要があります。言い換えると、ハッシュ プロシージャは、数学的な意味でハッシュされるデータの関数である必要があります。この要件により、疑似乱数ジェネレータや時刻などの外部変数パラメータに依存するハッシュ関数は除外されます。また、ハッシュされるオブジェクトのメモリ アドレスに依存する関数も除外されます。これは、アドレスが実行中に変更される可能性があるためです (ガベージ コレクションの特定の方法を使用するシステムで発生する可能性があります)。ただし、アイテムの再ハッシュは可能な場合もあります。

決定論は関数の再利用の文脈にあります。たとえば、Pythonはハッシュ関数がハッシュされる入力に加えてPythonプロセスの開始時に一度生成されるランダムシードを利用する機能を追加します。^[9] Pythonハッシュ（SipHash）は、1回の実行内で使用される場合は有効なハッシュ関数ですが、値が永続化されている場合（たとえば、ディスクに書き込まれる場合）、次の実行ではランダム値が異なる可能性があるため、有効なハッシュ値として扱うことができなくなります。

ハッシュ関数の出力は固定サイズであることが望ましい場合が多い（ただし、下記参照）。たとえば、出力が 32 ビットの整数値に制限されている場合、ハッシュ値を使用して配列にインデックスを付けることができます。このようなハッシュは、データ検索を高速化するためによく使用されます。^[10]可変長の入力から固定長の出力を生成するには、入力データを特定のサイズのチャンクに分割します。データ検索に使用されるハッシュ関数は、入力のチャンク（文字列内の文字など）を反復的に処理してハッシュ値を生成する算術式を使用します。^[10]

多くのアプリケーションでは、ハッシュ値の範囲はプログラムの実行ごとに異なる場合や、同じ実行中に変更される場合があります (たとえば、ハッシュ テーブルを拡張する必要がある場合)。このような状況では、入力データzと許可されるハッシュ値の数nという 2 つのパラメータを取るハッシュ関数が必要です。

一般的な解決方法は、非常に広い範囲 (たとえば、0から2 ³²  − 1 ) で固定ハッシュ関数を計算し、その結果をnで割り、割り算の余りを使用することです。n自体が2の累乗である場合は、ビット マスキングとビット シフトによってこれを行うことができます。この方法を使用する場合、ハッシュ関数は、アプリケーションで発生する可能性のあるnの任意の値に対して、結果が0からn  − 1 の間でほぼ均一に分布するように選択する必要があります。関数によっては、余りがnの特定の値 (奇数や素数など)に対してのみ均一になる場合があります。

ハッシュ関数を使用して、プログラムの実行後も存続するハッシュ テーブルに値を格納し、ハッシュ テーブルを拡張または縮小する必要がある場合、そのハッシュ テーブルは動的ハッシュ テーブルと呼ばれます。

テーブルのサイズが変更されたときに、最小限の数のレコードを再配置するハッシュ関数が望ましいです。必要なのは、 n /( n + 1) に近い確率で H ( z , n + 1) = H ( z , n ) となるようなハッシュ関数H ( z , n )  (ここで、 zはハッシュされるキー、 nは許可されるハッシュ値の数) です。

線形ハッシュとスパイラルハッシュは、定数時間で実行されるが、最小移動特性を実現するために均一性の特性を緩和する動的ハッシュ関数の例です。拡張可能ハッシュは、ハッシュ関数を計算するためにnに比例するスペースを必要とする動的ハッシュ関数を使用し、ハッシュ関数は挿入された以前のキーの関数になります。均一性特性を維持しながら、H ( z、n )の値を計算するためにnに比例する時間を必要とするアルゴリズムがいくつか発明されています。^{[説明が必要]}

移動が最小限のハッシュ関数は、分散ハッシュ テーブルで特に役立ちます。

アプリケーションによっては、入力データに比較には関係のない特徴が含まれている場合があります。たとえば、個人名を検索する場合、大文字と小文字の区別を無視することが望ましい場合があります。このようなデータの場合、使用されているデータ同等性基準と互換性のあるハッシュ関数を使用する必要があります。つまり、同等と見なされる 2 つの入力は、同じハッシュ値を生成する必要があります。これは、すべての文字を大文字にするなど、ハッシュする前に入力を正規化することで実現できます。

整数をハッシュするための一般的なアルゴリズムはいくつかあります。最適な分散を実現する方法はデータに依存します。実際に最も単純で最も一般的な方法の 1 つは、モジュロ除算法です。

ハッシュするデータが十分に小さい場合は、データ自体 (整数として再解釈) をハッシュ値として使用できます。このアイデンティティハッシュ関数の計算コストは​​実質的にゼロです。このハッシュ関数は、各入力を個別のハッシュ値にマッピングするため、 完全です。

「十分に小さい」の意味は、ハッシュ値として使用される型のサイズによって異なります。たとえば、Javaでは、ハッシュ コードは 32 ビットの整数です。したがって、32 ビットの整数Integerと 32 ビットの浮動小数点Floatオブジェクトでは値を直接使用できますが、64 ビットの整数Longと 64 ビットの浮動小数点ではDouble使用できません。

他のタイプのデータでも、このハッシュ方式を使用できます。たとえば、大文字と小文字の間で文字列をマッピングする場合、各文字のバイナリエンコードを整数として解釈して、その文字の代替形式 (「a」の場合は「A」、「8」の場合は「8」など) を示すテーブルをインデックス化できます。各文字が 8 ビットで格納されている場合 (拡張 ASCII ^{[注 2]}またはISO Latin 1の場合)、テーブルには 2 ⁸ = 256 エントリしかありません。Unicode 文字の場合、テーブルには17 × 2 ¹⁶ =1 114 112エントリ。

同じ手法を使用して、 「us」や「za」などの2文字の国コードを国名（26 ² = 676のテーブルエントリ）にマッピングしたり、13083などの5桁の郵便番号を都市名（無効なデータ値 (国コード「xx」や郵便番号 00000 など) は、テーブル内で未定義のままにされるか、適切な「null」値にマッピングされ ます。

キーがキー空間全体に均一または十分に均一に分散され、キー値が本質的にランダムである場合、キーはすでに「ハッシュ」されていると見なすことができます。この場合、キー内の任意の数の任意のビットを抽出し、ハッシュ テーブルのインデックスとして照合することができます。たとえば、単純なハッシュ関数では、最下位のmビットをマスクし、その結果をサイズ2 ^mのハッシュ テーブルのインデックスとして使用できます。

ミッドスクエアハッシュコードは、入力を2乗し、適切な数の中間の数字またはビットを抽出することによって生成されます。たとえば、入力が123 456 789とハッシュテーブルのサイズ10 000の場合、キーを2乗すると15 241 578 750 190 521なので、ハッシュ コードは 17 桁の数字 (上位桁は無視) の真ん中の 4 桁である 8750 になります。キーの先頭または末尾にゼロがあまりない場合、中央の 2 乗法では適切なハッシュ コードが生成されます。これは乗法ハッシュのバリエーションですが、任意のキーは適切な乗数ではないため、それほど適切ではありません。

標準的な手法は、テーブル サイズに近い素数である除数M を選択してキーにモジュロ関数を使用することです。つまり、 h ( K ) ≡ K (mod M )です。テーブル サイズは通常 2 の累乗です。これにより、{0, M − 1}の分布が得られます。これにより、多数のキー セットに対して良好な結果が得られます。除算ハッシュの大きな欠点は、除算がほとんどの最新アーキテクチャ ( x86を含む) で複数のサイクルを必要とし、乗算よりも 10 倍遅くなる可能性があることです。2 つ目の欠点は、クラスター化されたキーを分割しないことです。たとえば、123000、456000、789000 などのキーは、1000 を法としてすべて同じアドレスにマップされます。多くのキー セットは既に十分にランダムであり、キー セットが大きな素数によって循環する確率は小さいため、この手法は実際にはうまく機能します。

代数的符号化はハッシュの除算法の変形であり、整数の代わりに 2 を法とする多項式による除算を使用してnビットをmビットにマッピングします。^{[3] : 512–513}このアプローチでは、M = 2 ^mであり、m次多項式Z ( x ) = x ^m + ζ _{m −1} x ^{m −1} + ⋯ + ζ ₀を仮定します。キーK = ( k _{n −1} … k ₁ k ₀ ) _{2 は}、多項式K ( x ) = k _{n −1} x ^{n −1} + ⋯ + k ₁ x + k ₀と見なすことができます。2 を法とする多項式演算を使用した剰余は、K ( x ) mod Z ( x ) = h _{m −1} x ^{m −1} + ⋯ h ₁ x + h ₀です。このとき、h ( K ) = ( h _{m −1} … h ₁ h ₀ ) _{2 と}なる。Z ( x ) がt個以下の非ゼロ係数を持つように構築されている場合、 tビット未満のキーは衝突しないことが保証される。

Z はk、t、n（最後の n は2 ^k − 1の約数）の関数であり、有限体 GF(2 ^k )から構成されます。Knuth は例を挙げています。( n、m、t ) = (15,10,7)とすると、 Z ( x ) = x ¹⁰ + x ⁸ + x ⁵ + x ⁴ + x ² + x + 1となります。導出は次のとおりです。

Sを{1,2,…, t }⊆Sかつ( 2 j mod n ) ∈S ∀ j∈Sとなるような最小の整数集合とする。^[注3]

α ∈ ⁿ GF(2 ^k )でP ( x )の係数がこの体で計算される場合に定義します。するとP ( x )の次数= | S | となります。α ^jが根であるときはいつでもα ^{2 j}はP ( x )の根であるため、 P ( x )の係数p ^{i は}p を満たすことになります。${\displaystyle P(x)=\prod _{j\in S}(x-\alpha ^{j})}$²
_私= p _iなので、すべて 0 か 1 です。R ( x ) = r _{n −1} x ^{n −1} + ⋯ + r ₁ x + r ₀が 2 を法とする任意の非ゼロ多項式で、非ゼロ係数が最大t個ある場合、 R ( x ) は2 を法とするP ( x )の倍数ではありません。 ^{[注 4]の場合、対応するハッシュ関数は、共通するビットが}t 未満のキーを一意のインデックスにマッピングします。^{[3] : 542–543}

通常、この方式が計算上実行可能となるには、nが大きくなるか、tが大きくなるか、あるいはその両方が成立する。したがって、この方式はハードウェアまたはマイクロコードの実装に適している。^{[3] : 542–543}

ユニーク順列ハッシュ法は、最悪のケースでも最良挿入時間が保証されている。^[11]

標準的な乗法ハッシュでは、式h _a ( K ) = ⌊ ( aK mod W ) / ( W / M ) ⌋を使用し、 {0, …, M − 1}のハッシュ値を生成します。値aは、適切に選択された値で、Wと互いに素である必要があります。また、大きくなければならず^{[明確化が必要]}、そのバイナリ表現は 1 と 0 のランダムな混合^{[明確化が必要]}である必要があります。重要な実用的な特別なケースは、W = 2 ^wおよびM = 2 ^mが 2 の累乗で、w がマシンワードサイズである場合に発生します。この場合、この式はh _a ( K ) = ⌊ ( aK mod 2 ^w ) / 2 ^{w − m} ⌋になります。これが特別なのは、低レベルのプログラミング言語では2 ^{w を}法とする算術がデフォルトで実行され、2 の累乗による整数の除算は単に右シフトであるためです。そのため、たとえばCでは、この関数は次のようになります。

符号なしハッシュ(符号なしK) {
   (a*K) >> (wm) を返します。
}

mとw が固定されている場合、これは単一の整数乗算と右シフトに変換され、計算が最も高速なハッシュ関数の 1 つになります。

乗法ハッシュは「よくある間違い」の影響を受けやすく、拡散が悪くなります。つまり、高い値の入力ビットが、低い値の出力ビットに影響を与えないのです。^[12] 入力の変換により、保持された上位ビットの範囲がシフトダウンされ、乗算ステップの前にキーにXORまたはADDが実行されます。結果の関数は次のようになります。^[7]

符号なしハッシュ(符号なしK) {
   K ^= K >> (wm);
   (a*K) >> (wm) を返します。
}

フィボナッチハッシュは乗法ハッシュの一種で、乗数は2 ^w / ϕです。ここで、wはマシン ワード長、ϕ (ファイ) は黄金比(約 1.618) です。この乗数の特性は、キー内の任意のビット ブロックに関して、連続するキーのブロックをテーブル スペース全体に均一に分散することです。キーの上位ビットまたは下位ビット (またはその他のフィールド) 内の連続するキーは比較的一般的です。さまざまなワード長の乗数は次のとおりです。

• 16: a =9E37 ₁₆=40 503 ₁₀
• 32 : =9E37 79B9 ₁₆=2 654 435 769 ₁₀
• 48: a =9E37 79B9 7F4B ₁₆=173 961 102 589 771 ₁₀ ^[注5]
• 64 : =9E37 79B9 7F4A 7C15 ₁₆=11 400 714 819 323 198 485 ₁₀

乗数は奇数である必要があるため、出力の最下位ビットは2 ^{w を}法として反転可能です。これを実現するために、上記の最後の 2 つの値は、最下位ビットの 1/2 以上で切り上げと切り下げが行われます。

タブレーションハッシュ法は、アルバート・ゾブリストにちなんでゾブリストハッシュ法とも呼ばれ、テーブル検索とXOR演算を組み合わせてハッシュ関数の汎用ファミリーを構築する手法である。このアルゴリズムは、ハッシュ目的（特に整数キーのハッシュ）で非常に高速かつ高品質であることが証明されている。^[13]

ゾブリスト ハッシュは、もともとはコンピュータ ゲーム プログラムでチェスの位置を簡潔に表現する手段として導入されました。盤上の各スペースにある各タイプの駒 (黒と白にそれぞれ 6 つずつ) を表すために、一意の乱数が割り当てられました。したがって、プログラムの開始時に、64×12 のそのような数値のテーブルが初期化されます。乱数の長さは任意ですが、盤上の 64 個のマス目を考えると、64 ビットが自然です。位置は、位置にある駒を循環し、対応する乱数をインデックス化し (計算に空きスペースは含めない)、それらを XOR することで転写されます (開始値は 0 (XOR の単位値) またはランダム シードにすることができます)。結果の値は、モジュロ、フォールディング、またはその他の操作によって減算され、ハッシュ テーブル インデックスが生成されます。元のゾブリスト ハッシュは、位置の表現としてテーブルに格納されます。

その後、この方法は、ワード内の 4 つの位置のそれぞれのバイトを一意の 32 ビット乱数で表すことによって、整数のハッシュに拡張されました。このようにして、2 ⁸ ×4 乱数のテーブルが構築されます。32 ビットのハッシュ整数は、プレーン テキスト整数の各バイトの値でテーブルを連続的にインデックスし、ロードされた値を排他的論理和することで転写されます (この場合も、開始値は ID 値またはランダム シードになります)。64 ビット整数への自然な拡張は、2 ⁸ ×8 64 ビット乱数のテーブルを使用することです。

この種の関数には優れた理論的特性がいくつかあります。そのうちの 1 つは3 組の独立性と呼ばれ、これは、すべての 3 組のキーが任意の 3 組のハッシュ値に等しくマッピングされることを意味します。

ハッシュ関数は、キーの既存のエントロピーを利用するように設計できます。キーの先頭または末尾にゼロがある場合、または特定のフィールドが未使用、常にゼロまたはその他の定数である場合、または全体的にほとんど変化しない場合は、揮発性ビットのみをマスクしてハッシュすると、より優れた、おそらくより高速なハッシュ関数が提供されます。キーが循環的であるか、その他の冗長性がある場合、除算および乗算スキームで選択された除数または乗数は、より均一なハッシュ関数を作成する可能性があります。

データ値が長い（または可変長の）文字列（個人名、Web ページのアドレス、メール メッセージなど）である場合、その分布は通常非常に不均一で、依存関係が複雑です。たとえば、自然言語のテキストには、その言語特有の文字、文字ペア、文字の分布が非常に不均一です。このようなデータの場合、文字列のすべての文字に依存し、各文字に異なる方法で依存するハッシュ関数を使用するのが賢明です。^{[説明が必要]}

単純なハッシュ関数は、文字列の最初と最後のn文字を長さとともに追加するか、文字列の中央の 4 文字からワード サイズのハッシュを形成します。これにより、(長くなる可能性のある) 文字列の反復処理が省かれますが、文字列のすべての文字をハッシュしないハッシュ関数は、キー セット内の冗長性、クラスタリング、またはその他の異常により、すぐに線形になる可能性があります。このような戦略は、キーの構造が中央、末尾、またはその他のフィールドのいずれかがゼロであるか、キーを区別しないその他の不変定数である場合に、カスタム ハッシュ関数として効果的である可能性があります。その場合、キーの不変部分は無視できます。

文字による折りたたみの典型的な例は、文字列内のすべての文字の整数値を加算することです。より良いアイデアは、オーバーフローを無視して、次の文字を追加する前に、ハッシュの合計に定数 (通常はかなり大きな素数) を掛けることです。加算の代わりに排他的論理和を使用するのも妥当な代替策です。最終操作は、モジュロ、マスク、またはその他の関数で、単語の値をテーブルのサイズのインデックスに減らします。この手順の弱点は、情報がバイトの上位ビットまたは下位ビットに集まる可能性があることです。この集まりはハッシュ結果に残り、適切なランダム化ハッシュよりも多くの衝突を引き起こします。たとえば、ASCII バイト コードの上位ビットは 0 で、印刷可能な文字列は最後のバイト コードまたは最初の 32 バイト コードの大部分を使用しないため、残りのバイト コードを使用する情報は、わかりにくい方法で残りのビットに集まります。

1970 年代にベル研究所でピーター J. ワインバーガーが行った研究に基づいてPJW ハッシュと呼ばれる古典的なアプローチは、もともと「ドラゴン ブック」に記載されているように、識別子をコンパイラ シンボル テーブルにハッシュするために設計されました。^[14]このハッシュ関数は、バイトを合計する前に 4 ビットオフセットします。量がラップすると、上位 4 ビットがシフトされ、ゼロでない場合は累積量の下位バイトにXOR されます。結果は、モジュロまたはその他の縮小演算を適用して最終的なハッシュ インデックスを生成することができるワード サイズのハッシュ コードです。

今日では、特に 64 ビットのワード サイズの出現により、ワード チャンクによるはるかに効率的な可変長文字列ハッシュが利用可能になりました。

現代のマイクロプロセッサでは、8 ビット文字列を 1 文字ずつ処理してハッシュするのではなく、文字列を 32 ビットまたは 64 ビットの整数の配列として解釈し、これらの「ワイド ワード」整数値を算術演算 (定数による乗算やビット シフトなど) によってハッシュ/累積することで、はるかに高速な処理が可能になります。最後のワードには、未使用のバイト位置がある可能性があり、ハッシュに折り込まれる前に、ゼロまたは指定されたランダム化値で埋められます。累積されたハッシュ コードは、最後のモジュロまたはその他の演算によって削減され、テーブルへのインデックスが生成されます。

10 進数を表す ASCII またはEBCDIC文字列を計算用に数値に変換する方法と同様に、可変長文字列はx _{k −1} a ^{k −1} + x _{k −2} a ^{k −2} + ⋯ + x ₁ a + x ₀として変換できます。これは、長さ k の入力文字列の文字として要素( x ₀、x ₁、...、x _{k −1} )を取る、基数 a  > 1の多項式です。これは、ハッシュ コードとして直接使用することも、ハッシュ関数を適用して潜在的に大きな値をハッシュ テーブルのサイズにマッピングすることもできます。a の値は通常、潜在的なキーの文字セット内の異なる文字の数を保持するのに十分な大きさの素数です。文字列の基数変換ハッシュにより、衝突の数が最小限に抑えられます。^[15]使用可能なデータ サイズによって、この方法でハッシュできる文字列の最大長が制限される場合があります。たとえば、128 ビット ワードでは、基数 29 の 26 文字のアルファベット文字列 (大文字と小文字は区別しない) のみがハッシュ化されます。印刷可能な ASCII 文字列は、基数 97 と 64 ビット ワードを使用して 9 文字に制限されます。ただし、アルファベット キーはハッシュ テーブルに格納する必要があるため、通常は適度な長さになります。数値文字列は通常は問題になりません。64 ビットでは、基数 10で10 ¹⁹または 19 桁の 10 進数までカウントできます。

部分文字列検索などの一部のアプリケーションでは、文字列に沿って 幅k文字のウィンドウを進めることで、与えられたn文字の文字列のすべてのk文字の部分文字列に対してハッシュ関数h を計算できます。ここで、 k は固定整数で、n > kです。テキスト内のすべての文字位置でそのような部分文字列を抽出し、h を個別に計算するという簡単な解決策では、 k · nに比例する操作の数が必要になります。ただし、 hを適切に選択すると、ローリングハッシュの手法を使用して、 mk  +  nに比例する労力ですべてのハッシュを計算できます。ここで、m は部分文字列の出現回数です。^{[16] [ h の選択は何ですか? ]}

このタイプの最もよく知られているアルゴリズムは、Rabin-Karpであり、最良および平均的なケースのパフォーマンスはO ( n + mk )、最悪のケースはO ( n · k )です (公平に言えば、ここでの最悪のケースは極めて異常です。つまり、テキスト文字列と部分文字列の両方が、t ="AAAAAAAAAAAA" やs ="AAA" などの単一の文字の繰り返しで構成されています)。このアルゴリズムに使用されるハッシュ関数は通常、 8 ビット文字列での衝突を回避するように設計されたRabin フィンガープリントですが、他の適切なハッシュ関数も使用されます。

ハッシュ関数の最悪の結果は、理論的な方法と実際的な方法の 2 つの方法で評価できます。理論的な最悪のケースは、すべてのキーが 1 つのスロットにマップされる確率です。実際的な最悪のケースは、予想される最長のプローブ シーケンス (ハッシュ関数 + 衝突解決方法) です。この分析では、ユニフォーム ハッシュ、つまり、任意のキーが確率1/ mで任意の特定のスロットにマップされるというユニバーサル ハッシュ関数の特性を考慮します。

クヌースはリアルタイムシステムに対する敵対的攻撃を懸念しているが、 ^[24]ゴネットはそのようなケースの確率は「途方もなく小さい」ことを示した。彼の表現によれば、n個のキーのうちk個が単一のスロットにマッピングされる確率はα ^k / ( e ^α k !)であり、αは負荷係数n / mである。^[25]

ハッシュという用語は、ハッシュ関数が入力データをかき混ぜて出力を導き出す方法を考えると、非技術的な意味（何かを切り刻む、めちゃくちゃにする）と自然な類似性を提供します。^{[26] : 514}用語の正確な起源に関する研究で、ドナルド・クヌースは、IBMのハンス・ピーター・ルーンが1953年1月のメモでハッシュ関数の概念を最初に使用したように見えるが、その用語自体は、その時点ですでに広く使用されている専門用語であったにもかかわらず、1960年代後半のハーバート・ヘラーマンのデジタルコンピュータシステムの原則まで出版された文献に登場しなかったと指摘しています。^{[26] : 547–548}

• Timo Denk による指定された値のハッシュの計算
• Goulburn ハッシュ関数 ( PDF ) by Mayur Patel
• テキストおよび幾何学的データ検索のためのハッシュ関数の構築 ( PDF ) Latest Trends on Computers、Vol.2、pp. 483–489、CSCC カンファレンス、コルフ、2010