Knuth's multiplicative Hashing Method

Knuth 先生の The Art of Computer Programming の Volume 3 に、multiplicative hashing method が説明されています。C++ で書くと以下のコードになります。

#include <cstdio>
#include <cinttypes>
#include <unordered_map>

std::uint32_t hashOf(std::uint32_t x)
{
  // 2654435769 is godlden ratio of 2^32
  return x * UINT32_C(2654435769);
}

int main(int argc, char **argv)
{
  using namespace std;

  printf("%u\n", hashOf(103039302));
    
    return 0;
}

結果だけ見ると大変シンプルですが、TAOCP に記載されている hash function の定義は実質的には同じものですが上記コードとはだいぶ異なって見えます。

さて、TAOCP 版の hashing function は、

$$ h(K) = \lfloor (M (\frac{A}{w} K \bmod 1)) \rfloor $$

で定義されています。ここで K は入力となる integer で、A は $0 < \frac{A}{w} < 1$ が成り立つように選んだ任意の定数、w はコードを実行する機械の word size です。典型的には、$w = 2^{32}$ です。 $\bmod 1$ は小数部分だけを取り出すための演算で、コードで書けば x - floor(x) と等価です。

TAOCP を参照している別の文献によっては、

$$ h(K) = \lfloor (M (A \cdot K \bmod 1)) \rfloor $$

を hashing function としている場合もありますが、$\frac{A}{w}$ を改めて $A$ と置き直しているだけなので本質的には同じものです。

この式の詳細は TAOCP を読んでもらうとして、実践的にはだいたい以下の値が使われます。

$$ \begin{eqnarray} \frac{A}{w} = \frac{\sqrt{5} - 1}{2} \fallingdotseq 0.618033988 \newline M = 2^{32} \newline \end{eqnarray} $$

で、ここからが本題です。 上式とその値から hashing function の実装である x * UINT32_C(2654435769) はどうやって導出されるのかを見ていきます。

まず、2654435769 です。この数は $A \cdot 2^{32}$ を計算した後に整数へと丸め込むことで計算されています。ここで $A = 0.618033988$ です。Ruby で表現すれば (0.618033988 * 2 ** 32).round となります。

今 $w = 2^{32}$ を選択しているため $A = \frac{s}{2^{32}}$ となるように改めて $A$ を置き直してもよく、この時 $s$ は $0 < \frac{A}{w} < 1$ から $0 < s < 2^{32}$ の整数とします。 $A$ を $0 < A < 1$ と置き直したので、w は考えなくてよくなり

$$ h(K) = \lfloor (M (A \cdot K \bmod 1)) \rfloor $$

式を使っていると考えてください。

$A = \frac{s}{2^{32}}$ を式変形して $s = A \cdot 2^{32}$ とできます。この式変形から $A \cdot 2^{32}$ が出てくることになります。

この時、$A \cdot K$ の演算結果は $r_1 \cdot 2^{32} + r_0$ で表現できます。なぜなら、$A$ は 32 bits の数で $K$ も 32 bits の数であり、$A \cdot K$ は 64 bits に理論上はなり得ますが、その乗算結果を bit レベルでは high bits(32 bits) + low bits(32 bits) として表現できるためです。つまり、$r1$ が high bits の数、$r0$ が low bit の数を意味しているということです。

ところで、$s = A \cdot 2^{32}$ は小数部分が 32bit 固定小数点への変換とみなせます12。 ここで固定小数点を考えるのは、

$$ h(K) = \lfloor (M (A \cdot K \bmod 1)) \rfloor $$

この式の $A \cdot K \bmod 1$ が $A \cdot K$ の小数点部分だけを取り出す演算に相当しているためです。 別の言い方をすれば、$r_1 \cdot 2^{32} + r_0$ の 2 word size の数の上位 1 word size(32bit)の部分($r1$ の部分)は無視してもよく、下位 1 word size だけを考慮すればよいため、多くの計算機でより効率よく計算できる整数演算を利用するためというのが私の理解です。

$r_1 \cdot 2^{32} + r_0$ から $r_0$ だけを抜き出すには $\bmod 2^{32}$3 が必要です。$\bmod 2^{32}$ で $r_1 \cdot 2^{32}$ の項の計算結果は 0 になり、$r_0$ は変化しないためです。

しかし、C++ のコード x * UINT32_C(2654435769) では明示的な mod を利用していません。なぜでしょうか? 実は C 言語では uint32_t な数が overflow した場合、uint32_t の最大値に 1 を足した数で modulo を取った結果になる仕様があるため、明示的な $\bmod 2^{32}$ を省略するために unsigned 型を利用できます。 そのために C++ のコードは UINT32_Cuint32_t としての演算を明示しているというのが私の理解ですが、解説が見当たらなかったため間違っていればご指摘ください。

ここで、

$$ h(K) = \lfloor (M (A \cdot K \bmod 1)) \rfloor $$

に戻り、まだ説明していない M の説明をします。

TAOCP によると M は任意の数でよいみたいです。そもそもの M の目的は $A \cdot K$ の the leading bits of the least significant half(下位半分の bit 列の先頭 N bits) を抜き出すことにあります。なので、p bits を抜き出したい、かつ、$w = 2^{32}$ を選んだケースでは、$A \cdot K \bmod 2^{32}$ の右 bit から $32 - p$ bit を捨てる処理と考えることができます。 この処理をコードで表現すると x >> (32 - p) とできます。上記 C++ コードでは 32 bit を取得する前提があるためこの処理をしていません。

以上が C++ のコードの説明になります。より詳しい話は TAOCP Vol.3 を参照してください。

注意点

疑問点

For English Readers

TBD


  1. $s = A \cdot 2^{32}$ が固定小数点演算に相当すると名言されているのが、CS 3110 Lecture 21 Hash functions しか見当たらずこの解釈でよいのかはよく分かっていません。 [return]
  2. 一般的に round(x * 1 << p) を計算することで浮動小数点 x を小数部分 p bit の固定小数点へと変換できることを利用しています。固定小数点と整数の乗算はそのまま $a \cdot b$ として計算できます。 [return]
  3. $\bmod 2^{32}$ は & 0xFFFFFFFF で置き換え可能です。一般に $\bmod 2^{n}$ は $\& (2^{n} - 1)$ に置き換えられます。 [return]

Comments

comments powered by Disqus