46 | 缓存系统:如何通过哈希表和队列实现高效访问?
黄申

你好,我是黄申。
经过前三大模块的学习,我带你纵览了数学在各个计算机编程领域的重要应用。离散数学是基础数据结构和编程算法的基石,而概率统计论和线性代数,是很多信息检索和机器学习算法的核心。
因此,今天开始,我会综合性地运用之前所讲解的一些知识,设计并实现一些更有实用性的核心模块或者原型系统。通过这种基于案例的讲解,我们可以融会贯通不同的数学知识,并打造更加高效、更加智能的计算机系统。首先,让我们从一个缓存系统入手,开始综合应用篇的学习。
什么是缓存系统?
缓存(Cache)是计算机系统里非常重要的发明之一,它在编程领域中有非常非常多的应用。小到电脑的中央处理器(CPU)、主板、显卡等硬件,大到大规模的互联网站点,都在广泛使用缓存来提升速度。而在网站的架构设计中,一般不会像 PC 电脑那样采用高速的缓存介质,而是采用普通的服务器内存。但是网站架构所使用的内存容量大得多,至少是数个吉字节 (GB)。
我们可以把缓存定义为数据交换的缓冲区。它的读取速度远远高于普通存储介质,可以帮助系统更快地运行。当某个应用需要读取数据时,会优先从缓存中查找需要的内容,如果找到了则直接获取,这个效率要比读取普通存储更高。如果缓存中没有发现需要的内容,再到普通存储中寻找。
公开
同步至部落
取消
完成
0/2000
笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《程序员的数学基础课》,新⼈⾸单¥68
《程序员的数学基础课》,新⼈⾸单¥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
- 013923Cache 是计算机OS的基本元件归属地:上海1
- 013923学习了Cache缓存系统;计算机基础课程归属地:上海1
收起评论