JAva LRU(Least Recenly Used)詳細およびインスタンスコード

JAva LRU(Least Recenly Used)詳細
LRUはLeast Recently Usedの略で、翻訳すると「最近最も少ない使用」です.LRUキャッシュはこの原理を使って実現されています.簡単に言えば、一定量のデータをキャッシュし、設定したしきい値を超えると、期限切れのデータを削除します.例えば、10000個のデータをキャッシュし、10000個未満のデータを勝手に追加することができます.10000を超える時新しいデータを追加する必要があって、同時に期限切れのデータを削除して、私達の最大キャッシュ10000条を確保して、それではどの期限切れのデータを削除することをどのように確定して、LRUアルゴリズムを採用して実現するならば最も古いデータを削除して、くだらない話は多くなくて、下の面でJava版のLRUキャッシュは実現します
JavaでLRUキャッシュを実装するには、LinkedHashMapを使用するか、データ構造を独自に設計するか、チェーンテーブル+HashMapを使用するかの2つの選択肢があります.
LRU CacheのLinkedHashMap実装
LinkedHashMap自体は既にシーケンスストレージを実現しており、デフォルトでは要素の追加順に格納されているが、アクセス順に格納することも可能である.すなわち、最近読み込んだデータを一番前に、一番早く読み込んだデータを一番後ろに、そして一番古いデータを削除するかどうかを判断する方法があり、デフォルトではfalseに戻り、つまりデータを削除しない.LinkedHashMapを使用してLRUキャッシュを実現する方法はLinkedHashMapに対して簡単な拡張を実現することであり、拡張方式は2種類あり、1つはinheritanceであり、1つはdelegationであり、具体的にどのような方法で個人の好みを見るか

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

//LinkedHashMap                ，    false，       
//             ，             
protected boolean removeEldestEntry(Map.Entry eldest) {
    return false;
}

LRUキャッシュLinkedHashMap(inheritance)実装
Inheritance方式の実装は比較的簡単で、Mapインタフェースを実現し、マルチスレッド環境で使用する場合はCollections.synchronizedMap()法を使用してスレッドセキュリティ操作を実現できる

package cn.lzrabbit.structure.lru;

import java.util.LinkedHashMap;
import java.util.Map;

/**
 * Created by liuzhao on 14-5-15.
 */
public class LRUCache2 extends LinkedHashMap {
  private final int MAX_CACHE_SIZE;

  public LRUCache2(int cacheSize) {
    super((int) Math.ceil(cacheSize / 0.75) + 1, 0.75f, true);
    MAX_CACHE_SIZE = cacheSize;
  }

  @Override
  protected boolean removeEldestEntry(Map.Entry eldest) {
    return size() > MAX_CACHE_SIZE;
  }

  @Override
  public String toString() {
    StringBuilder sb = new StringBuilder();
    for (Map.Entry entry : entrySet()) {
      sb.append(String.format("%s:%s ", entry.getKey(), entry.getValue()));
    }
    return sb.toString();
  }
}

 これは比較的標準的な実現でしょうが、実際の使用ではこのように書くのは煩雑で、より実用的な方法では以下のように書くことで、単独で1つのクラスに会う手間を省くことができます.

final int cacheSize = 100;
Map map = new LinkedHashMap((int) Math.ceil(cacheSize / 0.75f) + 1, 0.75f, true) {
  @Override
  protected boolean removeEldestEntry(Map.Entry eldest) {
  return size() > cacheSize;
  }
};

 LRUキャッシュLinkedHashMap(delegation)実装
delegation方式はより優雅に実現されるが,Mapインタフェースが実現されていないため,スレッド同期は自分で行う必要がある.

package cn.lzrabbit.structure.lru;

import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Set;

/**
 * Created by liuzhao on 14-5-13.
 */
public class LRUCache3 {

  private final int MAX_CACHE_SIZE;
  private final float DEFAULT_LOAD_FACTOR = 0.75f;
  LinkedHashMap map;

