#LRU は Least Recent Used の略で、「最も最近使用されていない」という意味です。LRU キャッシュはこの原理を使用して実装されています。簡単に言うと、一定量のデータをキャッシュします。しきい値を設定すると、期限切れのデータの一部が削除されます。
たとえば、10,000 件のデータをキャッシュします。データが 10,000 件未満の場合は任意に追加できますが、10,000 件を超える場合は、新しいデータを追加し、期限切れのデータを削除する必要があります。最大 10,000 個のデータをキャッシュします。では、どの期限切れデータを削除するかを決定するにはどうすればよいでしょうか? LRU アルゴリズムを使用して実装されている場合、最も古いデータが削除されます。
Java バージョンの LRU キャッシュ実装について話しましょう: (推奨:
java ビデオ チュートリアル )
Java で LRU キャッシュを実装するには、通常 2 つのオプションがあります。 LinkedHashMap を使用する方法の 1 つは、リンク リスト HashMap を使用してデータ構造を自分で設計する方法です。
#LRU キャッシュの LinkedHashMap 実装#LinkedHashMap 自体がシーケンシャル ストレージを実装しています。デフォルトでは、要素は追加された順に保存されますが、アクセス順に保存することもできます。つまり、最後に読み取られたデータが先頭に配置され、最も古い読み取られたデータが最後に配置されます。次に、最新のデータを削除するかどうかの判断も行いますが、古いデータのメソッドはデフォルトで false (データは削除されません) を返します。
LinkedHashMap を使用して LRU キャッシュを実装する方法は、LinkedHashMap の単純な拡張を実装することです。拡張方法は 2 つあり、1 つは継承で、もう 1 つは委任です。
//LinkedHashMap的一个构造函数，当参数accessOrder为true时，即会按照访问顺序排序，最近访问的放在最前，最早访问的放在后面
public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
//LinkedHashMap自带的判断是否删除最老的元素方法，默认返回false，即不删除老数据
//我们要做的就是重写这个方法，当满足一定条件时删除老数据
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}ログイン後にコピー
LRU キャッシュ LinkedHashMap (継承) 実装
継承メソッドを使用して実装するのは比較的簡単で、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<K, V> extends LinkedHashMap<K, V> {
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<K, V> entry : entrySet()) {
sb.append(String.format("%s:%s ", entry.getKey(), entry.getValue()));
}
return sb.toString();
}
}ログイン後にコピー
これは比較的標準的な実装ですが、実際に使用する場合、このように記述するのはまだ少し面倒ですより現実的な方法は、クラス単体で見る手間を省いて次のように書くことです
final int cacheSize = 100;
Map<String, String> map = new LinkedHashMap<String, String>((int) Math.ceil(cacheSize / 0.75f) + 1, 0.75f, true) {
@Override
protected boolean removeEldestEntry(Map.Entry<String, String> eldest) {
return size() > cacheSize;
}
};ログイン後にコピー
LRUキャッシュLinkedHashMap(委任)実装
委任方法はより洗練されていますが、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<K, V> {
private final int MAX_CACHE_SIZE;
private final float DEFAULT_LOAD_FACTOR = 0.75f;
LinkedHashMap<K, V> 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<Map.Entry<K, V>> 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 キャッシュのリンク リスト HashMap の実装
注: この実装はスレッドセーフではありません。マルチスレッド環境で使用する場合、スレッドセーフな操作を実現するには、関連するメソッドに synchronized を追加する必要がありますpackage cn.lzrabbit.structure.lru;
import java.util.HashMap;
/**
* Created by liuzhao on 14-5-12.
*/
public class LRUCache1<K, V> {
private final int MAX_CACHE_SIZE;
private Entry first;
private Entry last;
private HashMap<K, Entry<K, V>> hashMap;
public LRUCache1(int cacheSize) {
MAX_CACHE_SIZE = cacheSize;
hashMap = new HashMap<K, Entry<K, V>>();
}
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<K, V> 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<K, V> 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<K, V> {
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<Integer, String> lru = new LinkedHashMap<Integer, String>() {
@Override
protected boolean removeEldestEntry(Map.Entry<Integer, String> 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<Integer, String> 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 <T> void lruCache2() {
System.out.println();
System.out.println("===========================LRU LinkedHashMap(inheritance)实现===========================");
LRUCache2<Integer, String> 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<Integer, String> 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<Integer, String> lru = new LinkedHashMap<Integer, String>() {
@Override
protected boolean removeEldestEntry(Map.Entry<Integer, String> 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ログイン後にコピー
以上がJavaでのLRUキャッシュの実装の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。
![[Web フロントエンド] Node.js クイック スタート](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
