compiler-construction - ハッシュ テーブルの最適化

Question

いくつかのハッシュ テーブルの実装で、バケット内のアイテムに対して「転置」や「前面に移動」などのヒューリスティックの使用法を見てきました。

1. このようなヒューリスティックを使用する利点は何ですか? 私はそれを自分で理解できませんでした。
2. ハッシュ テーブル / バケット レベルで他にどのような最適化を行うことができますか?その理由と状況は?

ハッシュ関数の最適化はさておき。

Answer 1

衝突が発生していて、バケットにいくつかの項目があり、それらを調べる必要がある場合は、よくアクセスされる項目がリストの早い段階にあると便利です。

これらのヒューリスティックは、最近アクセスされたアイテムがすぐに再びアクセスされる可能性が高いと想定する理由がある場合に意味があります。ニュース記事などを考えると、ニュース速報は頻繁にアクセスされる可能性が高いです。