手写LRU

LRU算法简介

LRU是Least Recently Used的缩写，即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的数据予以淘汰。

LRU的思想

• 写操作+读操作时间复杂度都需要为O(1)
• 必须要有顺序之分，区分最近使用的和很久没有使用的数据排序

查找快、插入快、删除快，（O(1)时间复杂度）且还需要先后排序———->什么样的数据结构可以满足这个问题？

LRU的算法核心是哈希链表

巧用LinkedHashMap完成LRU算法

import java.util.LinkedHashMap;
import java.util.Map;

public class LRUDemo extends LinkedHashMap<Integer, Integer> {
    private int capacity;

    public LRUDemo(int initialCapacity) {
        super(initialCapacity, 0.75F, true);
        this.capacity = initialCapacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return super.size() > capacity;
    }

    public static void main(String[] args) {
        LRUDemo lruDemo = new LRUDemo(3);

        lruDemo.put(1, 1);
        lruDemo.put(2, 2);
        lruDemo.put(3, 3);

        System.out.println(lruDemo.keySet());

        lruDemo.put(4, 4);
        System.out.println(lruDemo.keySet());

        lruDemo.put(3, 3);
        lruDemo.put(3, 3);
        System.out.println(lruDemo.keySet());
    }
}

输出结果：

[1, 2, 3]
[2, 3, 4]
[2, 4, 3]