multiplicative hash は完全ではない（証明付）

概要

• メルカリのハッシュ関数の完全性の別証明
• multiplicative hash（実数値計算）の実装と計算機実験
• multiplicative hash（整数値計算）の実装と計算機実験
  • multiplicative hash でインデックスが衝突する, 完全でない例（命題3の証明）
  • multiplicative hash とメルカリのハッシュ関数の違い

注

• 本文では, 参考文献を [著者名 西暦下2桁] と記す. その詳細は文末の参考文献に示す.
• 本文中に示す命題の証明は, 付録にまとめて示す.

はじめに

メルカリのブログに, Knuth multiplicative hash が最小完全ハッシュ関数であることの証明 [metal_unk 17] というエントリがあり, Knuth の multiplicative hash が最小完全である証明を示しています.

実用的なハッシュ関数はたいていインデックスの衝突を起こす [Weiss 14] と説明されているため, そのエントリを興味深く読みました. 今のところわかったのは次の3点です.

• ブログエントリに書かれているハッシュ関数（以後, メルカリのハッシュ関数と呼ぶ）は完全である.
• multiplicative hash に対して広く知られている定義では, 一見では等価に見えない2種類の説明があり, そのどちらもメルカリのハッシュ関数の定義とは本質的に異なる.
• multiplicative hash はインデックスの衝突を起こすので完全ではない.

1点目については, はてなブックマークコメントにおいて,

やってることは変わらんが、「primeとmaxが互いに素なので法maxの下でprimeの逆元がある。よって、全単射」で通じそう。

[smoking186 17] や,

f(n) = ((n*PRIME) mod MAX) + 1 のようですね。mod MAX で PRIMEの逆元があるから全単射は自明ですね。また、復元可能が要件だとしても（逆元が定義域にないなら弾けばいいので）全射である必要性はないですね。

[mather314 17] のように, 自明だと理解されている方もいらっしゃいます. はじめは, ブログエントリやこのブックマークコメントだけではわからなかったため, 自分で理解するためにブログエントリとは別の, 切り捨て関数を使わない証明を書きました. しかしその後, これらのコメントを基に簡潔な証明が書けました. ありがとうございました.

2点目については, multiplicative hash の定義は, 大きく分けて2種類, 実数演算を用いる手続き（以後, 乗法ハッシュ（実数値）と呼ぶ）と整数演算とビットシフト操作を用いる手続き（以後, 乗法ハッシュ（整数値）と呼ぶ）がありました. どちらも, メルカリのハッシュ関数とは異なり, インデックスが衝突する結果を返すことを計算機実験により確認しました. ただし, Knuth の原著書 [Knuth 73] を参照する手段がなかったため, multiplicative hash については, 異なる複数の著者による講義資料で補いました. それらの部分部分をつぎはぎで読んだため, 一貫していない理解による誤った説明が含まれている可能性に留意して下さい.

3点目については, 実装した Python のコードと実行結果を用いて, multiplicative hash が衝突を起こす具体例から, 完全でないことを示します. これにより, メルカリのハッシュ関数は multiplicative hash とは本質的に異なることがわかります.

記述に間違いなど見つかりましたら, ご指摘ください. よろしくお願いします.

メルカリのハッシュ関数

定義1 $p$ は3以上のある素数, $m$ はハッシュ関数のテーブルサイズを表す 2 のべき乗 (ある正整数 $r$ を用いて $m=2^r$) をそれぞれ表すとする. このとき, キーの値 $n$ をインデックスに変換する メルカリのハッシュ関数 $f(n)$ を次で定義する.

f(n) = (np\mod m) + 1.

$f$ のキーの値の範囲（定義域）, インデックスの値の範囲（値域）はともに [1, ... , m] である.

補題1 $a, m$ を互いに素となる正整数とする. $0\leq n\le m-1$ に対して $g(n) = an\mod m$ とする. 任意の $n, n'$ の組 ($0\leq n < n'\leq m-1$) に対して, $g(n)\neq g(n')$ となる.

命題1 任意に与えられた、2つの互いに異なるキー $n, n' (1\leq n, n' \leq m, n\neq n')$ に対して, メルカリのハッシュ関数は $f(n) \neq f(n')$ となる.

