mercariengineering
XLinkedInRSS
XLinkedInRSS

Knuth multiplicative hash が最小完全ハッシュ関数であることの証明

Author:
Metal_unk
 , 
Knuth multiplicative hash が最小完全ハッシュ関数であることの証明

こんにちは！サーチチームの @metal_unk です。普段はサーバーサイドエンジニアとして、メルカリの検索を改善する仕事をしています。

メルカリには Be Professional Day という「普段できないことをやろう」をテーマとする日があり、その日は業務に直接関係のないことや、普段は手をつけられないリファクタリングなどがされます。Be Professional Day の様子はこちらで紹介されています。

tech.mercari.com

わたしは今回の Be Professional Day で、Knuth multiplicative hash が最小完全ハッシュであることを証明しました。このブログはその証明についての記事です。

「普段できないことをやろう」という Be Professional Day では、証明もアリです。

Knuth multiplicative hash とは

コンピュータサイエンスの有名人である Donald Knuth さんが、著書 “The Art of Computer Programming” で説明しているハッシュ関数です。

Knuth multiplicative hash を表す関数を以下とします。（後の証明のわかりやすさのため、細かい部分を変えていますが、本質的には同じものです）

f(n) = ( n \times \mbox{PRIME} ) \mod \mbox{MAX} + 1

ここで、 \mbox{PRIME} は 3 以上の素数、 \mbox{MAX} は2のべき乗であるような整数。集合 A = \{x \in \mathbb{Z} \mid 1 \leq x \leq \mbox{MAX} \} とすると、関数 f は A から A への変換写像です。

最小完全ハッシュ関数とは

Wikipedia によると、完全ハッシュ関数とは以下の通りです。

ハッシュ関数が単射の場合、すなわち正しい入力に対して必ず異なるハッシュ値が対応する場合、これを完全 (perfect) だという。

さらに、完全ハッシュ関数の特殊ケースである、最小完全ハッシュ関数の説明は以下の通りです。

n 個のキーに対する完全ハッシュ関数が最小 (minimal) であるとは、その値域が n 個の連続な整数（通常 0 から n-1）の場合である。単に参照が単純化されるだけでなく、ハッシュテーブルもコンパクトになり、空きスロットができない。最小完全ハッシュ関数は単なる完全ハッシュ関数よりも求めるのが難しい。

f:id:Metal_unk:20170825205021p:plain

Wikipedia contributors. ハッシュ関数. Wikipedia. November 8, 2016, 15:00 UTC. Available at: https://ja.wikipedia.org/w/index.php?title=%E3%83%8F%E3%83%83%E3%82%B7%E3%83%A5%E9%96%A2%E6%95%B0&oldid=61853949. Accessed November 8, 2016.

ここで、最小完全ハッシュは数学の言葉を使うと、全単射である関数とも言えます。

メルカリでの使い道

（わたしは証明をしただけなので伝聞ですが）ある内部 id をハッシュ化 / 復元するための関数が必要とされていました。Knuth multiplicative hash はこの条件を満たし、計算時間が高速であるため採用されました。

証明する意味

Knuth multiplicative hash が最小完全ハッシュである証明が見つからなかったので、証明しました。

もしも最小完全ハッシュであることがわからなかったら、衝突をケアするコードを書く必要があったり、1 から \mbox{MAX} までを入力して衝突しないことを確かめるテストを書いたりする必要があるかもしれません。

今回は証明によってコードを減らすことができました。数学は机上の空論であったり、抽象的すぎるものになりがちですが、現実世界の問題を扱い、プロダクトのために活用できたところがとても嬉しいです。

では証明を始めます。（もしも途中で飽きたら飛ばして最後だけ読んでください）

証明

Knuth multiplicative hash を f として以下のように表す。

f(n) = ( n \times \mbox{PRIME} ) \mod \mbox{MAX} + 1

ここで、 \mbox{PRIME} は 3 以上の素数、 \mbox{MAX} は2のべき乗であるような整数。集合 A = \{x \in \mathbb{Z} \mid 1 \leq x \leq \mbox{MAX} \} とする。

