ハッシュ関数

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

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

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

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

優れたハッシュ関数は、想定される入力値を出力範囲全体にできるだけ均等にマッピングする必要があります。つまり、出力範囲内のすべてのハッシュ値は、ほぼ同じ確率で生成されるべきです。この要件の理由は、ハッシュベースの手法では、衝突（同じハッシュ値にマッピングされる入力値のペア）の数が増えるにつれてコストが急激に上昇するためです。一部のハッシュ値が他のハッシュ値よりも発生しやすい場合、ルックアップ操作の大部分は、より多くの衝突するテーブルエントリを検索する必要が生じます。

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

ハッシュテーブルには、有効な入力値のごく一部しか含まれていないことがよくあります。例えば、クラブの会員名簿には、膨大な数の名前の中から、わずか100名程度の名前しか含まれていない場合があります。このような場合、均一性基準は、テーブルに含まれる可能性のある典型的なエントリのサブセットのほぼすべてに対して成り立つべきであり、すべてのエントリの全体に対して成り立つべきではありません。

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

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

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

$${\displaystyle {\frac {m}{n}}{\sum _{j=1}^{m}b_{j}^{2}}-n}$$

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

信頼区間（例えば0.95～1.05）内の比率は、評価されたハッシュ関数が期待される一様分布を持つことを示しています。

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

データストレージおよび検索アプリケーションにおいて、ハッシュ関数の使用は、検索時間とデータストレージ容量のトレードオフとなります。検索時間に制約がなければ、非常にコンパクトな順不同線形リストが最適な手段となります。ストレージ容量に制約がなければ、キーと値でインデックス付け可能なランダムアクセス構造は非常に大きく疎になりますが、非常に高速になります。ハッシュ関数は、キーの数に関係なく、潜在的に大きなキー空間を、限られた時間で検索可能な実行可能なストレージ容量にマッピングするのに有限の時間しかかかりません。ほとんどのアプリケーションでは、ハッシュ関数は最小限のレイテンシで、そして二次的に最小限の命令数で計算可能である必要があります。

計算の複雑さは、必要な命令数と個々の命令の遅延時間によって異なり、最も単純なのはビット演算（畳み込み）であり、次に乗算演算、そして最も複雑（最も遅い）なのは除算演算である。

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

除算に基づく実装は、ほぼすべてのプロセッサマイクロアーキテクチャで除算に複数のサイクルが必要となるため、特に注意が必要です。定数による除算（剰余演算）は、その定数のワードサイズの乗法逆数による乗算に変換できます。これはプログラマまたはコンパイラによって実行できます。除算は、シフト減算とシフト加算の連続に直接還元することもできますが、必要な演算の数を最小限に抑えるのは困難な問題です。結果として生成される機械語命令の数は10個を超える可能性があり、パイプラインが過負荷になることがあります。マイクロアーキテクチャにハードウェア乗算機能ユニットがある場合は、逆数による乗算の方がより良いアプローチとなるでしょう。

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

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

ユニバーサルハッシュ方式は、ハッシュ関数群の中からハッシュ関数hをランダムに選択するアルゴリズムであり、2つの異なるキーが衝突する確率が1/ mとなるように選択されます。ここでmは、 2つのキーとは無関係に、必要なハッシュ値の数です。ユニバーサルハッシュは、（確率的な意味で）入力データの分布に関わらず、ハッシュ関数の適用がランダム関数を使用した場合と同様に機能することを保証します。ただし、完全ハッシュよりも衝突が多く、専用ハッシュ関数よりも多くの演算が必要になる場合があります。

特定のテーブルサイズや特定の長さまでの文字列しか許可しないハッシュ関数、またはシードを受け入れない（つまり、二重ハッシュを許可しない）ハッシュ関数は、それらを許可するハッシュ関数よりも有用性が低い。

ハッシュ関数はさまざまな状況で適用可能です。特に暗号化の分野では、注目すべきアプリケーションとして以下が挙げられます。^{[ 9 ]}

