位置: 编程技术 - 正文
LRUCache的实现原理及利用python实现的方法(lrucache算法)
编辑：rootadmin推荐整理分享LRUCache的实现原理及利用python实现的方法(lrucache算法)，希望有所帮助，仅作参考，欢迎阅读内容。
文章相关热门搜索词:实现lru算法所需的硬件支持是什么?,lrucache算法,实现lru算法常用方法有几种,lru实现原理,lru实现原理,lrucache算法,实现lru算法常用方法有几种,lrucache原理,内容如对您有帮助，希望把文章链接给更多的朋友！
简介
LRU(Least Recently Used)最近最少使用，最近有时间和空间最近的歧义，所以我更喜欢叫它近期最少使用算法。它的核心思想是，如果一个数据被访问过，我们有理由相信它在将来被访问的概率就越高。于是当LRU缓存达到设定的最大值时将缓存中近期最少使用的对象移除。LRUCache内部使用LinkedHashMap来存储key-value键值对，并将LinkedHashMap设置为访问顺序来体现LRU算法。
无论是对某个key的get，还是set都算做是对该key的一次使用。当set一个不存在的key，并且LRU Cache中key的数量超过cache size的时候，需要将使用时间距离现在最长的那个key从LRU Cache中清除。
LRU Cache实现
在Java中，LRUCache是通过LinkedHashMap实现的。鄙人照猫画虎，实现一个Python版的LRU Cache（可能和其他大神的实现有所区别）。
首先，需要说明的是：
LRU Cache对象内部会维护一个 双端循环链表 的 头节点
LRU Cache对象内部会维护一个dict
内部dict的value都是Entry对象，每个Entry对象包含：
key的hash_code（hash_code = hash(key)，在本实现中，hash_code相同的不同key，会被当作一个key来处理。因此，对于自定义类，应该实现魔术方法：__hash__） v - (key, value)对中的value prev - 前一个对象 next - 后一个对象具体实现是：
当从LRU Cache中get一个key的时候：
计算该key的hash_code 从内部dict中获取到entry 将该entry移动到 双端循环链表 的 第一个位置 返回entry.value当向LRU Cache中set一个(key, value)对的时候：
计算该key的hash_code，
从LRU Cache的内部dict中，取出该hash_code对应的old_entry（可能不存在），然后根据(key, value)对生成一个new_entry，之后执行：
dict[hash_code] = new_entry 将new_entry提到 双端循环链表 的第一个位置 如果old_entry存在，则从链表中删除old_entry 如果是新增了一个(key, value)对，并且cache中key的数量超过了cache size，那么将双端链表的最后一个元素删除（该元素就是那个最近最少被使用的元素），并且从内部dict中删除该元素HashMap的实现原理
（面试过程中也经常会被问到）：数组和链表组合成的链表散列结构，通过hash算法，尽量将数组中的数据分布均匀，如果hashcode相同再比较equals方法，如果equals方法返回false，那么就将数据以链表的形式存储在数组的对应位置，并将之前在该位置的数据往链表的后面移动，并记录一个next属性，来指示后移的那个数据。
注意：数组中保存的是entry（其中保存的是键值）
Python实现
总结
标签: lrucache算法
本文链接地址:https://www.jiuchutong.com/biancheng/372311.html 转载请保留说明！
