极客时间-轻松学习，高效学习-极客邦

铁丑-王立丰

2019-04-04

嗯嗯，我下午也在想，这个队列应该是一个双向链表，而且新加的哈希表可能还要解决队列节点的冲突问题。设计的再复杂一点这个结构应该能够和原有的那张缓存哈希表融合。这样还能节省内存。

作者回复: 融合的概念很新颖，代码可读性会弱一点，但是效率很高👍



 2

铁丑-王立丰

2019-04-03

查找数据是否在队列这个成本也不小啊

作者回复: 这是个好问题，正常的情况下，我们假设哈希表和队列里的数据一致，除非发生了异常。
如果是这样，我们可以利用链表来实现队列，然后使用哈希表存储每个被缓存结果所对应的队列结点，这样我们可以快速访问队列的结点，并使用链表结点的移动来实现队列内结点的移动。



 2

Paul Shan

2019-10-14

缓存意味着数据源有两个，而且这两个数据源访问成本和数据完备度不同。访问成本低的数据不完备，数据完备的访问成本高。要结合这两个数据源来设计访问成本尽可能低，同时数据又是完备的系统。基于队列和哈希表实现的LRU算法是经典算法之一。队列维护缓存大小，满的时候淘汰最近没用到的数据。哈希表提升查询效率。每次访问，先查哈希表，如果数据存在，将该数据放到队列尾部，让其远离被淘汰的位置，然后返回数据。如果数据不存在，就从完备的数据源中取得数据，将数据放入队列，如果队列已满，则淘汰掉最近最少用的数据，然后得到最新返回的数据。队列要面临频繁的插入和改位置操作，选用基于双向链表的队列较为高效。



 1

失火的夏天

2019-04-01

因为篇幅不够，分段截出来了，这里先声明一个内部类，表示为队列（链表）的节点，接下来的Node节点是这个内部类
private class Node{
        private Node prev;
        private Node next;
        private int key;
        private int value;

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

展开



 1

qinggeouye

2019-04-09

# collections 的 OrderedDict()

class LRUCache:

    def __init__(self, capacity):
        self.capacity = capacity
        self.queue = collections.OrderedDict()

    def get(self, key):
        if key not in self.queue:
            return -1 # 要找的数据不在缓存中则返回 -1
        value = self.queue.pop(key) # 将命中缓存的数据移除
        self.queue[key] = value # 将命中缓存的数据重新添加到头部
        return self.queue[key]

    def put(self, key, value):
        if key in self.queue: # 如果已经存在缓存中，则先移除老的数据
            self.queue.pop(key)
        elif len(self.queue.items()) == self.capacity:
            self.queue.popitem(last=False) # 如果不存在缓存并且达到最大容量则把最后的数据淘汰
        self.queue[key] = value # 将新数据添加到头部

展开

作者回复: 这部分实现主要侧重于queue实现LRU策略，依赖于Python queue的查找机制，如果Python的queue也有类似哈希表的查询效率，那么也是一种更简洁的实现方式。





失火的夏天

2019-04-01

class LRUCache {

    private Node head;// 最近最少使用，类似列队的头，出队
    private Node tail;// 最近最多使用，类似队列的尾，入队
    private Map<Integer,Node> cache;
    private int capacity;

    public LRUCache(int capacity) {
        this.cache = new HashMap<>();
        this.capacity = capacity;
    }

    public int get(int key) {
        Node node = cache.get(key);
        if(node == null){
            return -1;
        }else{
            moveNode(node);
            return node.value;
        }
    }

    public void put(int key, int value) {
        Node node = cache.get(key);
        if (node != null){
            node.value = value;
            moveNode(node);
        }else {
            removeHead();
            node = new Node(key,value);
            addNode(node);
        }
        cache.put(key,node);
    }

    private void removeHead(){
        if (cache.size() == capacity){
            Node tempNode = head;
            cache.remove(head.key);
            head = head.next;
            tempNode.next = null;
            if (head != null){
                head.prev = null;
            }
        }
    }

    /**
     * 链表加入节点
     * @param node
     */
    private void addNode(Node node){
        if (head == null){
            head = node;
            tail = node;
        }else {
            addNodeToTail(node);
        }
    }

    private void addNodeToTail(Node node){
        node.prev = tail;
        tail.next = node;
        tail = node;
    }

    private void moveNode(Node node){
        if(head == node && node != tail){
            head = node.next;
            head.prev = null;
            node.next = null;
            addNodeToTail(node);
        }else if (tail == node){
            // 不做任何操作
        }else {
            // 普遍情况，node节点移除链表，加入到尾节点后面，tail指针指向node
            node.prev.next = node.next;
            node.next.prev = node.prev;
            node.next = null;
            addNodeToTail(node);
        }
    }
}

展开

作者回复: 实现的很仔细👍



