感兴趣的朋友可以直接从:
下载代码本地运行。
代码看着比较多，其实实现的思路还是比较简单：
- 采用了与 HashMap 一样的保存数据方式，只是自己手动实现了一个简易版。
- 内部采用了一个队列来保存每次写入的数据。
- 写入的时候判断缓存是否大于了阈值 N，如果满足则根据队列的 FIFO 特性将队列头的数据删除。因为队列头的数据肯定是最先放进去的。
- 再开启了一个守护线程用于判断最先放进去的数据是否超期（因为就算超期也是最先放进去的数据最有可能满足超期条件。）
- 设置为守护线程可以更好的表明其目的（最坏的情况下，如果是一个用户线程最终有可能导致程序不能正常退出，因为该线程一直在运行，守护线程则不会有这个情况。）
以上代码大体功能满足了，但是有一个致命问题。
就是最近最少使用没有满足，删除的数据都是最先放入的数据。
不过其中的
put get流程算是一个简易的 HashMap 实现，可以对 HashMap 加深一些理解。
实现二
因此如何来实现一个完整的 LRU 缓存呢，这次不考虑过期时间的问题。
其实从上一个实现也能想到一些思路：
- 要记录最近最少使用，那至少需要一个有序的集合来保证写入的顺序。
- 在使用了数据之后能够更新它的顺序。
基于以上两点很容易想到一个常用的数据结构：链表。
- 每次写入数据时将数据放入链表头结点。
- 使用数据时候将数据移动到头结点。
- 缓存数量超过阈值时移除链表尾部数据。
因此有了以下实现：
public class LRUMap<K, V> { private final Map<K, V> cacheMap = new HashMap<>(); /** * 最大缓存大小 */ private int cacheSize; /** * 节点大小 */ private int nodeCount; /** * 头结点 */ private Node<K, V> header; /** * 尾结点 */ private Node<K, V> tailer; public LRUMap(int cacheSize) { this.cacheSize = cacheSize; //头结点的下一个结点为空 header = new Node<>(); header.next = null; //尾结点的上一个结点为空 tailer = new Node<>(); tailer.tail = null; //双向链表 头结点的上结点指向尾结点 header.tail = tailer; //尾结点的下结点指向头结点 tailer.next = header; } public void put(K key, V value) { cacheMap.put(key, value); //双向链表中添加结点 addNode(key, value); } public V get(K key){ Node<K, V> node = getNode(key); //移动到头结点 moveToHead(node) ; return cacheMap.get(key); } private void moveToHead(Node<K,V> node){ //如果是最后的一个节点 if (node.tail == null){ node.next.tail = null ; tailer = node.next ; nodeCount -- ; } //如果是本来就是头节点 不作处理 if (node.next == null){ return ; } //如果处于中间节点 if (node.tail != null && node.next != null){ //它的上一节点指向它的下一节点 也就删除当前节点 node.tail.next = node.next ; nodeCount -- ; } //最后在头部增加当前节点 //注意这里需要重新 new 一个对象，不然原本的node 还有着下面的引用，会造成内存溢出。 node = new Node<>(node.getKey(),node.getValue()) ; addHead(node) ; } /** * 链表查询 效率较低 * @param key * @return */ private Node<K,V> getNode(K key){ Node<K,V> node = tailer ; while (node != null){ if (node.getKey().equals(key)){ return node ; } node = node.next ; } return null ; } /** * 写入头结点 * @param key * @param value */ private void addNode(K key, V value) { Node<K, V> node = new Node<>(key, value); //容量满了删除最后一个 if (cacheSize == nodeCount) { //删除尾结点 delTail(); } //写入头结点 addHead(node); } /** * 添加头结点 * * @param node */ private void addHead(Node<K, V> node) { //写入头结点 header.next = node; node.tail = header; header = node; nodeCount++; //如果写入的数据大于2个 就将初始化的头尾结点删除 if (nodeCount == 2) { tailer.next.next.tail = null; tailer = tailer.next.next; } } private void delTail() { //把尾结点从缓存中删除 cacheMap.remove(tailer.getKey()); //删除尾结点 tailer.next.tail = null; tailer = tailer.next; nodeCount--; } private class Node<K, V> { private K key; private V value; Node<K, V> tail; Node<K, V> next; public Node(K key, V value) { this.key = key; this.value = value; } public Node() { } public K getKey() { return key; } public void setKey(K key) { this.key = key; } public V getValue() { return value; } public void setValue(V value) { this.value = value; } } @Override public String toString() { StringBuilder sb = new StringBuilder() ; Node<K,V> node = tailer ; while (node != null){ sb.append(node.getKey()).append(":") .append(node.getValue()) .append("-->") ; node = node.next ; } return sb.toString(); } }
实际效果，写入时：
@Test public void put() throws Exception { LRUMap<String,Integer> lruMap = new LRUMap(3) ; lruMap.put("1",1) ; lruMap.put("2",2) ; lruMap.put("3",3) ; System.out.println(lruMap.toString()); lruMap.put("4",4) ; System.out.println(lruMap.toString()); lruMap.put("5",5) ; System.out.println(lruMap.toString()); } //输出： 1:1-->2:2-->3:3--> 2:2-->3:3-->4:4--> 3:3-->4:4-->5:5-->
使用时：
@Test public void get() throws Exception { LRUMap<String,Integer> lruMap = new LRUMap(3) ; lruMap.put("1",1) ; lruMap.put("2",2) ; lruMap.put("3",3) ; System.out.println(lruMap.toString()); System.out.println("=============="); Integer integer = lruMap.get("1"); System.out.println(integer); System.out.println("=============="); System.out.println(lruMap.toString()); } //输出 1:1-->2:2-->3:3--> ============== 1 ============== 2:2-->3:3-->1:1-->
