介绍
LRU是Least Recently Used的缩写，即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。
编码实现（高手绕行）
了解LRU的应该都其低层实现的数据结构主要是是Map和链表，如下：
package com.zte.sdn.oscp.xls.read; import lombok.Data; import java.util.Map; import java.util.concurrent.ConcurrentHashMap; public class LRU { /**LRU存在数据容量**/ private int capacity = 5; /**主要用以快速判断是否存在数据**/ private Map<String, Node> nodeMap = new ConcurrentHashMap<>(); private Node tail; private Node head; public LRU() { tail = new Node(); head = new Node(); tail.pre = head; head.nex = tail; tail.nex = null; head.pre = null; } public String getValue(String key) { String result = null; if (nodeMap.containsKey(key)) { Node node = nodeMap.get(key); result = node.value; //刷新位置（移动到头） removeNode(node); addHead(node); } return result; } public void putValue(String key, String value) { if (nodeMap.containsKey(key)) { Node node = nodeMap.get(key); node.setValue(value); //刷新位置（移动到头） removeNode(node); addHead(node); } else { Node node = new Node(); node.setValue(value); if (nodeMap.size() < capacity) { addHead(node); } else { removeNode(tail.pre); addHead(node); } nodeMap.put(key,node); } } private void addHead(Node node) { node.nex = head.nex; node.nex.pre = node; head.nex = node; node.pre = head; } private void removeNode(Node node) { node.pre.nex = node.nex; node.nex.pre = node.pre; } @Override public String toString() { StringBuffer output = new StringBuffer(); Node node = head.nex; while (node != null && node.nex != null) { output.append(node.value).append(","); node = node.nex; } return output.toString(); } @Data class Node { private String value; private Node pre; private Node nex; } public static void main(String[] args) { LRU lru = new LRU(); lru.putValue("1", "1"); lru.putValue("2", "2"); lru.putValue("3", "3"); lru.putValue("4", "4"); System.out.println("4:" + lru); lru.putValue("5", "5"); System.out.println("5:" + lru); lru.putValue("6", "6"); System.out.println("6:" + lru); lru.putValue("4", "44"); System.out.println("7:" + lru); String value = lru.getValue("2"); System.out.println("8:" + lru); } }
LinkedHashMap实现
JDK中提供了LinkedHashMap数据结构，LinkedHashMap底层就是用的HashMap加双向链表实现的，而且本身已经实现了按照访问顺序的存储。此外，LinkedHashMap中本身就实现了一个 removeEldestEntry用于判断是否需要移除最不常读取的数， 默认是直接返回false，不会移除元素，所以需要重写该 。即当缓存满后就移除最不常用的数
public class LRU<K,V> { private static final float hashLoadFactory = 0.75f; private LinkedHashMap<K,V> map; private int cacheSize; public LRU(int cacheSize) { this.cacheSize = cacheSize; int capacity = (int)Math.ceil(cacheSize / hashLoadFactory) + 1; map = new LinkedHashMap<K,V>(capacity, hashLoadFactory, true){ private static final long serialVersionUID = 1; @Override protected boolean removeEldestEntry(Map.Entry eldest) { return size() > LRU.this.cacheSize; } }; } public synchronized V get(K key) { return map.get(key); } public synchronized void put(K key, V value) { map.put(key, value); } public synchronized void clear() { map.clear(); } public synchronized int usedSize() { return map.size(); } public void print() { for (Map.Entry<K, V> entry : map.entrySet()) { System.out.print(entry.getValue() + "--"); } System.out.println(); } }
