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

黄申

你好，我是黄申。
经过前三大模块的学习，我带你纵览了数学在各个计算机编程领域的重要应用。离散数学是基础数据结构和编程算法的基石，而概率统计论和线性代数，是很多信息检索和机器学习算法的核心。
因此，今天开始，我会综合性地运用之前所讲解的一些知识，设计并实现一些更有实用性的核心模块或者原型系统。通过这种基于案例的讲解，我们可以融会贯通不同的数学知识，并打造更加高效、更加智能的计算机系统。首先，让我们从一个缓存系统入手，开始综合应用篇的学习。
什么是缓存系统？缓存（Cache）是计算机系统里非常重要的发明之一，它在编程领域中有非常非常多的应用。小到电脑的中央处理器（CPU）、主板、显卡等硬件，大到大规模的互联网站点，都在广泛使用缓存来提升速度。而在网站的架构设计中，一般不会像 PC 电脑那样采用高速的缓存介质，而是采用普通的服务器内存。但是网站架构所使用的内存容量大得多，至少是数个吉字节 （GB）。
我们可以把缓存定义为数据交换的缓冲区。它的读取速度远远高于普通存储介质，可以帮助系统更快地运行。当某个应用需要读取数据时，会优先从缓存中查找需要的内容，如果找到了则直接获取，这个效率要比读取普通存储更高。如果缓存中没有发现需要的内容，再到普通存储中寻找。

公开

同步至部落

取消

完成

0/2000

荧光笔

直线

曲线

笔记

复制

AI

深入了解
翻译
英语
中文简体
中文繁体
法语
德语
日语
韩语
俄语
西班牙语
阿拉伯语
解释
总结

仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《程序员的数学基础课》，新⼈⾸单¥68

立即购买

登录后留言

全部留言(11)

最新
精选

铁丑-王立丰
查找数据是否在队列这个成本也不小啊
作者回复: 这是个好问题，正常的情况下，我们假设哈希表和队列里的数据一致，除非发生了异常。如果是这样，我们可以利用链表来实现队列，然后使用哈希表存储每个被缓存结果所对应的队列结点，这样我们可以快速访问队列的结点，并使用链表结点的移动来实现队列内结点的移动。

6
铁丑-王立丰
嗯嗯，我下午也在想，这个队列应该是一个双向链表，而且新加的哈希表可能还要解决队列节点的冲突问题。设计的再复杂一点这个结构应该能够和原有的那张缓存哈希表融合。这样还能节省内存。
作者回复: 融合的概念很新颖，代码可读性会弱一点，但是效率很高👍

5
小灰
老师请教一下，(1+7+5)/10^6=13 这个是怎么计算的
作者回复: 由于排版的关系，应该是(1+7+5)%10^6，其中10^6表示10的6次方，计算优先级最高，所以是13%1000000，而%表示求余，求余为13

1
qinggeouye
# 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也有类似哈希表的查询效率，那么也是一种更简洁的实现方式。

1
失火的夏天
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); } } }
作者回复: 实现的很仔细👍

1
失火的夏天
因为篇幅不够，分段截出来了，这里先声明一个内部类，表示为队列（链表）的节点，接下来的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; } }

3
Paul Shan
缓存意味着数据源有两个，而且这两个数据源访问成本和数据完备度不同。访问成本低的数据不完备，数据完备的访问成本高。要结合这两个数据源来设计访问成本尽可能低，同时数据又是完备的系统。基于队列和哈希表实现的LRU算法是经典算法之一。队列维护缓存大小，满的时候淘汰最近没用到的数据。哈希表提升查询效率。每次访问，先查哈希表，如果数据存在，将该数据放到队列尾部，让其远离被淘汰的位置，然后返回数据。如果数据不存在，就从完备的数据源中取得数据，将数据放入队列，如果队列已满，则淘汰掉最近最少用的数据，然后得到最新返回的数据。队列要面临频繁的插入和改位置操作，选用基于双向链表的队列较为高效。

2
013923
使用哈希表和队列可以实现高效访问；
归属地：上海

1
013923
Cache 是计算机OS的基本元件
归属地：上海

1
013923
学习了Cache缓存系统；计算机基础课程
归属地：上海

1

收起评论