最近最少使用LRU（Least Recently Used）算法java实现一.使用LinkedHashMap算法实现二.手撸 LRU 算法实现（Hash表 + 双向链表）三.总结

最近最少使用LRU（Least Recently Used）算法java实现

LRU 是Least Recently Used的缩写，即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 t，当须淘汰一个页面时，选择现有页面中其 t 值最大的，即最近最少使用的页面予以淘汰。

以上是来自百度百科的介绍，通俗来说，LRU就是一个淘汰算法，例如内存相较于硬盘可以快速的读写，但是内存的空间是有限的，为了有效的利用内存空间，就需要将一些非热点数据给淘汰掉，这里就用到 LRU 算法，它会将内存中最近一段时间没有使用的数据给淘汰掉。

另外 LRU 算法在找工作面试中，经常会被问到，需要能够在短时间内写出来，大家平时还是要勤加练习，下面给出两种算法实现。

动动发财小手，关注 + 点赞 + 收藏不迷路。

一.使用LinkedHashMap算法实现

LinkedHashMap 底层采用 HashMap + 双向链表，已经实现了 LRU 算法，我们可以直接来使用 LinkedHashMap 来实现LRU算法。

以下是 LinkedHashMap 构造函数的代码

/*** Constructs an empty <tt>LinkedHashMap</tt> instance with the* specified initial capacity, load factor and ordering mode.** @param initialCapacity the initial capacity* @param loadFactorthe load factor* @param accessOrderthe ordering mode - <tt>true</tt> for* access-order, <tt>false</tt> for insertion-order* @throws IllegalArgumentException if the initial capacity is negative* or the load factor is nonpositive*/public LinkedHashMap(int initialCapacity,float loadFactor,boolean accessOrder) {super(initialCapacity, loadFactor);this.accessOrder = accessOrder;}

LinkedHashMap 构造函数前两个参数在这里就不介绍了，这儿简单介绍一下第三个参数：boolean accessOrder，true 代表按照存取顺序来排序， false 代表按照插入顺序来排序。

以下是使用 LinkedHashMap 来实现的 LRU 算法。

package algorithm.lru;import java.util.Iterator;import java.util.LinkedHashMap;import java.util.Map;/*** 使用LinkedHashMap 实现的LRU** @date: -12-12 21:55*/public class LRUCache<K, V> extends LinkedHashMap<K, V> {private int cacheSize;public LRUCache(int cacheSize) {super(cacheSize, 0.75f, true);this.cacheSize = cacheSize;}@Overrideprotected boolean removeEldestEntry(Map.Entry<K, V> eldest) {return size() > cacheSize;}public static void main(String[] args) {LRUCache lru = new LRUCache(3);lru.put("1", 1);lru.put("2", 2);lru.put("3", 3);lru.put("4", 4);lru.printLRU(lru);System.out.println();lru.get("3");lru.printLRU(lru);}public void printLRU(LRUCache lru) {Iterator<Map.Entry<String, Integer>> iterator = lru.entrySet().iterator();while (iterator.hasNext()) {Map.Entry<String, Integer> entry = iterator.next();System.out.println("key = " + entry.getKey() + ", value = " + entry.getValue());}}}

输出如下：

key = 2, value = 2key = 3, value = 3key = 4, value = 4key = 2, value = 2key = 4, value = 4key = 3, value = 3

可以看到，执行了 lru.put(“4”, 4) 之后，key = 1 就被remove了；当执行 lru.get(“3”) 之后，key = 3被挪到了双向链表的最前面。

二.手撸 LRU 算法实现（Hash表 + 双向链表）

上面的 LRU 算法实现，有点取巧，通常在面试的时候，面试官希望看到具体的算法实现逻辑，而不是使用 LinkedHashMap 已有的功能。当然了，在工作当中，还是不要自己来实现了。

package algorithm.lru;import java.util.concurrent.ConcurrentHashMap;/*** LRU (Least recently used) 最近最少使用** @date: /12/12 22:19*/public class LruCache {private static ConcurrentHashMap<String, Node> cacheMap;private static volatile int count;private static int capacity;private Node head = new Node();private Node tail = new Node();LruCache(int capacity) {this.count = 0;this.capacity = capacity;cacheMap = new ConcurrentHashMap<>();this.tail.pre = head;this.head.next = tail;}private static class Node {Node() {}Node(String key) {this.key = key;this.value = Integer.parseInt(key);}private String key;private int value;private Node pre;private Node next;public String getKey() {return this.key;}}public void put(Node node) {Node existNode = get(node);if (existNode != null) {// cacheMap中node存在,先remove节点,再把节点移到链表头部removeNode(existNode);// 在链表头部插入nodeheadAdd(existNode);} else {// cacheMap中node不存在,则插入nodeif (count == capacity) {// 缓存已满,在链表尾部removetailRemove();count--;}headAdd(node);count++;cacheMap.put(node.getKey(), node);}}public void headAdd(Node node) {node.next = head.next;head.next.pre = node;node.pre = head;head.next = node;}public void removeNode(Node node) {node.pre.next = node.next;node.next.pre = node.pre;}public void tailRemove() {tail.pre.pre.next = tail;tail.pre = tail.pre.pre;}public Node get(Node node) {return cacheMap.get(node.getKey());}public void print() {Node node = head;System.out.println("========================================");while (node.next != null && node.next != tail) {System.out.println(node.next.key + " count = " + count);node = node.next;}}public static void main(String[] args) {Node node1 = new Node("1");Node node2 = new Node("2");Node node3 = new Node("3");Node node4 = new Node("4");LruCache lruCache1 = new LruCache(3);lruCache1.put(node1);lruCache1.print();lruCache1.put(node2);lruCache1.print();lruCache1.put(node3);lruCache1.print();lruCache1.put(node4);lruCache1.print();System.out.println("");System.out.println("###################################################");System.out.println("");Node node5 = new Node("5");Node node6 = new Node("6");Node node7 = new Node("7");LruCache lruCache3 = new LruCache(3);lruCache3.put(node5);lruCache3.print();lruCache3.put(node6);lruCache3.print();lruCache3.put(node7);lruCache3.print();lruCache3.put(node5);lruCache3.print();System.out.println("");System.out.println("###################################################");System.out.println("");Node node8 = new Node("8");LruCache lruCache2 = new LruCache(3);lruCache2.put(node8);lruCache2.print();lruCache2.put(node8);lruCache2.print();}}

输出如下：

========================================1 count = 1========================================2 count = 21 count = 2========================================3 count = 32 count = 31 count = 3========================================4 count = 33 count = 32 count = 3###################################################========================================5 count = 1========================================6 count = 25 count = 2========================================7 count = 36 count = 35 count = 3========================================5 count = 37 count = 36 count = 3###################################################========================================8 count = 1========================================8 count = 1

三.总结

最好还是能够手写第二种 LRU 的算法实现，就算不能全写出来，也可以写一个大概的思路，面试官主要考察的也就是这个，毕竟在短短的10几分钟内，手撸一个 LRU 还是有点难度的，难免会有一些小bug。

引用:

1./item/LRU/1269842?fr=aladdin

如果觉得《最近最少使用LRU（Least Recently Used）算法java实现》对你有帮助，请点赞、收藏，并留下你的观点哦！