カッコウハッシュ法 とは？

挿入先にいる要素を追い出し、その要素を別の候補へ移すハッシュ表の方式だよ。先客の場所を取る様子を、カッコウの巣にたとえた名前なんだ。

2つのハッシュ関数を使うよ。各データは、2つのハッシュ関数が指す2か所のどちらかに必ず置くんだ。挿入するとき、どちらかの場所が空いていれば、そこへ入れておしまいだね。

片方の場所にいる既存の要素を追い出して、そこに新しい要素を入れるんだ。追い出された要素は、自分のもう一方の候補の場所へ移るよ。そこにも先客がいれば、また追い出す。これを空きが見つかるまで繰り返すんだね。

追い出しがループしたり、決めた試行回数を超えたりすることがあるよ。その場合はハッシュ関数を替えて作り直すなどの対処をする。基本形の理論上の解析では、表全体の使用率を半分未満に保つなどの条件があるんだ。

基本形では、要素の候補が2か所に決まっているから、検索は最悪でも2か所の確認で済むよ。一方、1回の挿入では追い出しや作り直しで時間がかかる場合がある。ハッシュ関数の選び方や表の空きに条件を置いた解析では、多数の更新をならして期待定数時間で扱えると示されているんだ。