  public LRUCache3(int cacheSize) {
    MAX_CACHE_SIZE = cacheSize;
    //  cacheSize       hashmap capactiy，+1     cacheSize       hashmap   ，
    int capacity = (int) Math.ceil(MAX_CACHE_SIZE / DEFAULT_LOAD_FACTOR) + 1;
    map = new LinkedHashMap(capacity, DEFAULT_LOAD_FACTOR, true) {
      @Override
      protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > MAX_CACHE_SIZE;
      }
    };
  }

  public synchronized void put(K key, V value) {
    map.put(key, value);
  }

  public synchronized V get(K key) {
    return map.get(key);
  }

  public synchronized void remove(K key) {
    map.remove(key);
  }

  public synchronized Set> getAll() {
    return map.entrySet();
  }

  public synchronized int size() {
    return map.size();
  }

  public synchronized void clear() {
    map.clear();
  }

  @Override
  public String toString() {
    StringBuilder sb = new StringBuilder();
    for (Map.Entry entry : map.entrySet()) {
      sb.append(String.format("%s:%s ", entry.getKey(), entry.getValue()));
    }
    return sb.toString();
  }
}

 LRU Cacheのチェーンテーブル+HashMap実装
 注意:これは非スレッドセキュリティとして実装されます.マルチスレッド環境で使用する場合は、関連メソッドにsynchronizedを追加してスレッドセキュリティ操作を実装する必要があります.

package cn.lzrabbit.structure.lru;


import java.util.HashMap;

/**
 * Created by liuzhao on 14-5-12.
 */
public class LRUCache1 {

  private final int MAX_CACHE_SIZE;
  private Entry first;
  private Entry last;

  private HashMap> hashMap;

  public LRUCache1(int cacheSize) {
    MAX_CACHE_SIZE = cacheSize;
    hashMap = new HashMap>();
  }

  public void put(K key, V value) {
    Entry entry = getEntry(key);
    if (entry == null) {
      if (hashMap.size() >= MAX_CACHE_SIZE) {
        hashMap.remove(last.key);
        removeLast();
      }
      entry = new Entry();
      entry.key = key;
    }
    entry.value = value;
    moveToFirst(entry);
    hashMap.put(key, entry);
  }

  public V get(K key) {
    Entry entry = getEntry(key);
    if (entry == null) return null;
    moveToFirst(entry);
    return entry.value;
  }

  public void remove(K key) {
    Entry entry = getEntry(key);
    if (entry != null) {
      if (entry.pre != null) entry.pre.next = entry.next;
      if (entry.next != null) entry.next.pre = entry.pre;
      if (entry == first) first = entry.next;
      if (entry == last) last = entry.pre;
    }
    hashMap.remove(key);
  }

  private void moveToFirst(Entry entry) {
    if (entry == first) return;
    if (entry.pre != null) entry.pre.next = entry.next;
    if (entry.next != null) entry.next.pre = entry.pre;
    if (entry == last) last = last.pre;

    if (first == null || last == null) {
      first = last = entry;
      return;
    }

    entry.next = first;
    first.pre = entry;
    first = entry;
    entry.pre = null;
  }

  private void removeLast() {
    if (last != null) {
      last = last.pre;
      if (last == null) first = null;
      else last.next = null;
    }
  }


  private Entry getEntry(K key) {
    return hashMap.get(key);
  }

  @Override
  public String toString() {
    StringBuilder sb = new StringBuilder();
    Entry entry = first;
    while (entry != null) {
      sb.append(String.format("%s:%s ", entry.key, entry.value));
      entry = entry.next;
    }
    return sb.toString();
  }

  class Entry {
    public Entry pre;
    public Entry next;
    public K key;
    public V value;
  }
}

LinkedHashMapのFIFO実装
FIFOはFirst Input First Outputの略で、いわゆる先入先出ですが、デフォルトではLinkedHashMapは追加順に保存されています.removeEldestEntryメソッドを書き換えるだけで簡単にFIFOキャッシュを実現できます.簡略化版の実装コードは以下の通りです.

final int cacheSize = 5;
LinkedHashMap lru = new LinkedHashMap() {
  @Override
  protected boolean removeEldestEntry(Map.Entry eldest) {
  return size() > cacheSize;
  }
};

呼び出しの例

package cn.lzrabbit.structure.lru;

import cn.lzrabbit.ITest;

import java.util.LinkedHashMap;
import java.util.Map;

/**
 * Created by liuzhao on 14-5-15.
 */
public class LRUCacheTest {

  public static void main(String[] args) throws Exception {
    System.out.println("start...");

    lruCache1();
    lruCache2();
    lruCache3();
    lruCache4();
   
    System.out.println("over...");
  }
 

