Leetcode 146 LRU(最近最少使用)缓存机制

最近最少使用的一个缓存机制是操作系统这门课程里面的一个概念

非常直观基本的一个思路就是HashMap+加双端链表

使用 HashMap 是为了提高查找的一个效率在O(1)

双端链表是为了提高增加或者交换元素位置时的开销O(1)

当然这么做是代价,是使用了一些额外的空间O(n)

下面的代码参考自官方文档的题解。

class LRUCache extends LinkedHashMap<Integer, Integer>{

    int capacity;
    public LRUCache(int capacity) {
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }
    
    public int get(int key) {
        int res = super.getOrDefault(key, -1);
        return res;
    }
    
    public void put(int key, int value) {
        super.put(key, value);
    }

    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {

        return size() > capacity;
    }
}

值得注意的是Java语言内部实现了这个结构非常和我们需求很相符,

其中内部内置final private boolean assessOrder这个变量,如果这个变量值是true的话,每次get操作get到的那个元素/(或者put插入的元素)会插入到链表头的位置。是在初始化的时候默认值是false,所以我们要在构造函数显式给定

同时在put方法结束前的最后会调用remove all these entry这个方法,这个方法返回true,就会去掉最后一个元素,默认是返回一个false,所以我们要对这个方法进行重写,以满足我们的需求。

当然也可以手写一个双向链表和使用Hashmap的方式实现

class LRUCache{

    class Node {
        int val;
        int key;
        Node pre;
        Node next;
        public Node(int key, int val) {this.key = key; this.val = val;}
    }
    int capacity;
    Node dummyHead = new Node(0,0);
    Node dummyTail = new Node(0,0);
    HashMap<Integer, Node> hm = new HashMap<>();
    public LRUCache(int capacity) {
        this.capacity = capacity;
        dummyHead.next = dummyTail;
        dummyTail.pre = dummyHead;
    }
    
    public int get(int key) {
        if (hm.containsKey(key)) {
            Node cur = hm.get(key);
            moveToHead(cur, true);
            return cur.val;
        }
        return -1;
    }
    
    public void put(int key, int value) {
        if (hm.containsKey(key)) {
            Node cur = hm.get(key);
            cur.val = value;
            moveToHead(cur, true);
        } else {
            Node cur = new Node(key, value);
            hm.put(key, cur);
            moveToHead(cur, false);
            if (hm.size() > capacity)
                removeTail();
        }
    }

    private void moveToHead(Node cur, boolean removeFlag) {
        if (removeFlag) {
            cur.pre.next = cur.next;
            cur.next.pre = cur.pre;
        }
        cur.pre = dummyHead;
        cur.next = dummyHead.next;
        dummyHead.next.pre = cur;
        dummyHead.next = cur;
    }

    private void removeTail() {
        Node cur = dummyTail.pre;
        cur.pre.next = cur.next;
        cur.next.pre = cur.pre;
        cur.next = null;
        cur.pre = null;
        hm.remove(cur.key);
    }

    private void printList(){
        Node cur = dummyHead.next;
        while (cur != dummyTail) {
            System.out.print("" + cur.val + "->");
            cur = cur.next;
        }
        System.out.println();
    }

}

发表评论

电子邮件地址不会被公开。 必填项已用*标注