私は、キャッシュ排除ポリシーを実装する単純なデータ構造に取り組んでいます。実装したい2つの可能なシナリオは、LRUとMRUです。
どのキャッシュブロックが最も最近使用されたか、または最も最近使用されなかったかを知るために、キーがおそらく時間（または単に自動インクリメントされた整数）であるマップのようなデータ構造を探しています。そして、値はブロックのIDです。
挿入時にキーでデータを並べ替え、O（1）時間で特定のキーの値を取得する既存のデータ構造はありますか？
たとえば、JavaのHashMapには定数時間ルックアップがありますが、実装しているアルゴリズムに応じて、すべてのキーを取得して並べ替え、最後または最初を選択する必要があります。SortedMapは私が何をすべきか？LRUおよびMRUの実装でうまく機能する他のデータ構造を提案しますか？
ありがとう
そうですSortedMap、挿入のキーに従ってエントリをソートします。の最もよく知られている実装はSortedMapでTreeMap、エントリを平衡二分木として格納します。
javadocから:
キーの全体的な順序付けをさらに提供する {@link Map} 。マップは、そのキーの {@linkplain Comparable 自然順序付け} に従って、または通常は並べ替えられたマップの作成時に提供される {@link Comparator} に従って順序付けられます。この順序は、並べ替えられたマップのコレクション ビュー (entrySet、keySet、および values メソッドによって返される) を反復処理するときに反映されます。順序付けを利用するために、いくつかの追加操作が提供されています。
エントリとキーは から昇順でソートされて返されますが、SortedMapメソッドfirstKey()ともありlastKey()、これも役立つ場合があります。
特に LRU の場合: Java で最も一般的な方法はLinkedHashMap、メソッドを持つを使用することremoveEldestEntry(Map.Entry)です。デフォルトでは何もしませんが、クラスを簡単に拡張してそのメソッドを実装できます。詳細については、こちらをご覧ください。