系1 メルカリのハッシュ関数 $f$ において, $a, m$ が互いに素である限り, $f$ は全単射である.

そして, メルカリのハッシュ関数 $f(n)$ には次の特徴がある.
命題2 キー $n$ が奇数のとき, $f(n)$ は偶数になり, $n$ が偶数のとき, $f(n)$ は奇数になる.

命題2の意味を説明する.
メルカリのハッシュ関数はインデックスの集合からキーの集合へ写すときに, インデックスの2つの部分集合からそれぞれキーの2つの部分集合に分けている.
次のコードは, $a=40507$, テーブルサイズ $m=16$ に対するメルカリのハッシュ関数のインデックスと, 比較のために同じ条件での乗法ハッシュ（整数値）のインデックスを出力する.

hashsample.py

import math

def kmh2(n, a, r, w): # Knuth's multiplicative hash
    """
    defined in a handout of lecture 5 Hashing 1
    http://courses.csail.mit.edu/6.006/fall09/lecture_notes/lecture05.pdf
    """
    return ((a * n) % 2**w) >> (w-r)

def kmh(n, phi, tablesize): # Knuth's multiplicative hash
    """
    defined in a handout on hash functions 
    classes.engineering.wustl.edu/cse241/handouts/hash-functions.pdf
    """
    return int(math.floor(tablesize * (phi * n - math.floor(phi * n))))

def mmh(n, prime, tablesize): # Mercari's multiplicative hash
    return ((n * prime) % tablesize) + 1

def main():
    phis = [0.5*(math.sqrt(5)-1.0)]
    w = 16
    for phi in phis:
        a = 40507 # fixed prime
        # a = 2*int(2**(w-1)*phi)+1
        for v in range(4, 5):
            print "======="
            tablesize = 2**v
            print "tablesize", tablesize
            mmhvals = [mmh(x+1, a, tablesize) for x in range(tablesize)]
            kmh2vals = [kmh2(x, a, v, w) for x in range(tablesize)]
            print "mercali ", mmhvals
            print "multi   ", kmh2vals

main()

実行結果は次の通り.

hashsample.txt

=======
tablesize 16
mercali  [1, 12, 7, 2, 13, 8, 3, 14, 9, 4, 15, 10, 5, 16, 11, 6]
multi    [0, 9, 3, 13, 7, 1, 11, 5, 15, 9, 2, 12, 6, 0, 10, 4]

この実験結果を次の図に表す. ただし, キー, インデックスは, 奇数, 偶数で分けて並べる. 衝突の起きたキー, インデックスは同じ色（赤、緑）に塗りつぶされている. そのキーからインデックスを表す矢印を太線で表す. どのキーからも変換されないインデックスは水色に塗りつぶされている.

インデックスの奇数と偶数の境目を超えるキーの値がないことを表したのが, 命題2である. 後述する乗法ハッシュ（整数値）に対しては, 命題2は成り立たたず, キーが散らばっていることが図からわかる.

さらに, メルカリのハッシュ関数は, インデックスからキーの対応に, 奇数と偶数で同じパターンを持つ. 先ほどの例からにおけるパターンを次の図で表す. インデックスとキーの組を同じ色で塗りつぶしている.

メルカリのハッシュ関数はキーの値が2増えれば, インデックスの値は常に $2p$ 増えるので, このようなパターンは常に現れ, インデックスの初めの値を適切に揃えることで, 奇数におけるインデックスからキーへの対応と偶数における対応を一致させることができる.

multiplicative hash （乗法ハッシュ）

乗法ハッシュ（実数値）

まず講義資料 [Burler 15] に基づき, 乗法ハッシュ（実数値）を定義する.

定義2 $m$ をハッシュ関数のテーブルサイズ, $\phi$ を 0 から 1 の間の実数とする. キー $n$ に対する 乗法ハッシュ（実数値) $h_1(n)$ を次で定義する.

