内容简介:原文链接:前面,我们学习了
原文链接: https://wangwei.one/posts/jav...
前面,我们学习了 链表 的实现,今天我们来学习链表的一个经典的应用场景——LRU淘汰算法。
缓存是一种提高数据读取性能的技术,在硬件设计、软件开发中都有着非常广泛的应用,比如常见的 CPU 缓存、数据库缓存、浏览器缓存等等。
缓存的大小有限,当缓存被用满时,哪些数据应该被清理出去,哪些数据应该被保留?这就需要缓存淘汰策略来决定。常见的策略有三种:先进先出策略 FIFO(First In,First Out)
、最少使用策略 LFU(Least Frequently Used)
、最近最少使用策略 LRU(Least Recently Used)
,本篇将介绍LRU策略算法。
LRU Cache
这一算法的核心思想是,当缓存数据达到预设的上限后,会优先淘汰掉近期最少使用的缓存对象。
思路
LRU淘汰算法涉及数据的添加与删除,出于性能考虑,采用链表来进行实现,思路如下:
- 维护一个双向链表用于存放缓存数据,越接近链表尾部的数据表示越少被使用到。
-
放入一个数据时,如果数据已存在则将其移动到链表头部,并更新Key所对应的Value值,如果不存在,则:
- 如果缓存容量已达到最大值,则将链表尾部节点删除掉,将新的数据放入链表头部;
- 如果缓存容量未达到最大值,则直接将新的数据放入链表头部;
-
查询一个数据时,遍历整个链表,如果能查询到对应的数据,则将其移动到链表头部;如果查询不到则返回
null
;- 由于遍历链表的时间复杂度为
O(n)
,我们可以使用散列表HashMap
来记录每个Key所对应的Node节点,将时间复杂度降为O(1)。
- 由于遍历链表的时间复杂度为
代码
package one.wangwei.algorithms.utils; import java.util.HashMap; import java.util.Map; /** * LRU Cache * * @author https://wangwei.one * @date 2019/01/29 */ public class LRUCache<K, V> { private int capacity; private Node head; private Node tail; private Map<K, Node> nodeMap; public LRUCache(int capacity) { this.capacity = capacity; this.nodeMap = new HashMap<>(capacity); } /** * Get Key * * @param key * @return */ public V get(K key) { Node existNode = nodeMap.get(key); if (existNode == null) { return null; } remove(existNode); addFirst(existNode); return existNode.value; } /** * Add Key-Value * * @param key * @param value */ public void put(K key, V value) { Node existNode = nodeMap.get(key); if (existNode == null) { Node newNode = new Node(key, value); if (nodeMap.size() >= capacity) { removeLast(); } addFirst(newNode); } else { // update the value existNode.value = value; remove(existNode); addFirst(existNode); } } /** * remove node * * @param node */ private void remove(Node node) { Node prev = node.prev; Node next = node.next; if (prev == null) { head = next; } else { prev.next = next; } if (next == null) { tail = prev; } else { next.prev = prev; } nodeMap.remove(node.key); } /** * add first node * * @param node */ private void addFirst(Node node) { node.prev = null; if (head == null) { head = tail = node; } else { node.next = head; head.prev = node; head = node; } nodeMap.put(node.key, node); } /** * remove last */ private void removeLast() { if (tail == null) { return; } // remove key from map nodeMap.remove(tail.key); // remove node from linked list Node prev = tail.prev; if (prev != null) { prev.next = null; tail = prev; } else { head = tail = null; } } private class Node { private K key; private V value; private Node prev; private Node next; private Node(K key, V value) { this.key = key; this.value = value; } } }
LeetCode上相关的练习题: Leetcode 146. LRU Cache
性能测试:LeetCode上运行时间为 88ms
,超过了 43.42%
的 Java 代码。
以上所述就是小编给大家介绍的《数据结构与算法 | 如何实现LRU缓存淘汰算法》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:- 算法与数据结构之递归算法
- Python 数据结构与算法 —— 初识算法
- js实现数据结构及算法之排序算法
- 数据结构和算法面试题系列—递归算法总结
- 数据结构和算法面试题系列—随机算法总结
- 数据结构与算法——常用排序算法及其Java实现
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。