このハッシュテーブルの最適化の名前は何ですか？

オープンアドレス指定でカスタムハッシュテーブルを実装しているときに、私のアプリケーションでは、プローブされた要素の行を最初のプローブ位置のスロットに入れ替えた場合、パフォーマンスが向上することがわかりました。（テーブルを最適化して頻繁にアクセスする要素をより迅速に生成する）このハッシュテーブルの最適化の名前は何ですか？

この最適化の名前はありますか？

出典

2016-08-29 onno

一般に、このアプローチはMRUキャッシングと呼ばれます。しかし、ハッシュテーブルに特有のものではありません。 – rustyx

ありがとうございます。私は "キャッシュ"と "前に移動"グーグルは、キャッシュを実装するために使用されているハッシュテーブルについての記事を見つけた...私は読み取りアクセスを最適化するためのより多くのバリアントがあるかどうか、彼ら（とこれは）私のアプリケーションでそれらを試してみてください。 – onno

online-competitive algorithmsフィールドのlist update problemと非常によく似ています。

使用したソリューションはMTF (move to front)として知られています。このソリューションは2競合であることが知られています。つまり、未来を前もって知っている仮説的敵対者の倍の2倍になるでしょう。

bit algorithmよりも若干優れていることに注意してください。もう1つのビット+ランダム演算が必要ですが、競争相手は7-4です。

出典

2016-09-14 08:51:30

ありがとうございます**リスト更新の問題**本当に適切なようです！私は_hash table_関連リンクを探しましたが、充実したプロービングロケーションの実行がもちろん_list_と見なすことができると考えていたはずです。 – onno

あなたは大歓迎です。 FWIW、私はそれも魅力的な問題だと思います。コリジョンチェインを使用していた場合は、まさにこの問題であったはずです。プロービングはわずかに異なります。最後のアイテムをある位置に移動させ、すべてを戻していくコストは、リストのように一定ではありません。それにもかかわらず、私はこれがあなたにとって最も近い問題だと思います。 –

この種の最適化の最も一般的な用語はおそらくself-organizationです。

出典

2016-08-29 23:34:13 nwellnhof

ありがとうございます。これは確かに良い言葉です。私は、スワッピングを明らかにしている古い論文を見つけました：http://www.sciencedirect.com/science/article/pii/0020019085901036 私はまだ論文を買っていませんでしたが、最初のページが表示されていました。そこにはメソッドH2があります。 – onno

このハッシュテーブルの最適化の名前は何ですか？

答えて

関連する問題