46 | 缓存系统：如何通过哈希表和队列实现高效访问？

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

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

老师请教一下，(1+7+5)/10^6=13 这个是怎么计算的

# 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 # 将新数据添加到头部

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); } } }

因为篇幅不够，分段截出来了，这里先声明一个内部类，表示为队列（链表）的节点，接下来的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; } }

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

使用哈希表和队列可以实现高效访问；

Cache 是计算机OS的基本元件

学习了Cache缓存系统；计算机基础课程