乐趣区

关于java:Leetcode-146-LRU-缓存机制

jiezi

前言

缓存是一种进步数据读取性能的技术，在计算机中 cpu 和主内存之间读取数据存在差别，CPU 和主内存之间有 CPU 缓存，而且在内存和硬盘有内存缓存。当主存容量远大于 CPU 缓存，或磁盘容量远大于主存时，哪些数据应该被应该被清理，哪些数据应该被保留，这就须要缓存淘汰策略来决定。常见的策略有三种：先进先出策略 FIFO(First In,First Out)、起码应用策略 LFU(Least Frequently Used)、最近起码应用策略 LRU(Least Recently Used)。

LRU 形容

设计和实现一个  LRU (最近起码应用) 缓存机制。
实现 LRUCache 类：

  • LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
  • int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1。
  • void put(int key, int value) 如果关键字曾经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字 - 值」。当缓存容量达到下限时，它应该在写入新数据之前删除最久未应用的数据值，从而为新的数据值留出空间。

解题思路 哈希表 + 双向链表

  • 针对 LRU 的特点，抉择应用双链表实现。
  • 应用 gut 办法获取数据，如果有数据，把返回数据，并且把数据放在链表头部。
  • 应用 put 办法存放数据，如果数据存在，间接笼罩新值；如果数据不存在，增加新值。新值都放在链表头部。此外，还须要判断缓存有没有超出容量 capacity，如果有超出，删除链表的尾结点。
  • 因为是单链表，每次获取数据，或者删除数据，都须要遍历一遍链表，工夫复杂度是 O(n), 这里应用 hash 来记录每个数据的地位，将数据拜访的工夫复杂度降到 O(1)。
class LRUCache {

    class DLinkedNode{
        int key;
        int value;
        DLinkedNode prev;
        DLinkedNode next;

        public DLinkedNode() {}

        public DLinkedNode(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    private int size;

    private int capacity;

    private DLinkedNode head;

    private DLinkedNode tail;

    private Map<Integer,DLinkedNode> cache = new HashMap<>();

    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.next = tail;
        tail.prev = head;
    }
    
    public int get(int key) {DLinkedNode node = cache.get(key);
        if (node == null) {return -1;}
        // 找到并挪动到首位
        moveToHead(node);
        return node.value;

    }
    
    public void put(int key, int value) {DLinkedNode node = cache.get(key);
        if (node == null) {
            // 不存在就创立一个新的节点
            DLinkedNode newNode = new DLinkedNode(key,value);
            cache.put(key,newNode);
            addToHead(newNode);
            size++;
            if (size > capacity) {
                // 超出容量，移除最初节点
                DLinkedNode tail = removeTail();
                cache.remove(tail.key);
                size--;
            }
        } else {
            //key 存在，笼罩 value，并移到头部
            if (node.value != value) {node.value = value;}
            moveToHead(node);

        }
    }

    private DLinkedNode removeTail() {
        DLinkedNode node = tail.prev;
        removeNode(node);
        return node;
    }

    private DLinkedNode removeNode(DLinkedNode node) {
        node.next.prev = node.prev;
        node.prev.next = node.next;
        return node;
    }

    private void moveToHead(DLinkedNode node) {removeNode(node);
        addToHead(node);
    }

    private void addToHead(DLinkedNode node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }
}

参考

[LRU 维基百科]()
极客工夫 - 王争 - 如何实现 LRU 缓存淘汰算法?

退出移动版