h(n) = \lfloor m(\phi n - \lfloor \phi n\rfloor)\rfloor.

$\phi$ の値は, Knuth の推奨している黄金比 $(\sqrt{5}-1)/2$ や, $\sqrt{2}/2$, $\sqrt{3}-1$ といった無理数が多く使われる [Burler 15].

$h_1$ のキーの値の範囲（定義域）, インデックスの値の範囲（値域）はともに [0, ... , m-1] である.

この関数の計算手続きは, 次のようにも表される [FG 00].

s = phi * n
x = fractional part of s
h_1(n) = floor(m*x)

どちらもメルカリのハッシュ関数において足されていた $+1$ が含まれないが, 以下では 1 を足さない $h_1(n)$ で考える.

乗法ハッシュ（実数値）の Python による実装を以下に示す.

multihash1.py

import math

def kmh(n, phi, tablesize): # Knuth's multiplicative hash
    """
    defined in a handout on hash functions 
    classes.engineering.wustl.edu/cse241/handouts/hash-functions.pdf
    """
    return int(math.floor(tablesize * (phi * n - math.floor(phi * n))))

#def mmh(n, prime, tablesize): # Mercari's multiplicative hash
#    return ((n * prime) % tablesize) + 1

def main():
    phis = [0.5*(math.sqrt(5)-1.0), 0.5*math.sqrt(2), math.sqrt(3)-1.0] # 1st: the golden ratio
    for phi in phis:
        for v in range(2, 6): # tablesize = 4, 8, 16, 32
            print 
            tablesize = 2**v
            kmhvals = [kmh(x, phi, tablesize) for x in range(tablesize)]
            print kmhvals
            if (len(list(set(kmhvals))) != len(kmhvals)):
                print "collision found (phi:", phi, "tablesize:", tablesize, ")"
                #kmhvals.sort()
                kmhset = set(kmhvals)
                print "indices", kmhvals
                missed = sorted(list(set([x for x in range(tablesize)]).difference(kmhset)))
                print "missed indices", missed
            else: print "perfect (phi:", phi, "tablesize:", tablesize, ")"

main()

テーブルサイズ $m = 4, 8, 16, 32, \phi = (\sqrt{5}-1)/2, \sqrt{2}/2, \sqrt{3}-1$ のそれぞれの組み合わせに対する出力結果から, インデックスの衝突が起きた一部を示す.

multihash1.txt

indices [0, 9, 3, 13, 7, 1, 11, 5, 15, 8, 2, 12, 6, 0, 10, 4]
collision found (phi: 0.61803398875 tablesize: 16 )
missed indices [14]

indices [0, 19, 7, 27, 15, 2, 22, 10, 30, 17, 5, 25, 13, 1, 20, 8, 28, 16, 3, 23, 11, 31, 19, 6, 26, 14, 2, 21, 9, 29, 17, 5]
collision found (phi: 0.61803398875 tablesize: 32 )
missed indices [4, 12, 18, 24]

indices [0, 2, 1, 0]
collision found (phi: 0.707106781187 tablesize: 4 )
missed indices [3]

indices [0, 2, 1, 0]
collision found (phi: 0.732050807569 tablesize: 4 )
missed indices [3]

multihash1.py は, ある $m$ と $\phi$ の組み合わせに対して, インデックスが衝突したとき, collision found (phi, tablesize), リスト [0, ... , m-1] に対するインデックスのリスト, そして衝突によりインデックスに現れなかった値を表示する.

乗法ハッシュ（実数値）はインデックスの衝突を起こしたが, 実数値を用いたこれらの計算結果では, 丸め誤差が誤った結果を引き起こす可能性に注意が必要になる. そこで, 丸め誤差のない乗法ハッシュ（整数値）を実装し, 比較する.

乗法ハッシュ（整数値）

[DD 09] の6ページ目に基づき, 整数値のみで計算する multiplicative hash を定義する.

