龙空技术网

从原理到实现,三分钟轻松掌握LRU算法

Java编程世界 238

前言:

当前看官们对“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链表算法