前言:
当前看官们对“lru链表算法”都比较关切,你们都想要学习一些“lru链表算法”的相关知识。那么小编在网络上网罗了一些有关“lru链表算法””的相关知识,希望姐妹们能喜欢,大家快快来了解一下吧!一、什么是LRU算法
LRU算法的全称是“Least Recently Used”,即“最近最少使用”算法。LRU算法的基本思想是,当缓存空间已满时,优先淘汰最近最少使用的缓存数据,以腾出更多的缓存空间。因此,LRU算法需要维护一个缓存访问历史记录,以便确定哪些缓存数据是最近最少使用的。
LRU算法的实现可以采用多种数据结构,其中最常见的是使用一个双向链表和一个哈希表。双向链表用于维护缓存数据的访问顺序,哈希表用于快速查找缓存数据。具体来说,当新的数据被访问时,先在哈希表中查找该数据是否已经存在于缓存中,如果存在,则将该数据移动到双向链表的头部,表示该数据是最近访问的数据;如果不存在,则需要将该数据添加到缓存中,并将其添加到双向链表的头部。当缓存空间已满时,需要淘汰双向链表中最后一个节点,同时在哈希表中删除对应的缓存数据。
二、使用Java实现LRU算法
下面我们将使用Java语言实现一个LRU算法,并将其封装为一个LRU缓存类,该类提供了如下功能:
添加数据到缓存中;从缓存中获取数据;获取当前缓存的大小;清空缓存。
首先,我们需要定义一个双向链表节点类,用于保存缓存数据和维护节点的访问顺序:
class Node<K, V> { K key; V value; Node<K, V> prev; Node<K, V> next; public Node(K key, V value) { this.key = key; this.value = value; }}
接下来,我们定义一个LRU缓存类,该类维护了一个哈希表和一个双向链表,用于实现LRU算法:
public class LRUCache<K, V> { private int capacity; // 缓存容量 private Map<K, Node<K, V>> map; // 哈希表 private Node<K, V> head; // 双向链表头节点 private Node<K, V> tail; // 双向链表尾节点 public LRUCache(int capacity) { this.capacity = capacity; this.map = new HashMap<>(); // 初始化双向链表 this.head = new Node<>(null, null); this.tail = new Node<>(null, null); this.head.next = this.tail; this.tail.prev = this.head;}/** * 添加数据到缓存中 */public void put(K key, V value) { Node<K, V> node = map.get(key); if (node != null) { // 如果已经存在该节点,则将其移动到链表头部 removeNode(node); } else { // 如果不存在该节点,则需要添加新节点 node = new Node<>(key, value); map.put(key, node); if (map.size() > capacity) { // 如果缓存已满,则需要淘汰最近最少使用的节点 Node<K, V> removedNode = removeLast(); map.remove(removedNode.key); } } // 将新节点添加到链表头部 addFirst(node);}/** * 从缓存中获取数据 */public V get(K key) { Node<K, V> node = map.get(key); if (node != null) { // 如果存在该节点,则将其移动到链表头部,并返回其值 removeNode(node); addFirst(node); return node.value; } return null;}/** * 获取当前缓存的大小 */public int size() { return map.size();}/** * 清空缓存 */public void clear() { map.clear(); head.next = tail; tail.prev = head;}/** * 从双向链表中移除指定节点 */private void removeNode(Node<K, V> node) { node.prev.next = node.next; node.next.prev = node.prev;}/** * 将节点添加到双向链表头部 */private void addFirst(Node<K, V> node) { node.prev = head; node.next = head.next; head.next.prev = node; head.next = node;}/** * 从双向链表尾部移除节点,并返回该节点 */private Node<K, V> removeLast() { Node<K, V> node = tail.prev; if (node == head) { return null; } removeNode(node); return node;}}
在LRUCache类中,我们定义了一个哈希表map,用于快速查找缓存数据,同时定义了一个双向链表,用于维护缓存数据的访问顺序。具体实现时,我们在put方法中先查找缓存中是否已经存在该节点,如果存在则将其移动到链表头部,表示该节点是最近访问的节点;如果不存在则需要添加新节点,如果缓存已满,则需要淘汰最近最少使用的节点。在get方法中,我们根据给定的key查找缓存数据,如果存在该节点则将其移动到链表头部,表示该节点是最近访问的节点,并返回其值。在LRUCache类中还定义了一些辅助方法,如size方法用于获取当前缓存的大小,clear方法用于清空缓存,以及三个私有方法removeNode、addFirst和removeLast,分别用于从双向链表中移除指定节点、将节点添加到双向链表头部以及从双向链表尾部移除节点。
值得一提的是,在put方法中,如果缓存已满,则需要淘汰最近最少使用的节点。这里我们采用的是淘汰最近最少使用的节点,也就是在访问缓存时最久没被访问过的节点。具体实现是在双向链表的尾部维护了这些最近最少使用的节点,当缓存已满时,淘汰双向链表尾部的节点,即最久没被访问的节点。这里之所以采用双向链表,是因为双向链表可以方便地在节点之间移动,并且可以快速删除节点。
下面我们来测试一下我们实现的LRU算法,具体代码如下:
public class LRUTest { public static void main(String[] args) { LRUCache<Integer, String> cache = new LRUCache<>(3); cache.put(1, "a"); cache.put(2, "b"); cache.put(3, "c"); System.out.println(cache.get(1)); // 输出a cache.put(4, "d"); System.out.println(cache.get(2)); // 输出null System.out.println(cache.get(1)); // 输出a cache.put(5, "e"); cache.clear(); System.out.println(cache.size()); // 输出0 }}
在测试代码中,我们先创建一个容量为3的LRUCache对象,然后依次往其中添加4个节点。在第4次添加时,由于缓存已满,会淘汰最近最少使用的节点,即节点3。接着我们分别测试节点2和节点1是否能够被正确获取到,并添加一个新节点5,最后清空缓存并测试缓存大小是否为0。运行测试代码后,可以得到如下输出:
三、结语
可以看到,LRU算法的实现非常简单,而且具有较好的效率和性能。它可以被广泛应用于各种场景,如数据库缓存、页面缓存、图片缓存等。在实际开发中,如果我们需要使用缓存来优化程序性能,那么LRU算法无疑是一个不错的选择。
标签: #lru链表算法