定義3 テーブルサイズ $2^r=m$, ワードのビット長 $w$, $2^{w-1}<a<2^{w}$ を満たす奇数 $a$ がそれぞれ与えられているとする. 乗法ハッシュ（整数値） を $h_2(n) = (an\mod 2^w) \gg (w − r)$ とする. ただし, $t \gg s$ は $t$ を右側へ $s$ ビットシフトする演算を表す.

$a$ は, 乗法ハッシュ（実数値）における $\phi$ に対応し, $2^{w−1}$ と $2^w$ のどちらにもあまり近くない奇数が推奨されている [DD 09].

乗法ハッシュ（実数値）と 乗法ハッシュ（整数値）の関係については, [Weiss 14] の5ページ目から説明がある.

ここで, 乗法ハッシュ（実数値）と乗法ハッシュ（整数値）を計算機実験で比較する. 同一条件でのインデックスを並べて表示し, 乗法ハッシュ（実数値）で誤りが起きていたかを確認する. その Python コードを以下に示す.

multihash2.py

import math

def kmh2(n, a, r, w): # Knuth's multiplicative hash
    """
    defined in a handout of lecture 5 Hashing 1
    http://courses.csail.mit.edu/6.006/fall09/lecture_notes/lecture05.pdf
    """
    return ((a * n) % 2**w) >> (w-r)

def kmh(n, phi, tablesize): # Knuth's multiplicative hash
    """
    defined in a handout on hash functions 
    classes.engineering.wustl.edu/cse241/handouts/hash-functions.pdf
    """
    return int(math.floor(tablesize * (phi * n - math.floor(phi * n))))

def mmh(n, prime, tablesize): # Mercari's multiplicative hash
    return ((n * prime) % tablesize) + 1

def main():
    phis = [0.5*(math.sqrt(5)-1.0), 0.5*math.sqrt(2), math.sqrt(3)-1.0] # 1st: the golden ratio
    w = 16
    for phi in phis:
        a = 2*int(2**(w-1)*phi)+1
        for v in range(2, 6):
            print "======="
            tablesize = 2**v
            kmhvals = [kmh(x, phi, tablesize) for x in range(tablesize)]
            kmh2vals = [kmh2(x, a, v, w) for x in range(tablesize)]
            print kmhvals
            print kmh2vals

main()

このコードの実行結果を次に示す.

multihash2.txt

[0, 2, 0, 3]
[0, 2, 0, 3]
=======
[0, 4, 1, 6, 3, 0, 5, 2]
[0, 4, 1, 6, 3, 0, 5, 2]
=======
[0, 9, 3, 13, 7, 1, 11, 5, 15, 8, 2, 12, 6, 0, 10, 4]
[0, 9, 3, 13, 7, 1, 11, 5, 15, 8, 2, 12, 6, 0, 10, 4]
=======
[0, 19, 7, 27, 15, 2, 22, 10, 30, 17, 5, 25, 13, 1, 20, 8, 28, 16, 3, 23, 11, 31, 19, 6, 26, 14, 2, 21, 9, 29, 17, 5]
[0, 19, 7, 27, 15, 2, 22, 10, 30, 17, 5, 25, 13, 1, 20, 8, 28, 16, 3, 23, 11, 31, 19, 6, 26, 14, 2, 21, 9, 29, 17, 5]
=======
[0, 2, 1, 0]
[0, 2, 1, 0]
=======
[0, 5, 3, 0, 6, 4, 1, 7]
[0, 5, 3, 0, 6, 4, 1, 7]
=======
[0, 11, 6, 1, 13, 8, 3, 15, 10, 5, 1, 12, 7, 3, 14, 9]
[0, 11, 6, 1, 13, 8, 3, 15, 10, 5, 1, 12, 7, 3, 14, 9]
=======
[0, 22, 13, 3, 26, 17, 7, 30, 21, 11, 2, 24, 15, 6, 28, 19, 10, 0, 23, 13, 4, 27, 17, 8, 31, 21, 12, 2, 25, 16, 6, 29]
[0, 22, 13, 3, 26, 17, 7, 30, 21, 11, 2, 24, 15, 6, 28, 19, 10, 0, 23, 13, 4, 27, 17, 8, 31, 21, 12, 2, 25, 16, 6, 29]
=======
[0, 2, 1, 0]
[0, 2, 1, 0]
=======
[0, 5, 3, 1, 7, 5, 3, 0]
[0, 5, 3, 1, 7, 5, 3, 0]
=======
[0, 11, 7, 3, 14, 10, 6, 1, 13, 9, 5, 0, 12, 8, 3, 15]
[0, 11, 7, 3, 14, 10, 6, 1, 13, 9, 5, 0, 12, 8, 3, 15]
=======
[0, 23, 14, 6, 29, 21, 12, 3, 27, 18, 10, 1, 25, 16, 7, 31, 22, 14, 5, 29, 20, 11, 3, 26, 18, 9, 1, 24, 15, 7, 30, 22]
[0, 23, 14, 6, 29, 21, 12, 3, 27, 18, 10, 1, 25, 16, 7, 31, 22, 14, 5, 29, 20, 11, 3, 26, 18, 9, 1, 24, 15, 7, 30, 22]