 static  void lruCache1() {
    System.out.println();
    System.out.println("===========================LRU     ===========================");
    LRUCache1 lru = new LRUCache1(5);
    lru.put(1, "11");
    lru.put(2, "11");
    lru.put(3, "11");
    lru.put(4, "11");
    lru.put(5, "11");
    System.out.println(lru.toString());
    lru.put(6, "66");
    lru.get(2);
    lru.put(7, "77");
    lru.get(4);
    System.out.println(lru.toString());
    System.out.println();
  }


static   void lruCache2() {
    System.out.println();
    System.out.println("===========================LRU LinkedHashMap(inheritance)  ===========================");
    LRUCache2 lru = new LRUCache2(5);
    lru.put(1, "11");
    lru.put(2, "11");
    lru.put(3, "11");
    lru.put(4, "11");
    lru.put(5, "11");
    System.out.println(lru.toString());
    lru.put(6, "66");
    lru.get(2);
    lru.put(7, "77");
    lru.get(4);
    System.out.println(lru.toString());
    System.out.println();
  }

 static void lruCache3() {
    System.out.println();
    System.out.println("===========================LRU LinkedHashMap(delegation)  ===========================");
    LRUCache3 lru = new LRUCache3(5);
    lru.put(1, "11");
    lru.put(2, "11");
    lru.put(3, "11");
    lru.put(4, "11");
    lru.put(5, "11");
    System.out.println(lru.toString());
    lru.put(6, "66");
    lru.get(2);
    lru.put(7, "77");
    lru.get(4);
    System.out.println(lru.toString());
    System.out.println();
  }

 static void lruCache4() {
    System.out.println();
    System.out.println("===========================FIFO LinkedHashMap    ===========================");
    final int cacheSize = 5;
    LinkedHashMap lru = new LinkedHashMap() {
      @Override
      protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > cacheSize;
      }
    };
    lru.put(1, "11");
    lru.put(2, "11");
    lru.put(3, "11");
    lru.put(4, "11");
    lru.put(5, "11");
    System.out.println(lru.toString());
    lru.put(6, "66");
    lru.get(2);
    lru.put(7, "77");
    lru.get(4);
    System.out.println(lru.toString());
    System.out.println();
  }

}

実行結果

"C:\Program Files (x86)\Java\jdk1.6.0_10\bin\java" -Didea.launcher.port=7535 "-Didea.launcher.bin.path=C:\Program Files (x86)\JetBrains\IntelliJ IDEA 13.0.2\bin" -Dfile.encoding=UTF-8 -classpath "C:\Program Files (x86)\Java\jdk1.6.0_10\jre\lib\charsets.jar;C:\Program Files (x86)\Java\jdk1.6.0_10\jre\lib\deploy.jar;C:\Program Files (x86)\Java\jdk1.6.0_10\jre\lib\javaws.jar;C:\Program Files (x86)\Java\jdk1.6.0_10\jre\lib\jce.jar;C:\Program Files (x86)\Java\jdk1.6.0_10\jre\lib\jsse.jar;C:\Program Files (x86)\Java\jdk1.6.0_10\jre\lib\management-agent.jar;C:\Program Files (x86)\Java\jdk1.6.0_10\jre\lib\plugin.jar;C:\Program Files (x86)\Java\jdk1.6.0_10\jre\lib\resources.jar;C:\Program Files (x86)\Java\jdk1.6.0_10\jre\lib\rt.jar;C:\Program Files (x86)\Java\jdk1.6.0_10\jre\lib\ext\dnsns.jar;C:\Program Files (x86)\Java\jdk1.6.0_10\jre\lib\ext\localedata.jar;C:\Program Files (x86)\Java\jdk1.6.0_10\jre\lib\ext\sunjce_provider.jar;C:\Program Files (x86)\Java\jdk1.6.0_10\jre\lib\ext\sunmscapi.jar;C:\Program Files (x86)\Java\jdk1.6.0_10\jre\lib\ext\sunpkcs11.jar;D:\SVN\projects\Java\Java.Algorithm\target\test-classes;D:\SVN\projects\Java\Java.Algorithm\target\classes;C:\Program Files (x86)\JetBrains\IntelliJ IDEA 13.0.2\lib\idea_rt.jar" com.intellij.rt.execution.application.AppMain Main
start...

===========================LRU     ===========================
5:11 4:11 3:11 2:11 1:11 
4:11 7:77 2:11 6:66 5:11 


===========================LRU LinkedHashMap(inheritance)  ===========================
1:11 2:11 3:11 4:11 5:11 
5:11 6:66 2:11 7:77 4:11 


===========================LRU LinkedHashMap(delegation)  ===========================
1:11 2:11 3:11 4:11 5:11 
5:11 6:66 2:11 7:77 4:11 


===========================FIFO LinkedHashMap    ===========================
{1=11, 2=11, 3=11, 4=11, 5=11}
{3=11, 4=11, 5=11, 6=66, 7=77}

over...

Process finished with exit code 0

読書に感謝して、みんなを助けることができることを望んで、みんなの当駅に対する支持に感謝します!