手書きの最も単純なLRUアルゴリズム

1 LRUとは何か

LRU (Least Recently Used) は、最も最近使用されていないデータです。その基本的な考え方は、「データが最近アクセスされた場合、将来アクセスされる可能性が高くなる」というものです。したがって、LRU アルゴリズムは、過去のアクセスレコードに従ってデータを並べ替えます。十分なスペースがない場合は、最も最近使用されていないデータが削除されます。

2 LRU実装の原則

LRU アルゴリズムは最近使用されたデータを優先するため、ソートをサポートするデータ構造が必要であり、リンクリストが非常に適しています。

配列を検討してみませんか?

LRU アルゴリズムは一般的にアクセス頻度の高いシナリオで使用されるため、データの移動は頻繁に行われます。配列を移動したら、移動した値の後ろにあるすべてのデータの位置を変更する必要があります。これは非効率的であり、推奨されません。

3. 双方向リンクリストのLinkedHashMap

先ほど、LRU アルゴリズムの実装はリンクリストを使用して実装できることを分析しました。Java の LinkedHashMap は双方向のリンクリストです。

LinkedHashMap は HashMap のサブクラスです。HashMap データ構造に基づいて、すべてのエントリをリンクする双方向リンクリストも維持します。このリンクリストは反復順序を定義します。これは通常、データが挿入される順序です。

LinkedHashMap のソースコードを見てみましょう。

ソースコードの定義から、accessOrder プロパティで LinkedHashMap をトラバースする順序を指定できることがわかります。true はアクセス順序、false は挿入順序を意味し、デフォルトは false です。

LRU はアクセス順序に敏感なので、単純に検証するために true を使用します。

パブリッククラスLRUTest {
公共 静的void main(String[] args) {
        LinkedHashMap<String, Object> マップ = new LinkedHashMap<>(16, 0.75f, true );
        map.put( "a" 、1);
        map.put( "b" 、2);
        map.put( "c" 、3);
        System.out.println ( "get の前に " + map) ;
        マップを取得します。
        System.out.println ( "get 後" + map) ;
    }}

結果は次のとおりです。

前に {a=1, b=2, c=3} を取得します
取得後{b=2, c=3, a=1}

accessOrder = true を設定すると、LinkedHashMap をアクセス順にソートできることがわかります。

では、LinkedHashMap はどのようにそれを実現するのでしょうか?

getメソッドを見てみましょう

パブリックV get(オブジェクトキー) {
    ノード<K,V> e;
    // ノードを取得する
    ((e = getNode(hash( key ), key )) == null の場合)
戻る ヌル;
    // accessOrder = trueの場合、afterNodeAccess メソッドを実行します
    if (アクセス順序)
        afterNodeAccess(e);
 e.valueを返します。
 }

afterNodeAccess メソッドをもう一度見てみると、ノードが移動されていることがわかります。ここまでで、ノードを移動する原理は理解できました。

 void afterNodeAccess(Node<K,V> e) { //ノードを移動する 最後 
   LinkedHashMap.Entry<K,V>最後;
   if (accessOrder && ( last = tail ) != e) {
       LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e、b = p.before、a = p.after ; p.after = null ; if (b == null )
           ヘッド = a;それ以外 
           b. after = a; if (a != null )
           a.before = b;そうでなければ 
最後= b;
       （最後== null ）の場合
           ヘッド = p;それ以外の場合{
           p.before =最後;
最後. after = p; } 末尾 = p; ++modCount; }}

現在、LinkedHashMap を LRU として使用する場合、容量が限られている場合に古いデータをどのように削除するかという、まだ気になる問題があります。

戻ってputメソッドを見てみましょう

公開V put(Kキー、V値) {
 putVal(hash( key ), key , value, false , true )を返します。
 }
最終的な V putVal( intハッシュ、 Kキー、 V 値、 boolean onlyIfAbsent、 boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    ((tab = table ) == null || (n = tab.length) == 0)の場合
        n = (タブ = resize()).length;
    ((p = tab[i = (n - 1) & hash] ) == null の場合
        tab[i] = newNode(ハッシュ、キー、値、 null );
それ以外{
        ノード<K,V> e; K k;
        if (p.hash == ハッシュ &&
            ((k = p.key ) == key || ( key != null && key .equals(k))))
            e = p;
そうでない場合 (p TreeNode のインスタンス)
            e = ((TreeNode<K,V>)p).putTreeVal(this、タブ、ハッシュ、キー、値);
それ以外{
 ( int binCount = 0; ; ++binCount) {
                ((e = p.next ) == null の場合) {
                    p.next = newNode(ハッシュ、キー、値、 null );
                    if (binCount >= TREEIFY_THRESHOLD - 1) // 1番目は-1
                        treeifyBin(タブ、ハッシュ);
                    壊す;
                }
                if (e.hash == hash &&
                    ((k = e.key ) == key || ( key != null && key .equals(k))))
                    壊す;
                p = e;
            }
        }
        if (e != null ) { // 既存のマッピング 鍵 
            V 古い値 = e.value;
            if (!onlyIfAbsent || oldValue == null )
                e.value = 値;
            afterNodeAccess(e);
古い値を返します。
        }
    }
    ++modCount;
    if (++サイズ> しきい値)
        サイズを変更します。
    afterNodeInsertion(削除);
戻る ヌル;
 }
 void afterNodeInsertion(boolean evict) { // 最長のものを削除する可能性がある
    LinkedHashMap.Entry<K,V>を最初に;
    if (evict && ( first = head) != null && removeEldestEntry( first )) {
        Kキー=最初の.キー;
        ノードを削除します(ハッシュ(キー),キー, null , false , true );
    }
 }

put メソッドをステップごとに見ていくと、removeEldestEntry(first) メソッドが true を返すとヘッドが削除され、最近使用されていないデータが排除されることがわかります。完全に LRU に準拠しています。

4 最も単純なLRU実装

上記の分析に基づいて、最も単純なLRUを次のように実装できます。

パブリッククラスLRUCache<K,V>はLinkedHashMap<K,V>を拡張します。
      プライベートintキャッシュサイズ;
パブリックLRUCache( intキャッシュサイズ){
      // 注意: ここでは accessOrder = trueが必要です 
      super(キャッシュサイズ、0.75f、 true );
      this.cacheSize = キャッシュサイズ;
  }
  /**
   * 要素数がキャッシュ容量を超えているかどうかを判断し、超えている場合は削除します。
   */
  @オーバーライド
  保護されたブール値の長男エントリを削除します(Map.Entry<K, V> 長男) {
戻る サイズ() > キャッシュサイズ;
  }
 }