介绍
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 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 { private static final float hashLoadFactory = 0.75f; private LinkedHashMap map; private int cacheSize; public LRU(int cacheSize) { this.cacheSize = cacheSize; int capacity = (int)Math.ceil(cacheSize / hashLoadFactory) + 1; map = new LinkedHashMap(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 entry : map.entrySet()) { System.out.print(entry.getValue() + “–“); } System.out.println(); }}
