为什么要用LRU算法？Java怎么实现？

为什么要用LRU算法？Java怎么实现？

一、LRU算法介绍

LRU算法全称Least Recently Used，即检查出最近最少使用的数据。其通常应用在内存淘汰策略中，将不常用的数据移出内存，为"热点数据" 或 新数据 腾出空间。

本质上算法很简单，只需要将所有数据按使用时间排序，在需要进行数据淘汰的时候把最老的数据淘汰掉。

二、LRU算法的应用

LRU算法的应用很多，我们这里分别从硬件和软件中抽取一个典型应用做介绍。

1、Linux内存分页

分页是为了解决内存不够用的问题，它把内存分成固定大小的页框（page frame 4K标准页），把硬盘上的程序分成4K大小的块装入页框，后续用到哪一块，就加载哪一块。

加载的过程中，如果内存已经满了，会把最不常用的一块放到swap分区，把最新的一块加载进来，这里便是LRU算法的应用。

2、Redis内存淘汰策略

当Redis的内存不足（超过maxmemory限定）以使用时，会使用选择的内存淘汰策略淘汰数据。

相关的LRU策略：

allkeys-lru：移除最近最少使用的key；volatile-lru：在设置了过期时间的键空间中，移除最近最少使用的key；

LRU底层实现：

Redis对象头中有一个24bit的lru字段，用来记录对象的热度。在LRU模式下，lru字段存储的是Redis时钟server.lruclock– 自增整数。当某个key被访问一次，它对象头中的lru字段就会被更新为server.lruclock。lruclock是支持原子操作的，因为可能会有多个线程要获取redis时钟。

三、LRU算法Java实现

1、实现思路

1）双向链表 --> 插入时间复杂度O(1)

我们可以使用双向链表来维持数据被访问的先后顺序，创建两个虚拟节点：头结点和尾结点。

靠近头部的数据是最近被使用的，而靠近尾部的数据是最久未被使用的。当我们进行put和get操作的时候将数据放到链表的最头部。当容量不足以容纳新增的数据时，先将链表尾部的数据移除，然后再新增。

将数据添加到链表头部流程如下：

将数据从链表中移除流程如下：

后续的实现基本都是基于这两种操作做一个结合使用。

但是只使用链表的话，数据查询的均摊时间复杂度为O(n/2)，如果我们做到数据查询的时间复杂度也是O(1)的话，就需要使用哈希表。

hash表即为普通的哈希映射（HashMap），将缓存数据的键key映射到双向链表中的位置。

这样可以使用我们整个LRU数据结构的put和get操作的时间复杂度都为O(1)。 下面我们来看一下这个思路的两种实现方式：一种是基于LinkedHashMap做一个重写，一种是我们就要HashMap做一个类LinkedHashMap的结构。

一般而言如果在面试中被要求手写LRU算法，不建议直接写一个类继承自LinkedHashMap做一个重写操作，面试官更希望通过你自己实现一个LRU数据结构来考察一下你的数据结构基础。

2、实现一（基于LinkedHashMap）

这种实现就很简单：

我们规定一个capacity，使用super关键字调用父类的构造函数，然后给capacity赋值。get、put操作也都是使用父类的方法。重写父类的模板方法–removeEldestEntry()，自定义自己的数据淘汰策略。

class LRUCache2 extends LinkedHashMap { private int capacity; public LRUCache2(int capacity) { super(capacity, 0.75F, true); this.capacity = capacity; } public int get(int key) { return super.getOrDefault(key, -1); } public void put(int key, int value) { super.put(key, value); } @Override protected boolean removeEldestEntry(Map.Entry eldest) { return size() > capacity; }}

3、实现二（自定义双向链表）

1）数据结构说明

Map中的key与Node中的LRUNode一一对应，因为Java是参数是按值传递，而这个值是引用对象的内存地址。所以Map中的value：LRUNode保存的是LRUNode的内存地址，所以可以通过Map的key直接定位到LRUNode在链表中的位置。因为我们需要以O(1)时间复杂度 改变链表中数据的位置，所以我们需要使用双向链表，即在LRUNode中定义prev和next节点。

2）get流程

首先判断key是否在HashMap中存在。如果不存在，返回-1。如果存在，则说明key对应的node节点是最近被使用的节点，通过表定位到该节点在链表中的位置，然后将其移动到双向链表的头部，最后返回该节点的value值。

3）put流程

首先判断key是否存在如果不存在，首先创建一个新的Node节点，然后将节点插入到链表的头部，并将key和该节点的键值对添加到hash表中。最后判断当前size是否超过capacity。

如果超过则将链表尾部的节点移除，并删除其在hash表中对应的key-calue键值对。

如果存在，则操作与get流程类似，首先通过hash表定位到该节点在链表中的位置，再将该节点的value值更新为newValue，最后将其移动到双向链表的头部。

​​注意：在双向链表的实现中，使用伪头部和伪尾部标记界限，这样删除节点的时候就不需要检查其相邻的节点是否存在。​​

代码实现

/** * LRU * @author Saint */public class LRUCache { private Map map; private int size; private int capacity; /** * 链表头节点、尾节点 */ private LRUNode head, tail; /** * 双向链表节点 */ class LRUNode { private LRUNode prev; private LRUNode next; private int key; private int value; public LRUNode() { } public LRUNode(int key, int value) { this.key = key; this.value = value; } } public LRUCache(int capacity) { map = new HashMap<>(capacity); // 虚拟头结点和尾结点 head = new LRUNode(-1, -1); tail = new LRUNode(-1, -1); head.next = tail; tail.prev = head; this.capacity = capacity; this.size = 0; } public int get(int key) { LRUNode node = map.get(key); if (null == node) { return -1; } // 如果key存在，通过hash表定位，然后将其移动到链表头部 moveNodeToHead(node); return node.value; } public void put(int key, int value) { LRUNode node = map.get(key); // 如果key不存在 if (null == node) { // 创建一个链表节点 LRUNode lruNode = new LRUNode(key, value); // 将节点添加到链表头部 addNodeToHead(lruNode); // 将节点插入到hash表 map.put(key, lruNode); ++size; if (size > capacity) { LRUNode removeTail = removeTail(); map.remove(removeTail.key); --size; } } else { // key已经存在 node.value = value; moveNodeToHead(node); } } /** * 从链表中移除Node节点 */ public void removeNode(LRUNode node) { node.prev.next = node.next; // node节点的next节点的prev指针 指向 Node节点的prev节点的next node.next.prev = node.prev; // 帮助GC node.next = null; node.prev = null; } /** * 将元素移到链表头部 */ public void addNodeToHead(LRUNode node) { node.prev = head; node.next = head.next; head.next.prev = node; head.next = node; } /** * 将Node节点移动到链表头部 */ public void moveNodeToHead(LRUNode node) { removeNode(node); addNodeToHead(node); } /** * 移除最久没被访问的元素 */ public LRUNode removeTail() { LRUNode tailNode = tail.prev; removeNode(tailNode); return tailNode; }}

PS：该算法可以在Leetcode146题中体现：​​https://leetcode-cn.com/problems/lru-cache/​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。