ロビンフードハッシュとは？データ構造における公平な衝突解決手法を徹底解説

ロビンフードハッシュ（Robin Hood Hashing）とは

ロビンフードハッシュは、オープンアドレス法（開番地法）に分類されるハッシュ手法のひとつです。「富者から奪って貧者に与える」という伝説の英雄ロビンフッドの名前にちなんだこの方式は、要素ごとの探索時間に偏りが生じないよう、より公平な衝突解決戦略を採用している点が最大の特徴です。

従来の線形探査などの手法では、挿入順序やハッシュ値の分布によって、特定の要素だけ探索に長い時間がかかるといった「格差」が発生しがちでした。ロビンフードハッシュは、この格差を積極的に是正することで、最悪ケースの性能を大幅に改善します。

挿入時のルール：「若い」要素が道を譲る

要素を挿入する際、新しい要素 x を位置 x_i に配置しようとしたところ、すでに別の要素 y が同一の位置（y_j = x_i）を占有していた場合を考えます。このとき、両者のうちより「若い」要素（ホームポジションからの移動回数が少ない要素）が先へ進むことになります。

• i ≤ j の場合： 要素 x の方が「若いため」、x を位置 x_i+1、x_i+2、… と順に試しながら挿入を続けます。
• i > j の場合： 要素 x をそのまま位置 x_i に格納し、代わりに既存の要素 y を位置 y_j+1、y_j+2、… へと再挿入します。

このような要素の「入れ替え」を繰り返すことで、各要素のホームスロットからの距離（プローブ回数）のばらつきが小さく保たれ、探索時間が要素間で均等化されます。

理論的評価：二重対数時間の最悪ケース探索

Devroye らの研究によれば、初期状態が空のサイズ m = αn のテーブルに対して n 回の挿入をロビンフード挿入アルゴリズムで実行した場合、最悪ケース探索時間の期待値は次のようになります。

$$E[W]=\Theta(\log\log n)$$

さらに、この評価値はタイト（tight）であることが示されています。つまり、ロビンフードハッシュはオープンアドレス法の一形態でありながら、二重対数（doubly logarithmic）レベルの最悪ケース探索時間を達成できるのです。

参考までに、一般的な線形探査では負荷率が高まると最悪ケースの性能が大きく劣化しますが、ロビンフードハッシュは負荷率 α が 1 に近づいても安定した性能を維持できます。この特性から、Rust 言語の標準ライブラリ HashMap（2019年以前の実装）など、実用的なシステムにも採用されてきた実績のある手法です。