このコードで試した変数の設定では, 乗法ハッシュ（実数値）と乗法ハッシュ（整数値）は同じインデックスを返し, 同じ衝突を起こした.

命題3 multiplicative hash は完全ではない.

さらに, インデックスのリスト multihash2.txt を見ると, 奇数や偶数が続けて現れているところがあり, $h_1(n), h_2(n)$ では命題2 も成り立たない. $h_1(n), h_2(n)$ は, インデックスの散らばり具合を上げた一方で, 完全性を犠牲にしたと捉えられる.

メルカリのハッシュ関数 $f(n)$ と乗法ハッシュ（整数値） $h_2(n)$ の違いをまとめると, 次の2点になる.

• $f(n)$ はビットシフト操作を含まず, $h_2(n)$ は含む.
• $f(n)$ で定義される $p$ は 3 以上の素数だが, $h_2(n)$ の定義において対応する $a$ は素数でない奇数でも良い.

最後に

• メルカリのハッシュ関数は完全.
• multiplicative hash を実装することにより, 完全ではない（インデックスが衝突する）例を示した.
• multiplicative hash は, その定義に含まれるビットシフト演算と用いる変数の制約が, メルカリのハッシュ関数と異なる.

付録

補題1の証明 背理法で証明する. ある $n, n'$ に対して, $g(n)=g(n')$ と仮定する. そのとき,

