leecodeアルゴリズム「146.LRUキャッシュメカニズム」には注釈が詳しく、簡単明瞭である.

leecodeアルゴリズム「146.LRUキャッシュメカニズム」には注釈が詳しく、簡単明瞭である.
原題の内容
あなたが把握しているデータ構造を運用し、LRU(最近最も少ない使用)キャッシュメカニズムを設計し、実現します.データgetの取得とデータputの書き込みをサポートする必要があります.
取得データget(key)-キー(key)がキャッシュに存在する場合、キーの値(常に正数)が取得され、そうでない場合は-1が返されます.書き込みデータput(key,value)-鍵が存在しない場合、そのデータ値が書き込まれます.キャッシュ容量が上限に達した場合、新しいデータを書き込む前に、最近最も少ないデータ値を削除して、新しいデータ値にスペースを残す必要があります.
ステップ:
O(1)時間の複雑さの中でこの2つの操作を完了できますか?
例:
LRUCache cache=new LRUCache(2/*キャッシュ容量*/);

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       //     1
cache.put(3, 3);    //          2   
cache.get(2);       //    -1 (   )
cache.put(4, 4);    //          1   
cache.get(1);       //    -1 (   )
cache.get(3);       //     3
cache.get(4);       //     4

ソース:力ボタン(LeetCode)リンク:https://leetcode-cn.com/problems/lru-cache著作権はインターネットの所有に帰属する.商業転載は公式の授権に連絡してください.非商業転載は出典を明記してください.
解法:LinkedHashMap

LinkedHashMapとHashMapの区別ほとんどの場合、スレッドセキュリティの問題に関係しない限り、Mapは基本的にHashMapを使用することができますが、HashMapには反復HashMapの順序がHashMapの配置の順序ではなく、無秩序であるという問題があります.HashMapのこの欠点は往々にして悩みをもたらす.一部のシーンでは、秩序あるMapを期待しているからだ.これが私たちのLinkedHashMapです.小さなDemoを見てください.

public static void main(String[] args) {
    Map<String, String> map = new LinkedHashMap<String, String>();
    map.put("apple", "  ");
    map.put("watermelon", "  ");
    map.put("banana", "  ");
    map.put("peach", "  ");

    Iterator iter = map.entrySet().iterator();
    while (iter.hasNext()) {
        Map.Entry entry = (Map.Entry) iter.next();
        System.out.println(entry.getKey() + "=" + entry.getValue());
    }
}

出力は、apple=アップルwatermelon=スイカbanana=バナナpeach=桃が見られますが、使用上はLinkedHashMapとHashMapの違いがLinkedHashMapで秩序があります.上の例では挿入順にソートしています.また、LinkedHashMapには、これに基づいてアクセス順(get,put)に従ってソートするかどうかを決定するパラメータがあります.挿入順に基づいてソートしていることを覚えておいてください.後でソースコードを見て、なぜか分かります.例を見てみましょう.

public static void main(String[] args) {
    Map<String, String> map = new LinkedHashMap<String, String>(16,0.75f,true);
    map.put("apple", "  ");
    map.put("watermelon", "  ");
    map.put("banana", "  ");
    map.put("peach", "  ");

    map.get("banana");
    map.get("apple");

    Iterator iter = map.entrySet().iterator();
    while (iter.hasNext()) {
        Map.Entry entry = (Map.Entry) iter.next();
        System.out.println(entry.getKey() + "=" + entry.getValue());
    }
}

出力:watermelon=スイカpeach=桃banana=バナナapple=リンゴはバナナとリンゴが元のランキングに基づいてまた後ろに並んでいるのが見えます.
LinkedHashMapを使用してLRUキャッシュLRU、すなわちLeast Recently Usedを実現し、最近最も使用されていない、つまりキャッシュがいっぱいになると、最近最もアクセスしていないデータを優先的に淘汰します.私たちのLinkedHashMapはちょうどこの特性を満たしています.なぜですか.accessOrderをtrueとすると、最新のアクセス(getまたはput(更新操作))のデータがキューの末尾に失われ、双方向キューのヘッダが最も頻繁に使用されないデータになります.たとえば,1 2 3の3つのEntryがあれば,1を訪問し,1を末尾に移動する2 3 1である.アクセスのたびにアクセスしたデータを双方向キューの末尾に移動すると、データを淘汰するたびに、双方向キューの先頭のデータが最もアクセスしにくいデータではないでしょうか.言い換えれば、双方向チェーンテーブルの一番先のデータは淘汰されるデータです.さらにLinkedHashMapでは、LRUキャッシュを実装するために提供されるremoveEldestEntry(Map.Entry eldest)メソッドも提供されています.この方法は、新しいエントリを追加するたびに最も古いエントリを削除するインプリメンテーションプログラムを提供し、デフォルトでfalseを返すことができる.さあ、皆さんに粗末なLRUキャッシュをあげましょう.

public class LRUCache extends LinkedHashMap
{
    public LRUCache(int maxSize)
    {
        super(maxSize, 0.75F, true);
        maxElements = maxSize;
    }

    protected boolean removeEldestEntry(java.util.Map.Entry eldest)
    {
        //     ，      Map   ，             ，          。
        return size() > maxElements;
    }

    private static final long serialVersionUID = 1L;
    protected int maxElements;
}

コード#コード#

class LRUCache extends LinkedHashMap<Integer, Integer> {
    //      
    private int capacity;

    //        false    true           
    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return capacity < super.size();
    }

    //     ， accessOrder true ，  
    public LRUCache(int capacity) {
        super(capacity, 0.75F, true);
        this.capacity = capacity;

    }

    public int get(int key) {
        return super.getOrDefault(key, -1);
    }

    public void put(int key, int value) {
        super.put(key, value);
    }

}