• 整合性チェック：異なるファイルに対して同一のハッシュ値が得られた場合、そのファイルは等しいとみなされ、ファイルの変更を確実に検出する手段となる。
• 鍵導出：入力のわずかな変化が、ランダムに見える出力の変化をもたらします。これは拡散特性として知られています。そのため、ハッシュ関数は鍵導出関数として非常に有用です。
• メッセージ認証コード（MAC）：ハッシュ関数は、入力データに機密キーを統合することにより、 HMACなどのデータの真正性を保証するMACを生成できます。
• パスワードの保存：パスワードのハッシュ値はパスワードの詳細を一切公開しないため、ハッシュ化されたパスワードをサーバー上に安全に保存することの重要性が強調されます。
• 署名：メッセージ全体ではなく、メッセージのハッシュ値に署名します。

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

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

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

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

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

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

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

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

移動が最小限のハッシュ関数は、分散ハッシュテーブルにおいて特に有用である。

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

ハッシュ化するデータが十分に小さい場合、データ自体（整数として再解釈したもの）をハッシュ値として使用できます。この同一性ハッシュ関数を計算するコストは実質的にゼロです。このハッシュ関数は、各入力をそれぞれ異なるハッシュ値にマッピングするため、完全です。

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

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

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

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

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

標準的な手法は、キーに対して剰余関数を使用することです。これは、テーブルサイズに近い素数である除数Mを選択することによって行われ、 h ( K ) ≡ K (mod M )となります。テーブルサイズは通常 2 のべき乗です。これにより、{0, M − 1}の範囲の分布が得られます。これは、多数のキーセットに対して良好な結果をもたらします。除算ハッシュの大きな欠点は、除算がほとんどの最新のアーキテクチャ ( x86を含む) で複数のサイクルを必要とし、乗算よりも 10 倍遅くなる可能性があることです。2 番目の欠点は、クラスタ化されたキーを分割できないことです。たとえば、キー 123000、456000、789000 などは、mod 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 0 とみなすことができます。2を法とする多項式演算を使用した剰余は、K ( x ) mod Z ( x ) = h _{m − 1} x ^{m − 1} + ⋯ h ₁ x + h _0です。すると、h ( K ) = ( h _{m − 1} … h ₁ h ₀ ) _{2 となります}。Z ( x )がt個以下の非ゼロ係数を持つように構築されている場合、 tビット未満を共有する鍵は衝突しないことが保証されます。

Z はk、t、n (n は2k − 1の約数)の関数であり、有限体GF( ^2k )から構成^されます。 クヌースは例を挙げています。( n , m , t ) = (15 ^, 10, 7)とすると、Z ( x ) = x10 ⁺ x8 + ^{x5 +} x4 + x2 + x + 1^となります。導出は次のとおりです。

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

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

一般的に、この方式が計算上実現可能となるためには、 nが大きくなるか、tが大きくなるか、あるいはその両方が必要となる。したがって、ハードウェアまたはマイクロコードによる実装に適している。^{[ 3 ]： 542-543}

一意順列ハッシュ法は、最悪ケースの挿入時間が保証されている。^{[ 12 ]}

標準的な乗法ハッシュでは、 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言語などではこの関数は次のようになります。

unsigned hash ( unsigned K ) { return ( a * K ) >> ( w - m ); }

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

乗法ハッシュは、拡散が不十分になるという「よくある間違い」に陥りやすい。つまり、値の高い入力ビットが値が低い出力ビットに影響を与えない。^{[ 13 ]} 入力に対して、保持される上位ビットの範囲を下にシフトし、乗算ステップの前にそれらをキーにXORまたはADDする変換を行うことで、この問題を修正できる。結果として得られる関数は次のようになる。^{[ 8 ]}

unsigned hash ( unsigned K ) { K ^= K >> ( w - m ); return ( a * K ) >> ( w - m ); }

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

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

乗数は奇数である必要があり、そうすることで出力の最下位ビットが 2w を法として可逆になります。^上記の最後の 2 つの値は、これを実現するために、それぞれ最下位ビットの 1/2 より大きく切り上げ、切り捨てられています。

ゾブリストハッシュは、アルバート・ゾブリストにちなんで名付けられた、表参照と XOR 演算を組み合わせることで普遍的なハッシュ関数ファミリーを構築する方法である表参照ハッシュの一種です。このアルゴリズムは、ハッシュ処理（特に整数キーのハッシュ処理）において非常に高速かつ高品質であることが証明されています。^{[ 14 ]}

