Knuth の乗算ハッシュ法

整数ハッシュの計算の一つ、 乗算ハッシュ法についての覚書です。

⇒ D. Knuth, The Art of Computer Programming 2nd Edition, Volume 3 6.4 HASHING, 516 page (TAoCP と略す)

ある整数 k に対するハッシュ値を求めるのに、 Knuth 乗算ハッシュ法は、 固定小数点数の乗算をおこないます。 例えば、 32 ビットが 1 ワードのバイナリ演算器を用い、 m ビットのハッシュ値が欲しいとき、

    h(k) == floor((A / 2.0**32) * k mod 1) * 2.0**m)

この固定小数点計算をそのまま計算するときは整数部 32 ビット、 小数点以下 32 ビットの計 64 ビットでおこないます。 ですので、 この固定小数点の計算を 64 ビット整数乗算とシフト演算に置き換えることができます。 実際、 TAoCP 記載の MIX 計算機のアセンブリは 2 ワードで計算しています。 ただし、 MIX 計算機は固定小数点数の計算に有利な設計になっており、 MMIX を含む現代の 2 進プロセッサでは事情が異なります。 現代のプロセッサ向けに計算するときは、 乗算結果の上位 32 ビットを捨ててしまうことを考えて、 ストレートに 32 ビットで計算を済ませます。

    h(k) == ((A * k mod (2**32)) << m) >> 32         これを計算するには 64 ビット整数が必要 (MIX アセンブリの例)
         == (A * k mod (2**32)) >> (32 - m)          シフト演算を書き換えると 32 ビット整数で計算可能

この式で、 A を 33 ビットの固定小数点数 1.0 に対する素数の逆数にすると剰余の近似計算になります。 例えば、 13 ビットの素数 8191 から A を求めてみます。

    A == 2**32 / 8191
      == 524352

これを使って、 13 ビットのハッシュ値を計算すると、 k mod 8191 の近似値が求まります。

    h(k) == (524352 * k mod (2**32)) >> (32 - 13)
         == k mod 8191

A に 33 ビット固定小数点数の黄金率を選ぶと、 m ビットのフィボナッチ・ハッシュが得られます。

    A == 2**32 * 0.6180339887
      == 2654435769

    h(k) == (2654435769 * k mod (2**32)) >> (32 - m)