介紹

LRU是Least Recently Used的縮寫，即最近最少使用，是一種常用的頁面置換算法，選擇最近最久未使用的頁面予以淘汰。

編碼實(shí)現(xiàn)（高手繞行）

了解LRU的應(yīng)該都其低層實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)主要是是Map和鏈表，如下：

package com.zte.sdn.oscp.xls.read;import lombok.Data;import java.util.Map;import java.util.concurrent.ConcurrentHashMap;public class LRU {/**LRU存在數(shù)據(jù)容量**/ private int capacity = 5; /**主要用以快速判斷是否存在數(shù)據(jù)**/ 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; //刷新位置（移動(dòng)到頭） 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); //刷新位置（移動(dòng)到頭） 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實(shí)現(xiàn)

JDK中提供了LinkedHashMap數(shù)據(jù)結(jié)構(gòu)，LinkedHashMap底層就是用的HashMap加雙向鏈表實(shí)現(xiàn)的，而且本身已經(jīng)實(shí)現(xiàn)了按照訪問順序的存儲(chǔ)。此外，LinkedHashMap中本身就實(shí)現(xiàn)了一個(gè)方法removeEldestEntry用于判斷是否需要移除最不常讀取的數(shù)，方法默認(rèn)是直接返回false，不會(huì)移除元素，所以需要重寫該方法。即當(dāng)緩存滿后就移除最不常用的數(shù)

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(); }}