乐趣区

关于java:实现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}

退出移动版