Java教程

实现LRU缓存淘汰算法

本文主要是介绍实现LRU缓存淘汰算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

缓存是一种提高数据读取性能的技术,在硬件设计、软件开发中都有着非常广泛的应用,比如常见的 CPU 缓存、数据库缓存、浏览器缓存等等。

缓存的大小有限,当缓存被用满时,哪些数据应该被清理出去,哪些数据应该被保留?这就需要缓存淘汰策略来决定。常见的策略有三种:先进先出策略 FIFO(First In,First Out)、最少使用策略 LFU(Least Frequently Used)、最近最少使用策略 LRU(Least Recently Used)。

leetcode-266
思路是这样的:我们维护一个有序单链表,越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时,我们从链表头开始顺序遍历链表。

  1. 如果此数据之前已经被缓存在链表中了,我们遍历得到这个数据对应的结点,并将其从原来的位置删除,然后再插入到链表的尾部。
  2. 如果此数据没有在缓存链表中,又可以分为两种情况:如果此时缓存未满,则将此结点直接插入到链表的尾部;如果此时缓存已满,则链表头结点删除,将新的数据结点插入链表的头部。

代码如下:

public class LRUCache{
    int capacity;
    Map<Integer, Integer> map;


    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new LinkedHashMap<>();
    }
    /**
     * @Title: get
     * @Description: 往缓存获取元素
     * @param key:
     * @return int
     * @Author: Ansen
     */
    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        // 先删除旧的位置,再放入新位置
        Integer value = map.remove(key);
        map.put(key, value);
        return value;
    }

    /**
     * @Title: put
     * @Description: 往缓存添加元素
     * @param key:
     * @param value:
     * @return void
     * @Author: Ansen
     */
    public void put(int key, int value) {
        if (map.containsKey(key)) {
            map.remove(key);
            map.put(key, value);
            return;
        }
        map.put(key, value);
        // 超出capacity,删除最久没用的,利用迭代器删除第一个
        if (map.size() > capacity) {
            map.remove(map.entrySet().iterator().next().getKey());
        }
    }
    /**
     * @Description: 测试
     * @param args:
     * @return void
     * @Author: Ansen
     */
    public static void main(String[] args) {
        LRUCache lruCache = new LRUCache(4);
        lruCache.put(0,0);
        lruCache.put(1,1);
        lruCache.put(2,2);
        lruCache.put(3,3);
        lruCache.put(4,4);
        lruCache.put(5,5);
        lruCache.put(6,6);
        int i = lruCache.get(3);
        System.out.println(lruCache.map);
    }
}


输出:
{4=4, 5=5, 6=6, 3=3}

这篇关于实现LRU缓存淘汰算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!