LRU 算法实现
什么是 LRU 算法
LRU是什么？按照英文的直接原义就是Least Recently Used,最近最久未使用法，它是按照一个非常著名的计算机操作系统基础理论得来的：最近使用的页面数据会在未来一段时期内仍然被使用,已经很久没有使用的页面很有可能在未来较长的一段时间内仍然不会被使用。基于这个思想,会存在一种缓存淘汰机制，每次从内存中找到最久未使用的数据然后置换出来，从而存入新的数据！它的主要衡量指标是使用的时间，附加指标是使用的次数。在计算机中大量使用了这个机制，它的合理性在于优先筛选热点数据，所谓热点数据，就是最近最多使用的数据！因为，利用LRU我们可以解决很多实际开发中的问题，并且很符合业务场景。
LRU 算法的核心思想：在 put 和 get 时，需要将该节点移动到首位置。当超出容量时，需要删除尾节点。
基于双链表法的 LRU 实现：
import java.util.HashMap; import java.util.Map.Entry; import java.util.Set; public class LRUCache<K, V> { private int currentCacheSize; private int CacheCapcity; private HashMap<K,CacheNode> caches; private CacheNode first; private CacheNode last; public LRUCache(int size){ currentCacheSize = 0; this.CacheCapcity = size; caches = new HashMap<K,CacheNode>(size); } public void put(K k,V v){ CacheNode node = caches.get(k); if(node == null){ if(caches.size() >= CacheCapcity){ caches.remove(last.key); removeLast(); } node = new CacheNode(); node.key = k; } node.value = v; moveToFirst(node); caches.put(k, node); } public Object get(K k){ CacheNode node = caches.get(k); if(node == null){ return null; } moveToFirst(node); return node.value; } public Object remove(K k){ CacheNode node = caches.get(k); if(node != null){ // 先断开前面节点的连接,把前一个节点指向当前节点的后一个节点 if(node.pre != null){ node.pre.next=node.next; } // 再断开后面节点的连接，把当前节点的下一个节点指向当前节点的前一个节点 if(node.next != null){ node.next.pre=node.pre; } if(node == first){ first = node.next; } if(node == last){ last = node.pre; } } return caches.remove(k); } public void clear(){ first = null; last = null; caches.clear(); } private void moveToFirst(CacheNode node){ if(first == node){ return; } // 先断开后一个连接，将当前节点的后一个连接指向当前节点的前一个连接 if(node.next != null){ node.next.pre = node.pre; } // 再断开前一个连接，当前节点的前一个节点指向当前节点下一个节点 if(node.pre != null){ node.pre.next = node.next; } if(node == last){ last= last.pre; } if(first == null || last == null){ first = last = node; return; } node.next=first; first.pre = node; first = node; first.pre=null; } private void removeLast(){ if(last != null){ last = last.pre; if(last == null){ first = null; }else{ last.next = null; } } } @Override public String toString(){ StringBuilder sb = new StringBuilder(); CacheNode node = first; while(node != null){ sb.append(String.format("%s:%s ", node.key,node.value)); node = node.next; } return sb.toString(); } class CacheNode{ CacheNode pre; CacheNode next; Object key; Object value; public CacheNode(){ } } public static void main(String[] args) { LRUCache<Integer,String> lru = new LRUCache<Integer,String>(3); lru.put(1, "a"); // 1:a System.out.println(lru.toString()); lru.put(2, "b"); // 2:b 1:a System.out.println(lru.toString()); lru.put(3, "c"); // 3:c 2:b 1:a System.out.println(lru.toString()); lru.put(4, "d"); // 4:d 3:c 2:b System.out.println(lru.toString()); lru.put(1, "aa"); // 1:aa 4:d 3:c System.out.println(lru.toString()); lru.put(2, "bb"); // 2:bb 1:aa 4:d System.out.println(lru.toString()); lru.put(5, "e"); // 5:e 2:bb 1:aa System.out.println(lru.toString()); lru.get(1); // 1:aa 5:e 2:bb System.out.println(lru.toString()); lru.remove(11); // 1:aa 5:e 2:bb System.out.println(lru.toString()); lru.remove(1); //5:e 2:bb System.out.println(lru.toString()); lru.put(1, "aaa"); //1:aaa 5:e 2:bb System.out.println(lru.toString()); } }
JDK 中 LinkedHashMap 就和 LRUCache 类似， LinkedHashMap 维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序，该迭代顺序可以是插入顺序或者是访问顺序。按插入顺序的链表，和按访问顺序(调用get方法)的链表，会调整节点的顺序。主要是因为 LinkedHashMap 实现了 afterNodeInsertion 和 afterNodeAccess ,afterNodeRemoval 方法.
void afterNodeAccess(Node<K,V> e) { // move node to last LinkedHashMap.Entry<K,V> last; if (accessOrder && (last = tail) != e) { LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after; p.after = null; if (b == null) head = a; else b.after = a; if (a != null) a.before = b; else last = b; if (last == null) head = p; else { p.before = last; last.after = p; } tail = p; ++modCount; } }
afterNodeInsertion 插入有可能要删除最老的节点
void afterNodeInsertion(boolean evict) { // possibly remove eldest LinkedHashMap.Entry<K,V> first; if (evict && (first = head) != null && removeEldestEntry(first)) { K key = first.key; removeNode(hash(key), key, null, false, true); } }
