ハッシュ関数とハッシュテーブルの基本を徹底解説！代表的な3つの手法とは

ハッシュ化（ハッシング）とは、ハッシュ関数と呼ばれる数学的な関数を用いて、テキストや数値のリストから値を生成する処理のことです。数値キーや英数字キーを扱うハッシュ関数は数多く存在し、それぞれ計算方法や特性が異なります。

本記事では、代表的なハッシュ関数である「除算法」「乗算法」「中央二乗法」の仕組みと計算例を解説し、あわせてそれらを活用するデータ構造「ハッシュテーブル」についても詳しく紹介します。

ハッシュ関数とは

ハッシュ関数は、任意のキー（データ）を受け取り、固定範囲内の数値（ハッシュ値）へ変換する関数です。以下に、代表的なハッシュ関数を3つ紹介します。

1. 除算法（デビジョン法）

除算法は、ハッシュ関数を作成するうえで最もシンプルな手法です。ハッシュ関数は次のように表されます。

h(k) = k mod n

ここで、h(k) はキー値 k をハッシュテーブルのサイズ n で割った余りから得られるハッシュ値です。n には素数を選ぶのが望ましく、そうすることでキーがより均一に分散され、衝突を減らせることが知られています。

除算法の計算例は以下の通りです。

k = 1276
n = 10
h(1276) = 1276 mod 10
        = 6

この場合、得られるハッシュ値は 6 となります。

ただし、除算法には欠点もあります。連続するキーがハッシュテーブル上の連続したハッシュ値にマッピングされやすく、特定の領域にデータが偏ることでパフォーマンスが低下する可能性がある点です。

2. 乗算法（乗算メソッド）

乗算法で使用されるハッシュ関数は次の通りです。

h(k) = floor( n( kA mod 1 ) )

ここで、k はキー、A は 0 以上 1 未満の任意の定数です。まず k と A を掛け合わせ、その小数部分だけを取り出します。さらにそれに n を掛けることでハッシュ値を求めます。

乗算法の計算例は以下の通りです。

k = 123
n = 100
A = 0.618033
h(123) = 100 × (123 × 0.618033 mod 1)
       = 100 × (76.018059 mod 1)
       = 100 × 0.018059
       = 1

この場合、得られるハッシュ値は 1 となります。

乗算法の利点は、定数 A の値を自由に選べる点です。特に黄金比に近い値（0.618033…）など、一部の値はキーをより均一に分散させると考えられています。

3. 中央二乗法（ミッドスクエア法）

中央二乗法は、非常に優れたハッシュ関数の一つです。キーの値を2乗し、その結果の中央にある r 桁をハッシュ値として抽出します。r の値は、ハッシュテーブルのサイズに応じて決定します。

中央二乗法の計算例を見てみましょう。ハッシュテーブルに 100 個のメモリ位置がある場合、2桁あればすべての位置を表現できるため r = 2 となります。

k = 50
k × k = 2500
h(50) = 50

この場合、2500 の中央2桁から得られるハッシュ値は 50 です。

ハッシュテーブルとは

ハッシュテーブルは、キーを値に対応付ける（マッピングする）データ構造です。ハッシュ関数を使ってデータキーの格納先となるインデックスを計算し、そのインデックス位置にキーを格納します。これにより、大量のデータからも高速に目的の要素を検索・挿入・削除できるのが大きな特長です。

具体的な例として、次のキーシーケンスをハッシュテーブルに格納する場合を考えてみます。

35 50 11 79 76 85

使用するハッシュ関数は次の通りです。

h(k) = k mod 10

このとき、異なるキーが同じハッシュ値を持つ「衝突（コリジョン）」が発生することがあります。そこで線形探査法（リニアプロービング）を用いると、衝突が起きた場合にテーブル上の次の空きスロットへ順番に格納していくことで、すべてのキーを適切に配置できます。

このように、ハッシュ関数の選択と衝突解決策の設計は、ハッシュテーブルの性能を左右する重要なポイントです。用途やデータの特性に応じて最適な手法を選びましょう。