LRU algorithm , Also known as the least recently used algorithm , We can use this algorithm to implement cache mechanism , Simply put, it is to cache a certain amount of data , When exceeding the set threshold, some expired data will be deleted , In this article, we'll take a look at how to implement it LRU
Cache, Let's do it in two ways .
<> be based on LinkedHashMap
stay java In the collection class of LinkedHashMap class , When parameter accessOrder by true When , It will be sorted in the order of access , The last to be visited comes first , The first to be visited is at the back , So we can do it LRU Algorithm . This method is relatively simple , The code is as follows ：
public class LRU { private final int CAPACITY=0; private
LinkedHashMap<Integer,Integer> cache; public LRU(int capacity){ cache=new
LinkedHashMap<Integer,Integer>(capacity,0.75f,true){ @Override protected
boolean removeEldestEntry(java.util.Map.Entry<Integer, Integer> eldest) {
return size()>CAPACITY; } }; } public int get(int key) { return
cache.getOrDefault(key, -1); } public void put(int key, int value) {
cache.put(key, value); } }
<> Linked list +HashMap
The second way is to use linked lists +HashMap To achieve , We need to implement a series of methods ourselves , The code is as follows ：
import java.util.Collection; import java.util.HashMap; import
java.util.Iterator; /** * LRUCache Linked list +hashmap How to realize * @author shinelon * */
public class LRUCache2<K,V>{ public final int CACHE_SIZE; public Entry frist;
public Entry last; public HashMap<K,Entry<K,V>> hashMap; public LRUCache2(int
cacheSize){ this.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()>=CACHE_SIZE){ hashMap.remove(last.key); removeLast(); }
entry=new Entry(); entry.key=key; } entry.value=value; moveToFrist(entry);
hashMap.put(key, entry); } public V get(K key){ Entry<K,V> entry=getEntry(key);
if(entry==null) return null; moveToFrist(entry); return entry.value; } private
void moveToFrist(Entry entry) { if(entry==frist) return; if(entry.pre!=null)
entry.pre.next=entry.next; if(entry.next!=null) entry.next.pre=entry.pre;
if(last==entry) last=last.pre; if(frist==null||last==null){ frist=last=entry;
return; } entry.next=frist; frist.pre=entry; frist=entry; frist.pre=null; }
private void removeLast() { if(last!=null){ last=last.pre; if(last==null)
frist=null; else last.next=null; } } public Entry getEntry(K key){ return
hashMap.get(key); } public void print(HashMap<K,Entry<K,V>> map){
Collection<Entry<K,V>> entry=map.values(); Iterator it=entry.iterator();
while(it.hasNext()){ Entry<K,V> e=(LRUCache2<K, V>.Entry<K, V>) it.next();
System.out.println(e.key+" : "+e.value); } } class Entry<K,V>{ Entry pre; Entry
next; K key; V value; } public static void main(String[] args) {
LRUCache2<String, String> cache=new LRUCache2<>(3); cache.put("one", "1");
cache.put("tow", "2"); cache.put("three", "3"); System.out.println("first
entry: "+cache.frist.key); cache.print(cache.hashMap); cache.put("four", "4");
System.out.println("============================"); System.out.println("first
entry: "+cache.frist.key); cache.print(cache.hashMap); cache.put("five", "5");
System.out.println("============================"); System.out.println("first
entry: "+cache.frist.key); cache.print(cache.hashMap); } }
Technology