新たに floor 関数 g(n) = \Bigl\lfloor{\frac{ n \times \mbox{PRIME}}{\mbox{MAX}}\Bigr\rfloor} を利用して、 f は以下のように書ける。

f(n) = n \times \mbox{PRIME} - g(n) \mbox{MAX} + 1

ここで、関数 f は A から A への変換写像であるから、 f は単射のとき全射でもある。よって、ここでは f が最小完全ハッシュであることを証明するために、 f が単射であることを示す。示したいものは以下。

\forall n, n' \in A, f(n) = f(n') \Rightarrow n = n'

A から任意に要素を2つ取得し、小さい方を n_1, 大きい方を n_2 とする。（ n_1 \leq n_2）

f(n_1) = f(n_2) を仮定すると、

\Rightarrow n_1 \times \mbox{PRIME} - g(n_1) \mbox{MAX} + 1 = n_2 \times \mbox{PRIME} - g(n_2) \mbox{MAX} + 1

\Rightarrow \mbox{PRIME} (n_2 - n_1) = \mbox{MAX} (g(n_2) - g(n_1))

このとき、

\mbox{PRIME} (n_2 - n_1) = \mbox{MAX} (g(n_2) - g(n_1)) = \mbox{PRIME} \times \mbox{MAX} \times m … â‘ 

となるような m が存在するが、その m について以下のことが言える。

  1. n_2 - n_1 \geq 0, \mbox{PRIME}, \mbox{MAX} > 0 であるから m \geq 0

  2. m = \frac{1}{\mbox{PRIME}} と仮定すると、① より \mbox{PRIME} (n_2 - n_1) = \mbox{MAX} である。ここで、 n_2 - n_1 \in \mathbb{Z} に対して \frac{\mbox{MAX}}{\mbox{PRIME}} \notin \mathbb{Z} が矛盾するから m \neq \frac{1}{\mbox{PRIME}}

次に ① より、

\mbox{PRIME} (n_2 - n_1) = \mbox{PRIME} \times \mbox{MAX} \times m

\Rightarrow n_2 - n_1 = \mbox{MAX} \times m

\Rightarrow 1 > m \; ( \because n_1, n_2 \in A \Rightarrow \mbox{MAX} > n_2 - n_1)

さらに ① より、

\mbox{MAX} (g(n_2) - g(n_1)) = \mbox{PRIME} \times \mbox{MAX} \times m

\Rightarrow g(n_2) - g(n_1) = \mbox{PRIME} \times m

g(n_1), g(n_2) \in \mathbb{Z} だから \mbox{PRIME} \times m \in \mathbb{Z} であり、素数である \mbox{PRIME} にかけて整数になるような数字は \frac{1}{\mbox{PRIME}} と整数だけであるが、 m \neq \frac{1}{\mbox{PRIME}} だったから m \in \mathbb{Z}

以上により、 m \in [0, 1) かつ m \in \mathbb{Z} であることがわかり、 m = 0 に定まった。

\Rightarrow n_2 - n_1 = \mbox{MAX} \times 0

\Rightarrow n_1 = n_2

よって、 f は単射であり、Knuth multiplicative hash は完全最小ハッシュであることが証明された。

おわりに

Knuth multiplicative hash が最小完全ハッシュであることを証明することで、プロダクトで安心して利用できるようになりました。

数学は実用に遠いイメージがあるかもしれませんが、世界（もちろんメルカリの中にも！）には数学で解ける問題がたくさん存在するはずです。今回のように証明を与えることで達成できることや、機械学習や数理最適化で解決できる問題もあります。そのような問題を数学で解決していきたいです。

また、メルカリではそのような問題を共に解決する仲間を募集中です。

Software Engineer, Machine Learning/Natural Language Processing

Software Engineer, Backend

興味のある方はぜひご飯を食べに行きましょう！気軽に誘ってください 🙂

最後の最後に、メルカリ数学部は毎週ゼミを実施し、楽しく議論しております。こちらも部員募集中です！（部員になるためには社員になる必要があります）

mercan.mercari.com
  • X
  • Facebook
  • linkedin
  • このエントリーをはてなブックマークに追加

Related article