ハッシュテーブルの仕組みを徹底解説！ハッシュ関数・バケット・衝突処理の基礎

私が特に好きなデータ構造のひとつがハッシュテーブルです。シンプルでありながら非常に強力だからです。

キーと値のペアを効率的に保存できる手段として、あなたもすでに使ったことがあるかもしれません。

実は、ハッシュテーブルの実装には学ぶ価値のある興味深いコンピュータサイエンスの概念がたくさん詰まっています。この記事では、その仕組みを一緒に掘り下げていきましょう!

バケットとハッシュ関数

ハッシュテーブルの基本的な考え方は、キーでインデックス付けされたデータに対して、O(1) の計算量で効率的にアクセスできるようにすることです。

おさらいとして、Ruby でハッシュテーブルを使うと次のような見た目になります。

prices = {
  apple: 0.50,
  ice_cream: 3,
  steak: 10
}

ハッシュテーブルを実装するには、次の2つの要素が必要です。

• テーブルのエントリを格納する場所(配列)
• キーと値のペアをデータストア内の特定の位置(インデックス)に割り当てる方法(ハッシュ関数)

つまり、「配列」と「ハッシュ関数」の組み合わせがハッシュテーブルの正体なのです。

シンプルなハッシュ関数を実装してみる

ハッシュ関数はハッシュテーブルの中核を担う重要な要素です。

この関数は、キーをインデックスへと変換し、そのキーに関連付けられた値を検索・更新できるようにします。

これこそが、普通の配列とハッシュテーブルの大きな違いです。配列ではインデックス(数値)でしか値にアクセスできませんが、ハッシュテーブルでは任意のキー(文字列、シンボル、整数など)で値にアクセスできます。ただし、そのキーに対応するハッシュ関数を書けることが条件です。

文字列用のシンプルなハッシュ関数は、すべての文字を ASCII コードに変換して足し合わせることで作れます。

具体例を見てみましょう:

BUCKETS = 32

def hash(input)
  input.to_s.chars.inject(0) { |sum, ch| sum + ch.ord } % BUCKETS
end

このメソッドでは、まず to_s を使って必ず文字列として扱うようにしています。これにより「undefined method」エラーを回避できます。続いて chars(文字列を1文字ずつの Array に変換)と inject(合計値の計算)を組み合わせています。

ブロック内では ord メソッドを使い、各文字を序数(コードポイント)に変換しました。

最後に、モジュロ演算子 % を使って結果の値が配列のサイズ内に収まるようにしています。この配列の各要素を「バケット(bucket)」と呼びます。

バケットの分布を確認する

理想的には、すべてのバケットにキーが均等に分散しているのが望ましく、これが最良の検索パフォーマンスにつながります。

それでは、次のコードでハッシュ関数をテストすると何が起こるか見てみましょう。

# BUCKETS サイズの配列を作り、全要素を 0 で初期化
table   = Array.new(BUCKETS) { 0 }
letters = Array('a'..'z')

10_000.times do
  # ランダムな文字列を生成
  input = Array.new(5) { letters.sample }.join

  # ハッシュの分布をカウント
  table[hash(input)] += 1
end

実行結果は次の通りです。

[302, 290, 299, 309, 321, 293, 316, 301, 296, 306, 340, 321, 313, 304, 318, 296, 331, 306, 348, 330, 310, 313, 298, 292, 304, 315, 337, 325, 325, 331, 319, 291]

キーはかなり均等に分布しているように見えますね……。

ところが、バケット数を増やすとどうなるでしょうか? 今度はバケット数を128(前回は32)にして試してみます。

[22, 24, 33, 36, 41, 58, 61, 66, 97, 77, 88, 110, 89, 82, 123, 121, 119, 111, 147, 178, 136, 176, 144, 180, 190, 193, 185, 192, 223, 209, 208, 196, 215, 251, 233, 226, 231, 236, 219, 218, 227, 221, 206, 220, 208, 213, 201, 191, 182, 165, 188, 141, 160, 135, 130, 117, 139, 106, 121, 85, 70, 93, 74, 61, 57, 54, 40, 46, 32, 36, 30, 21, 25, 17, 14, 16, 16, 14, 8, 11, 5, 5, 1, 1, 2, 1, 3, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, ...]

今度は良い分布とは言えなくなってしまいました!

一体何が起こったのでしょうか?

原因は、このハッシュ関数が不十分だからです。同じ長さの文字列は特定の範囲に集中してしまうため、中央付近のバケットが大量に空いたままになっています。

より良いハッシュ関数

文字列をより均等にインデックスへ変換するには、別のアプローチが必要です。改善例のひとつを見てみましょう。

BUCKETS = 256

def hash(input)
  input.to_s.each_char.inject(0) do |sum, ch|
    (sum << 8) ^ (ch.ord) ^ (sum >> 4)
  end % BUCKETS
end

ここで行っているのはビットシフト(>> と << 演算子)です。さらに「排他的論理和(XOR)」演算子(^)で値を組み合わせています。

このビットシフトによって値が混ぜ合わされ、より良いキーの分布が得られます。完璧ではありませんが、単純な ASCII ベースの関数よりは明確に優れています 🙂

本格的なハッシュ関数が必要なら、MurmurHash のような実装を検討すると良いでしょう。Ruby の内部でも採用されているのはこれだと言われています。

衝突(コリジョン)への対処

しかし、このままではまだ実用的なハッシュテーブルにはなりません。

なぜでしょうか?

お気づきかもしれませんが、異なるキーが同じインデックスにハッシュされると、古い値が上書きされてしまうのです。これは困りますよね。

これを「ハッシュの衝突(hash collision)」と呼び、対策にはいくつかの戦略があります。

代表的な手法は次の通りです:

• ダブルハッシング(Double Hashing)
• 線形探査(Linear Probing)
• 分離連鎖法(Separate Chaining)

ここでは分離連鎖法を見てみましょう。この方式では、連結リスト(linked list)を使って同じバケットに属するエントリを保持します。

たとえば :abc と :ccc が同じインデックスにハッシュされた場合、ハッシュテーブルは次のようになります。

3: [:abc, 100] -> [:ccc, 200]
4: nil
5: [:yx, 50]

そして目的のキーを見つけるには、連結リストを線形探索する必要があります。

これがパフォーマンスに影響を与えます。探索時間は期待される O(1) ではなく、徐々に O(n) へと悪化しうるからです。

この O(なんとか) という記法に馴染みがない方のために補足すると、これは「ビッグオー記法(Big-O Notation)」と呼ばれる計算量の表現方法です。

連結リストが深くなりすぎてハッシュテーブルの性能が劣化するのを防ぐためには、バケット数を増やしてハッシュテーブルを作り直す必要があります。

Ruby ではこの再構築(リハッシュ)が自動的に行われますが、仕組みを知っておくことは有益です。

まとめ

この記事の目的は、読者自身にハッシュテーブルを実装してもらうことではなく、ハッシュテーブルが実際にどう動いているのかを理解してもらうことです。少しでも面白いと感じてもらえたなら嬉しいです!

ブログ運営の励みになるので、よければこの記事をシェアしてください 🙂