除算法（モジュロ演算）によるハッシュ法の仕組みと計算量を徹底解説

除算法によるハッシュとは

ここでは、除算法（division method）と呼ばれるハッシュ手法について解説します。この手法では、次のようなハッシュ関数を使用します。

ℎ(𝑥) = 𝑥 𝑚𝑜𝑑 𝑚

つまり、キー x を m で割った余りをハッシュ値として利用する、シンプルながら広く使われている方法です。

チェイン法（連鎖法）による実装

このハッシュ関数を実際に利用するためには、配列 A[0, …, m − 1] を用意します。配列の各要素は、連結リストの先頭ノードへのポインタを保持しています。連結リスト L_i は配列要素 A[i] が指し示しており、h(x) = i を満たすすべての要素 x を格納します。

このように、同じハッシュ値を持つ複数の要素を連結リストで管理する技法は、「ハッシング・バイ・チェイニング（hashing by chaining）」、通称チェイン法と呼ばれます。

挿入・検索・削除にかかる時間

このようなハッシュテーブルへの要素の挿入は、O(1) の時間で行えます。手順は以下の通りです。

1. 添字 i = h(x) を計算する
2. リスト L_i の末尾（または先頭）に x を追加する

一方、検索や削除はそれほど簡単ではありません。まず添字 i = h(x) を求めた後、目的の値に到達するか、リストが尽きるまでリスト L_i を順に走査する必要があります。この操作にかかる時間は、リスト L_i のサイズに比例します。

極端な例として、集合 S が 0, m, 2m, 3m, …, nm のような要素のみで構成されている場合を考えてみましょう。これらの要素はすべて h(x) = 0 となるため、リスト L₀ に集中して格納され、検索や削除には線形時間がかかってしまいます。

平均的なケース：O(1 + α) の計算量

ただし、このような偏った状況は現実には非常にまれです。例えば、集合 S が普遍集合 U 内で一様かつ独立に分布しており、|U| = u が m の倍数である場合、各リスト L_i の期待サイズはわずか n/m となります。

この場合、検索および削除にかかる時間は O(1 + α) で表されます。ここで α = n/m は負荷率（load factor）と呼ばれ、ハッシュテーブル内の要素数とスロット数の比を示す重要な指標です。負荷率が小さければ小さいほど、各操作は定数時間に近づきます。

ハッシュ値の偏りを避ける m の選び方

上述のような最悪ケースを避けるためには、m の値を賢く選ぶことが不可欠です。一般的な指針は以下の通りです。

• m を 2 の冪（べき乗）にしない：多くの環境ではキーの下位ビットに偏りが出やすいため、ハッシュ値が特定の値に集中する恐れがあります。
• 2 の冪からあまり近くない素数を選ぶ：素数を m とすることで、キーのパターンに関係なくハッシュ値がより一様に分散されます。

適切な m を選ぶことで、チェイン法によるハッシュテーブルは、挿入・検索・削除すべてにおいて高い性能を安定して発揮できるようになります。