LRUアルゴリズムを手書きで書く方法

背景
Redisのメモリ消費量が多すぎる場合は、メモリの淘汰が行われ、LRUアルゴリズムに基づいて淘汰されるのが一般的です.ではLRUアルゴリズムとは何でしょうか.
LRUアルゴリズムの概念
LRUはLeast Recently Usedの略で、略称は最近最も少ない.
つまり、Redisにはメモリがいっぱいで、最近最もアクセスが少ないデータを優先的に淘汰します.Javaではどのようなデータ構造で実現されていますか?1つはLinkedHashMapに基づくもので、1つは自分でデータ構造を設計し、チェーンテーブル+HashMapを使用するものです.
既製品がある以上、直接持ってきて使いましょう.なぜLinkedHashMapを使うのかと聞かれることがあります.LinkedHashMapのデータ構造を見てみましょう.
LinkedHashMapデータ構造
LinkedHashMapはHashMapを継承し、HashMapのすべての特性を持つと同時に、LinkedHashMapはheadとtailポインタを追加し、双方向チェーンテーブルを実現する.

/**
 * The head (eldest) of the doubly linked list.
 */
transient LinkedHashMap.Entry<K,V> head;

/**
 * The tail (youngest) of the doubly linked list.
 */
transient LinkedHashMap.Entry<K,V> tail;

LinkedHashMapはデフォルトで挿入順にデータを保存し、新しいデータは双方向チェーンテーブルの末尾に挿入します.

public static void main(String[] args) {
    LinkedHashMap<String,String> linkedHashMap = new LinkedHashMap<>();

    linkedHashMap.put("3","3");
    linkedHashMap.put("4","4");
    linkedHashMap.put("1","1");
    linkedHashMap.put("7","7");
    linkedHashMap.put("5","5");
    linkedHashMap.put("9","9");
    linkedHashMap.put("0","0");
    linkedHashMap.put("2","2");
    linkedHashMap.put("6","6");
    linkedHashMap.put("8","8");

    for (Map.Entry<String,String> entry : linkedHashMap.entrySet()){
        System.out.println(entry.getKey());
    }

}
=================    =================
3
4
1
7
5
9
0
2
6
8

LinkedHashMapでは、チェーンテーブルの末尾に最新のアクセスデータを配置する構造方法があります.

public static void main(String[] args) {
    LinkedHashMap<String,String> linkedHashMap = new LinkedHashMap<>(10,0.75f,true);

    linkedHashMap.put("3","3");
    linkedHashMap.put("4","4");
    linkedHashMap.put("1","1");
    linkedHashMap.put("7","7");
    linkedHashMap.put("5","5");
    linkedHashMap.put("9","9");
    linkedHashMap.put("0","0");
    linkedHashMap.put("2","2");
    linkedHashMap.put("6","6");
    linkedHashMap.put("8","8");

    linkedHashMap.get("4");
    linkedHashMap.get("7");
    for (Map.Entry<String,String> entry : linkedHashMap.entrySet()){
        System.out.println(entry.getKey());
    }

}
============    ===========
3
1
5
9
0
2
6
8
4
7

次のソースコードから、accessOrderがtrueの場合、アクセス順にソートし、アクセスしたデータをチェーンテーブルの末尾に配置し、falseの場合、挿入順にソートすることがわかります.

/**
 * The iteration ordering method for this linked hash map: true
 * for access-order, false for insertion-order.
 *
 * @serial
 */
final boolean accessOrder;

public LinkedHashMap(int initialCapacity,
                         float loadFactor,
                         boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

//     
public V get(Object key) {
    Node<K,V> e;
    if ((e = getNode(hash(key), key)) == null)
        return null;
    if (accessOrder)
        //        ，            
        afterNodeAccess(e);
    return e.value;
}

void afterNodeAccess(Node<K,V> e) { // move node to last
    LinkedHashMap.Entry<K,V> last;
    //                  
    if (accessOrder && (last = tail) != e) {
        //   b e     ，a e     
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        //             null
        p.after = null;
        //   e       ,  e           ，   e             a
        if (b == null)
            head = a;
        else
            b.after = a;
        //   e        ， e             b，  ， e           
        if (a != null)
            a.before = b;
        else
            last = b;
        //        ，      p      ，                  ，             
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
        //           
        tail = p;
        ++modCount;
    }
}

LRUキャッシュ実装
LinkedHashMapの特性を通じて、どのようにLRUアルゴリズムを実現して、自動的にチェーンテーブルのヘッダーの期限切れのデータを削除します

クラス継承LinkedHashMap

を定義する

public class LRULinkedMap<K,V> extends LinkedHashMap<K,V> {

    private int size;

    public LRULinkedMap(int initialCapacity,float loadFactor,boolean accessOrder){
        super(initialCapacity,loadFactor,accessOrder);
        this.size = initialCapacity;
    }

    /**
     *   LinkedHashMap removeEldestEntry  
     *  LRU        size ，         
     * @param eldest
     * @return
     */
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > size;
    }
}

テストクラス

public static void main(String[] args) {
    LRULinkedMap<String,String> linkedHashMap = new LRULinkedMap<>(5,0.75f,true);

    linkedHashMap.put("3","3");
    linkedHashMap.put("4","4");
    linkedHashMap.put("1","1");
    linkedHashMap.put("5","5");
    linkedHashMap.put("6","6");

    for (Map.Entry<String,String> entry : linkedHashMap.entrySet()){
        System.out.println(entry.getKey());
    }

    System.out.println("=========get(1)  1     =========");

    linkedHashMap.get("1");

    for (Map.Entry<String,String> entry : linkedHashMap.entrySet()){
        System.out.println(entry.getKey());
    }

    System.out.println("=========      ，       3 4=========");

    linkedHashMap.put("2","2");
    linkedHashMap.put("9","9");

    for (Map.Entry<String,String> entry : linkedHashMap.entrySet()){
        System.out.println(entry.getKey());
    }
}
=========    ========
3
4
1
5
6
=========get(1)  1     =========
3
4
5
6
1
=========      ，       3 4=========
5
6
1
2
9

removeEldestEntry
今のところ確かに効果があったようですが、なぜremoveEldestEntryを書き直せばいいのか疑問に思う人もいるかもしれません.では、removeEldestEntryメソッドのソースコードを見てみましょう.
LinkedHashMapでremoveEldestEntryはfalseをデフォルトで返します

protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;
}

removeEldestEntryがどこで使われているのか、falseがどのような役割を果たしているのか見てみましょう.
LinkedHashMapでは、LinkedHashMapの要素を削除するには、次の3つの条件を同時に満たす必要があるafterNodeInsertionという方法があります.

入参evictはtrue

LinkedHashMapの要素ヘッダノードはnull

ではありません.

removeEldestEntryメソッドはtrue

に戻る.

void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}

afterNodeInsertionメソッドは,HashMapに要素を追加して実行するメソッドであるが,詳細は本論文では紹介せず,HashMapの内部の実装ロジックを自分で見ることができる.
まとめ
本文はRedisのキャッシュ淘汰戦略に基づいてLRUアルゴリズムの背景,基本概念を紹介した.LinkedHashMapの特性に基づいて簡易版のLRUアルゴリズムを実現し、LinkedHashMap内部の基本原理を紹介して、LRUアルゴリズムの実現をよりよく理解するのに役立ちます.