没有合适的资源?快使用搜索试试~ 我知道了~
温馨提示
试读
3页
简介 LRU(Least Recently Used)最近最少使用,最近有时间和空间最近的歧义,所以我更喜欢叫它近期最少使用算法。它的核心思想是,如果一个数据被访问过,我们有理由相信它在将来被访问的概率就越高。于是当LRU缓存达到设定的最大值时将缓存中近期最少使用的对象移除。LRUCache内部使用LinkedHashMap来存储key-value键值对,并将LinkedHashMap设置为访问顺序来体现LRU算法。 无论是对某个key的get,还是set都算做是对该key的一次使用。当set一个不存在的key,并且LRU Cache中key的数量超过cache size的时候,需要将使用时
资源详情
资源评论
资源推荐
LRUCache的实现原理及利用的实现原理及利用python实现的方法实现的方法
简介简介
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实现实现
class Entry:
def __init__(self, hash_code, v, prev=None, next=None):
self.hash_code = hash_code
self.v = v
self.prev = prev
self.next = next
def __str__(self):
weixin_38591011
- 粉丝: 4
- 资源: 919
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0