数据结构与算法 | 如何实现LRU缓存淘汰算法

栏目: 编程工具 · 发布时间: 5年前

内容简介:原文链接:前面,我们学习了

数据结构与算法 | 如何实现LRU缓存淘汰算法

原文链接: 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)。

数据结构与算法 | 如何实现LRU缓存淘汰算法

代码

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缓存淘汰算法》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

数据化运营速成手册

数据化运营速成手册

胡晨川 / 电子工业出版社 / 2017-4 / 55

《数据化运营速成手册》用于提升互联网公司员工的数据应用能力,即数据化运营能力。首先,从最常用的数据图表切入,帮助执行层正确地绘图,管理层正确地看图;接着,梳理运营中最基本的数据应用知识,涉及数据获取、数据清洗、数据认知、分析框架、指标体系、运营实验等内容。然后,介绍作者认为必要的统计学知识,包括假设检验、方差分析、回归分析和时间序列分解,并引入了管理科学中的规划求解方法。最后,介绍了数据分析工具的......一起来看看 《数据化运营速成手册》 这本书的介绍吧!

随机密码生成器
随机密码生成器

多种字符组合密码

RGB HSV 转换
RGB HSV 转换

RGB HSV 互转工具

RGB CMYK 转换工具
RGB CMYK 转换工具

RGB CMYK 互转工具