java LRU(Least Recently Used) detailed explanation
LRU is the abbreviation of Least Recently Used. It is translated as "latest use". LRU cache is implemented using this principle. Simply put, it is to cache a certain amount of data. When the set threshold is exceeded, some expired data will be deleted. For example, we cache 10,000 pieces of data. When the data is less than 10,000, you can add it at will. When it exceeds 10,000, you need to add new data. At the same time, you need to delete the expired data to ensure that we can cache 10,000 pieces of data at the maximum. How to determine which expired data to delete? If you use the LRU algorithm to implement it, you will delete the oldest data. Without saying much, let’s talk about the Java version of LRU cache implementation.
There are usually two options for implementing LRU cache in Java. One is to use LinkedHashMap, and the other is to design your own data structure and use linked list + HashMap.
LinkedHashMap implementation of LRU Cache
LinkedHashMap itself has implemented sequential storage. By default, it is stored in the order of adding elements. It can also enable storage in the order of access, that is, the recently read data is placed at the front and the earliest read data is placed at the end. Then it also has a method to determine whether to delete the oldest data. The default is to return false, that is, not delete data. The method of using LinkedHashMap to implement LRU cache is to implement simple expansion of LinkedHashMap. There are two ways to extend, one is inheritance and the other is delegation. The specific method is used to depend on personal preferences.
//A constructor of LinkedHashMap. When the parameter accessOrder is true, it will be sorted in the order of access. The most recent access is placed first and the earliest access is placed behind public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) { super(initialCapacity, loadFactor); this.accessOrder = accessOrder;}//LinkedHashMap comes with method to determine whether to delete the oldest element. It returns false by default, that is, it does not delete old data. //What we need to do is rewrite this method and delete old data when certain conditions are met protected boolean removeEldestEntry(Map.Entry<K,V> eldest) { return false;} LRU cache LinkedHashMap(inheritance) implementation
The inheritance method is relatively simple to implement, and the Map interface is implemented. When using a multi-threaded environment, you can use the Collections.synchronizedMap() method to implement thread-safe operations.
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 elderly) { 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(); }}This is a relatively standard implementation. It is still a bit cumbersome to write like this in actual use. When writing it like this more practical method, it saves the trouble of seeing a class separately.
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> elderly) { return size() > cacheSize; }}; LRU cache LinkedHashMap(delegation) implementation
Delegation method implementation is more elegant, but since the Map interface is not implemented, thread synchronization needs to be done by yourself.
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; // Calculate the capactiy of the hashmap based on cacheSize and loading factors. +1 ensure that the hashmap expansion will not be triggered when the cacheSize upper limit is reached. 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 elderly) { 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 Cache's linked list + HashMap implementation
Note: This implementation is non-threaded. If used in a multi-threaded environment, you need to add synchronized to relevant methods to achieve thread-safe operations.
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; 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; }} FIFO implementation of LinkedHashMap
FIFO is the abbreviation of First Input First Output, which is often called first-in, first-out. By default, LinkedHashMap is saved in the order of addition. We just need to rewrite the removeEldestEntry method to easily implement a FIFO cache. The simplified version of the implementation code is as follows.
final int cacheSize = 5;LinkedHashMap<Integer, String> lru = new LinkedHashMap<Integer, String>() { @Override protected boolean removeEldestEntry(Map.Entry<Integer, String> elderly) { return size() > cacheSize; }}; Call Example
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("=================================================================================================================================================================== 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(); }}Running results
"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/jce.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/ext/dnsns.jar;C:/Program Files (x86)/Java/jdk1.6.0_10/jre/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 Mainstart...================================================================================================================================================================================================================================================================================================================================================================================================================================================================== LinkedHashMap(inheritance) implementation======================================================================================================================================================================================================================================================================================== 1:11 2:11 3:11 4:11 5:11 5:11 6:66 2:11 7:77 4:11 =================================== FIFO LinkedHashMap default implementation=================================================={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 0Thank you for reading, I hope it can help you. Thank you for your support for this site!