データ構造の乗算法ハッシュとは？仕組みと黄金比による定数Aの選び方

乗算法ハッシュとは

ハッシュ表にキーを効率よく格納する手法の一つに「乗算法（multiplication method）」があります。この方法では、次のようなハッシュ関数を使用します。

h(x) = ⌊m・x・A⌋ mod m

ここで、A は実数値の定数、m はハッシュ表のサイズです。キー x に定数 A を掛けた値をもとにハッシュ値を算出し、mod m によって表の範囲に収めます。

乗算法のメリット：m の値が重要にならない

この方法の最大の利点は、表のサイズ m の値がそれほど critical ではない点です。一般的に使われる除算法（division method）では、衝突を避けるために m として素数や 2 の冪から離れた値を選ぶ必要がありますが、乗算法では m を 2 の冪（べき乗）にすることも可能です。2 の冪はビット演算で高速に処理できるため、実装面で大きなメリットがあります。

一方で、定数 A については注意が必要です。どんな値の A を選んでもハッシュ関数としては機能しますが、A の選び方によってキーの分散具合は大きく変わります。うまく選べば衝突を抑えられますが、適当な値では偏りが生じます。

クヌースが推奨する「黄金比」

ドナルド・クヌース（Donald Knuth）によれば、A には黄金比を用いるのが良いとされています。つまり、A は次の値となります。

A = (√5 − 1) / 2 ≒ 0.61803398

この黄金比を用いる方法は「フィボナッチハッシュ」とも呼ばれ、連続したキーや規則的なパターンを持つキーに対しても、ハッシュ値が比較的均等に分散するという優れた性質があります。

鳩の巣原理と最悪ケース

もちろん、どのような A の値を選んでも限界は存在します。鳩の巣原理（pigeonhole principle）により、u ≥ n・m が成り立つとき、あるハッシュ値 i と、サイズ n の部分集合 S ⊆ U が必ず存在し、S に属するすべての x に対して h(x) = i となってしまいます。つまり、大量のキーを有限のハッシュ値に対応させる以上、すべてが異なる値に割り振られることは保証できません。

このことから、乗算法によるハッシュの最悪ケースは、除算法によるハッシュと同じくらい悪くなり得ると言えます。平均的には良好な分散が期待できるものの、最悪時の計算量については両者に本質的な差はないのです。

まとめ

• 乗算法は h(x) = ⌊m・x・A⌋ mod m というハッシュ関数を用いる。
• 表サイズ m の制約が緩く、2 の冪も利用できるため実装が容易。
• 定数 A には黄金比 (√5 − 1)/2 ≒ 0.61803398 を用いるのが推奨される（クヌース）。
• ただし鳩の巣原理より、最悪ケースでは除算法と同様に性能が劣化しうる。