多肢選択式ハッシュ（Multiple Choice Hashing）の仕組みと理論

多肢選択式ハッシュの基本概念

多肢選択式ハッシュ（Multiple Choice Hashing）は、複数のハッシュ関数を用いて実装されることから、この名前が付けられました。

高レベルで見ると、複数のハッシュ関数が存在する場合、各項目は複数のバケットへ同時にマッピングされます。そのため、アルゴリズム設計者には「項目をどのバケットに配置するか」を選択する自由度が与えられます。

興味深いことに、この自由度こそが、単一のハッシュ関数のみを使用した場合と比べて、はるかにバランスの取れた割り当てを実現するアルゴリズムを可能にします。

本稿では、主要なアルゴリズムのアイデアと、これらのアルゴリズムが生成する割り当ての上限（バウンド）を証明するために用いられる主要な数学的ツールについて解説します。

さらに、その解析手法は基本モデルのさまざまな変種にも耐えうるほど強力であり、これこそが多肢選択式ハッシュのアルゴリズムが実務上の応用で高い効果を発揮する理由であると考えられています。

ボールとビンのモデルによる説明

多肢選択式ハッシュのアルゴリズムは、「ボールとビン（balls-into-bins）」モデルを例に挙げることで分かりやすく説明できます。

• 負荷分散プロセスを考察するための一般的な枠組みとして、「ボール」と「ビン」のモデルがあります。需要側（キー、プロセス、ファイルなど）は「ボール」で表され、資源の供給側（テーブルのスロット、サーバー、ストレージユニットなど）は「ビン」で表されます。
• この設定では、m個のボールが何らかの割り当てルールに従って、n個のビンへ順次投入されていきます。
• 目的は、全プロセス完了後のボールの割り当て状況を把握することです。通常は、最も負荷の高いビン（＝格納されているボールの数）に対して上限値を求めます。
• このモデルでは、1つ以上のハッシュ関数を適用することで、ボールからビンへの割り当てが行われます。
• これらのハッシュ関数は、ボールの一意なID（通常はモデル内で暗黙的に定義されます）を、1からnまでの番号が付けられたビンの集合へマッピングする役割を担います。
• 単純にランダムにビンを選ぶ代わりにハッシュ関数を用いることには大きな利点があります。後の時点で、ボールのIDからその格納場所を復元する必要が生じるケースが一般的だからです。