ゾブリストハッシュは、もともとコンピュータゲームプログラムでチェスの局面をコンパクトに表現する手段として導入されました。盤上の各マスにある駒の種類（黒と白それぞれ6種類）を表すために、一意の乱数が割り当てられます。そのため、プログラムの開始時に64×12個の乱数からなるテーブルが初期化されます。乱数の長さは任意ですが、盤上の64マスにちなんで64ビットが自然と採用されました。局面は、その局面にある駒を順に処理し、対応する乱数をインデックス付け（空きマスは計算に含まれません）、それらをXOR演算（開始値は0（XORの一意値）または乱数シード）することで書き起こされます。得られた値は、剰余演算、折り返し演算、またはその他の演算によってハッシュテーブルのインデックスに変換されます。元のゾブリストハッシュは、局面の表現としてテーブルに格納されます。

その後、この方法は、ワード内の4つの可能な位置のそれぞれにある各バイトを一意の32ビット乱数で表すことで、整数のハッシュ化に拡張されました。このようにして、2⁸ ^× 4の乱数テーブルが構築されます。32ビットのハッシュ整数は、平文整数の各バイトの値でテーブルを順次インデックス付けし、ロードされた値をXOR演算することで転記されます（ここでも、開始値は識別子値または乱数シードを使用できます）。64ビット整数への自然な拡張は、2⁸ ^× 8の64ビット乱数テーブルを使用することです。

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

ハッシュ関数は、キーに含まれるエントロピーを活用するように設計できます。キーの先頭または末尾にゼロがある場合、あるいは特定のフィールドが未使用で常にゼロまたはその他の定数である場合、あるいは一般的に変化が少ない場合は、揮発性ビットのみをマスクしてハッシュ化することで、より優れた、場合によってはより高速なハッシュ関数が得られます。キーが巡回的であったり、その他の冗長性がある場合、除算および乗算方式における除数または乗数の選択によって、より均一なハッシュ関数が得られる可能性があります。

単純なハッシュ関数では、文字列の最初と最後のn文字を長さに加えて加算したり、文字列の中央の 4 文字からワードサイズのハッシュを生成したりすることがあります。これにより、（場合によっては長い）文字列を反復処理する必要がなくなりますが、文字列のすべての文字に対してハッシュ化を行わないハッシュ関数は、キーセットの冗長性、クラスタリング、またはその他の異常によって容易に線形化してしまう可能性があります。キーの構造が、中央、両端、またはその他のフィールドがゼロであるか、キーを区別しない何らかの不変定数である場合、このような戦略はカスタムハッシュ関数として効果的です。この場合、キーの不変部分は無視できます。

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

1970年代にベル研究所のピーター・J・ワインバーガーの研究に基づいてPJWハッシュと呼ばれる古典的なアプローチは、元々は「ドラゴンブック」に示されているように、識別子をコンパイラシンボルテーブルにハッシュ化するために設計されました。^{[ 15 ]}このハッシュ関数は、バイトを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の値は通常、潜在的なキーの文字セット内の異なる文字の数を保持するのに十分な大きさの素数です。文字列の基数変換ハッシュは衝突の数を最小限に抑えます。^{[ 16 ]}利用可能なデータ サイズは、この方法でハッシュできる文字列の最大長を制限する場合があります。例えば、128ビットワードでは、基数29の場合、26文字のアルファベット文字列（大文字小文字を区別しない）しかハッシュ化できません。印刷可能なASCII文字列は、基数97と64ビットワードを使用した場合、9文字に制限されます。ただし、ハッシュテーブルにキーを格納する必要があるため、アルファベットキーは通常、それほど長くありません。数値文字列は通常問題ありません。64ビットでは、基数10で^10¹⁹、つまり19桁の10進数をカウントできます。

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

この種のアルゴリズムで最もよく知られているのは、Rabin-Karpアルゴリズムです。このアルゴリズムは、最良および平均的なパフォーマンスがO ( n + mk )、最悪の場合のパフォーマンスがO ( n · k )です(公平を期すために付け加えると、ここでの最悪ケースは非常に特殊なケースです。テキスト文字列と部分文字列の両方が、t ="AAAAAAAAAAA", やs ="AAA") のように、同じ文字が繰り返される場合です)。このアルゴリズムで使用されるハッシュ関数は通常、8 ビット文字列での衝突を回避するように設計されたRabin フィンガープリントですが、他の適切なハッシュ関数も使用されます。