ロビンフッドハッシュ法
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/06/22 04:36 UTC 版)
ナビゲーションに移動 検索に移動ロビンフッドハッシュ法（Robin Hood Hashing）は、1986年にPedro Celisによって公開された連想配列の一種。
要素の格納にはただひとつの配列を使用し、要素のハッシュ値を配列長で割った余りを格納先のインデックスとする。 このとき、要素と共にこの余りを格納する。つまり最初の挿入ではこの値はインデックスに等しい。 すでに格納先が埋まっている場合、それ以降のインデックスでどの要素も本来の位置からできるだけ近い場所になるような位置に格納または入れ替えを行う。探索時には要素のハッシュ値を計算してそれを配列長で割った余りを探索の起点にして線形探索を行う。要素の削除には元論文[1]で提案されている要素の代わりに削除フラグを格納しておく方法と、前方の要素を持ってきて初期位置との距離ができるだけ小さくなるように詰める方法がある。後者の場合探索がより高速になることがある[2]。ロビンフッドハッシュ法はRustのような比較的新しい言語で採用例がある[3]。
脚注
- ^ “Robin Hood Hashing”. Pedro Celis. 2014年3月22日閲覧。
- ^ 図解あり“"Robin Hood hashing - Code Capsule"”. 2014年3月22日閲覧。
- ^ “This Week in Rust - Rust 'n Stuffs”. Corey Richardson. 2014年3月22日閲覧。
関連項目
|
||||||||||||||||||||||||||||||||||||
- ロビンフッドハッシュ法のページへのリンク
