fromageの日記： ハッシュ関数の証明と wikipedia の説明の食い違い

メルカリの技術ブログに、Knuth multiplicative hash が最小完全ハッシュ関数であることの証明が掲載されています。一方、Wikipedia 英語版の完全ハッシュ関数の項目には、

In computer science, a perfect hash function for a set S is a hash function that maps distinct elements in S to a set of integers, with no collisions.

とあり、（最小でなくても）完全ハッシュ関数であれば、要素の写像先で衝突がない、とされています。そして、Wikipedia 英語版のmultiplicative hashingの項目を見ると、

Multiplicative hashing is a simple type of hash function often used by teachers introducing students to hash tables.[11] Multiplicative hash functions are simple and fast, but have higher collision rates in hash tables than more sophisticated hash functions.[12]
（略）
[11] Knuth. "The Art of Computer Programming". Volume 3: "Sorting and Searching". Section "6.4. Hashing".

とあり、ハッシュテーブルを紹介するのに使われ、簡潔で高速だが、より洗練されたハッシュ関数より高い衝突率を持つ、と説明されています。

Multiplicative Hashing を直接説明しているのではないのですが、ニューヨーク市立大学の Weiss 教授による講義資料 (PDF) では、5.3 Collision の中で、

Since almost all practical hash functions are not perfect, they will map one or more keys to the same indices...

ほとんどの実用的なハッシュ関数は完全ではなく、異なるキーを同じインデックスに写像することがある、と書いてあるので、この証明が正しければ非常に重要な結果だと思います。

メルカリの技術ブログには multiplicative hash の手順が示されている一方、Wikipedia には文章での説明だけなので、名前が似ているが違う手順を指している可能性があります。また、何らかの条件下で成り立つのかもしれません。証明を読んだらわかるかな。

ブログの結果は, すでに本に書いてある

[Anonymous Coward]

メルカリブログにある定義は, The Art of Computer Programming 3 の 6.4 Hashing で示されている式 (5) の multiplicative method から, 操作 SLB m (m ビット右へ移動する）を抜いています. ブログで証明している定理は, Knuth 氏自身が, 操作 SLB m がなければ, 逆元を用いることで K1 != K2 から f(K1) != f(K2) が導かれる, と式 (6) に書いています.

メルカリブログで示されているハッシュ関数はこの SLB 操作を抜いた, Knuth's multiplicative hash とは別の関数の話だと思います. だから Knuth 氏と同様に完全性を示せたのでしょう.

式 (5, 6) に示されている内容をブログの筆者がどうとらえているのか, 知りたいですね.