©2020-2024 ioDraw All rights reserved,
Privacy Policy
LRU算法，也叫最近最少使用算法，我们可以使用该算法来实现cache机制，简单地说就是缓存一定量的数据，当超过设定阀值的时候就把一些过期的数据删除掉，本篇文章我们来看看如何实现LRU
Cache，下面我们使用两种方式来实现。
<>基于LinkedHashMap
在java的集合类中有LinkedHashMap类，当参数accessOrder为true的时候，就会按照访问顺序排序，最后访问的放在最前面，最早访问的放在后面，这样我们就可以实现LRU算法了。这种方式比较简单，代码如下：
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); } }
<>链表+HashMap
第二种方式是使用链表+HashMap的方式来实现，需要我们自己实现一系列方法，代码如下：
import java.util.Collection; import java.util.HashMap; import
java.util.Iterator; /** * LRUCache链表+hashmap的实现方式 * @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); } }