\begin{eqnarray*}
g(n')-g(n)
&=&(an' - an)\mod m\\
&=&a(n'-n)\mod m\\
&=&0
\end{eqnarray*}

となる. $a,m$ は互いに素であるので, この差を 0 にするには, $n'-n$ は $m$ の倍数でなくてはならない. しかし, $n, n'$ の定義から, $0<n'-n<m$. よって, そのような $n, n'$ の組は存在しない. $\Box$

補題1の別証明 法 $m$ の下での $p$ の逆元を $p^{-1}$ と書く. $n\neq n' (0\leq n, n'\leq m-1)$ に対して, $f(n)=f(n')$ が成り立つと仮定する. このとき,

\begin{eqnarray*}
n\mod m
&=&
(p^{-1}np)\mod m\\
&=&
(p^{-1}f(n)\mod m)\\
&=&
(p^{-1}f(n')\mod m)\\
&=&
(p^{-1}n'p)\mod m\\
&=&
n'\mod m
\end{eqnarray*}

から $n=n'$ が成り立ち, $n, n'$ の選び方に反する. よって, 仮定が誤り. $\Box$

命題1の証明 補題1 の関数 $g(n)$ を使って $f(n)=g(n)+1$ と書ける. ただし, 定義域が異なるため, $f(m)=g(0)$ とする. $f$ と $g$ は一対一対応し, 異なる $n (0\leq n\leq m-1)$ に対して異なる $g(n)$ の値を返すことが補題1からわかっているので, 異なる $n (1\leq n\leq m)$ に対して, $f(n)$ も異なる値を取る.$\Box$

系1の証明 補題1の条件から明らか. $\Box$

命題2の証明 $q$ を $p=2q+1$ を満たす, ある正整数とする.

(1) $n$ が奇数のとき.
$k$ は $n=2k+1$ を満たす整数とする ($0\leq k < m/2$).
$f(2k+1)$ について次が成り立つ.

\begin{eqnarray*}
f(2k+1) 
&=& ((2k+1)(2q+1)) \mod m + 1\\
&=& (4kq \mod m)+(2(k+q) \mod m) + (1 \mod m) + 1\\
&=& (4kq \mod m)+(2(k+q) \mod m) + 2.
\end{eqnarray*}

$4kq$, $2(k+q)$ はともに偶数なので, それらに対する $m$ の剰余も偶数になり, 偶数の和で構成される $f(2k+1)$ は偶数になる.

(2) $n$ が偶数のとき.
$k$ は $n=2k$ を満たす整数とする ($0< k \leq m/2$).
$f(2k)$ について次が成り立つ.

\begin{eqnarray*}
f(2k) 
&=& (2k(2q+1)) \mod m + 1\\
&=&  (4kq \mod m)+(2k \mod m)  + 1.
\end{eqnarray*}

$4kq, 2k$ はともに偶数なので, それらの $m$ の剰余も偶数になり, それらに 1 を足した $f(2k)$ は奇数になる. $\Box$

命題3の証明 上の計算機実験により得られた反例により証明する. $r=2, m=4, w=16, a=2\cdot\lfloor 2^{w-1}(\sqrt{5}-1)/2)\rfloor+1 = 40503$ とおく. このとき, $h_2(0)=h_2(2)=0$ となり, インデックスが衝突する. また, $a$ を素数 $40507$ に置き換えても, $h_2(0)=h_2(2)=0$ となる. $\Box$

参考文献

ネット上の文献はいずれも 2017年8月29日から31日までに閲覧した. また, [Knuth 73] は閲覧できていない.

[Buhler 15] Buhler, J. Choosing hash functions, handout of CSE 241 (Algorithms and Data Structures), Dept. Computer Science and Engineering, Washington University in St. Louis, https://classes.engineering.wustl.edu/cse241/handouts/hash-functions.pdf, 2015.

[DD 09] Devadas, S. and Daskalakis, K. Hashing I: Chaining, Hash Functions, Handout of 6.006 (Introduction to Algorithms), Dept Electrical Engineering and Computer Science, Massachusetts Institute of Technology, https://courses.csail.mit.edu/6.006/fall09/lecture_notes/lecture05.pdf, 2009.

[FG 00] Fleck, M. and Kuenning, G. Hash Functions, Note for CS 70 (Data Structures and Program Development), Dept. Computer Science, Harvey Mudd College, https://www.cs.hmc.edu/~geoff/classes/hmc.cs070.200101/homework10/hashfuncs.html, 2000.

[Knuth 73] Knuth, D. The Art of Computer Programming, Volume 3: Sorting and Searching, Addison-Wesley, 1973.

[metal_unk 07] metal_unk, Knuth multiplicative hash が最小完全ハッシュ関数であることの証明, メルカリ技術ブログ, http://tech.mercari.com/entry/2017/08/29/115047.

[mather314 17] mather314, はてなブックマークコメント,
http://b.hatena.ne.jp/mather314/20170829#bookmark-344131614, 2017.

[smoking186 17] smoking186, はてなブックマークコメント, http://b.hatena.ne.jp/smoking186/20170829#bookmark-344131614, 2017.

[Weiss 14] Weiss, S. Chapter 5: Hashing and Hash Tables, Handout of CSci 335 (Software Design and Analysis III), Dept. Computer Science, Hunter College of the City University of New York, http://compsci.hunter.cuny.edu/~sweiss/course_materials/csci335/lecture_notes/chapter05.pdf, 2014.