LRUCache的实现原理及利用python实现的方法
简介
LRU(LeastRecentlyUsed)最近最少使用,最近有时间和空间最近的歧义,所以我更喜欢叫它近期最少使用算法。它的核心思想是,如果一个数据被访问过,我们有理由相信它在将来被访问的概率就越高。于是当LRU缓存达到设定的最大值时将缓存中近期最少使用的对象移除。LRUCache内部使用LinkedHashMap来存储key-value键值对,并将LinkedHashMap设置为访问顺序来体现LRU算法。
无论是对某个key的get,还是set都算做是对该key的一次使用。当set一个不存在的key,并且LRUCache中key的数量超过cachesize的时候,需要将使用时间距离现在最长的那个key从LRUCache中清除。
LRUCache实现
在Java中,LRUCache是通过LinkedHashMap实现的。鄙人照猫画虎,实现一个Python版的LRUCache(可能和其他大神的实现有所区别)。
首先,需要说明的是:
LRUCache对象内部会维护一个双端循环链表的头节点
LRUCache对象内部会维护一个dict
内部dict的value都是Entry对象,每个Entry对象包含:
- key的hash_code(hash_code=hash(key),在本实现中,hash_code相同的不同key,会被当作一个key来处理。因此,对于自定义类,应该实现魔术方法:__hash__)
- v-(key,value)对中的value
- prev-前一个对象
- next-后一个对象
具体实现是:
当从LRUCache中get一个key的时候:
- 计算该key的hash_code
- 从内部dict中获取到entry
- 将该entry移动到双端循环链表的第一个位置
- 返回entry.value
当向LRUCache中set一个(key,value)对的时候:
计算该key的hash_code,
从LRUCache的内部dict中,取出该hash_code对应的old_entry(可能不存在),然后根据(key,value)对生成一个new_entry,之后执行:
- dict[hash_code]=new_entry
- 将new_entry提到双端循环链表的第一个位置
- 如果old_entry存在,则从链表中删除old_entry
- 如果是新增了一个(key,value)对,并且cache中key的数量超过了cachesize,那么将双端链表的最后一个元素删除(该元素就是那个最近最少被使用的元素),并且从内部dict中删除该元素
HashMap的实现原理
(面试过程中也经常会被问到):数组和链表组合成的链表散列结构,通过hash算法,尽量将数组中的数据分布均匀,如果hashcode相同再比较equals方法,如果equals方法返回false,那么就将数据以链表的形式存储在数组的对应位置,并将之前在该位置的数据往链表的后面移动,并记录一个next属性,来指示后移的那个数据。
注意:数组中保存的是entry(其中保存的是键值)
Python实现
classEntry: 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): return"Entry{hash_code=%d,v=%s}"%( self.hash_code,self.v) __repr__=__str__ classLRUCache: def__init__(self,max_size): self._max_size=max_size self._dict=dict() self._head=Entry(None,None) self._head.prev=self._head self._head.next=self._head def__setitem__(self,k,v): try: hash_code=hash(k) exceptTypeError: raise old_entry=self._dict.get(hash_code) new_entry=Entry(hash_code,v) self._dict[hash_code]=new_entry ifold_entry: prev=old_entry.prev next=old_entry.next prev.next=next next.prev=prev head=self._head head_prev=self._head.prev head_next=self._head.next head.next=new_entry ifhead_previshead: head.prev=new_entry head_next.prev=new_entry new_entry.prev=head new_entry.next=head_next ifnotold_entryandlen(self._dict)>self._max_size: last_one=head.prev last_one.prev.next=head head.prev=last_one.prev self._dict.pop(last_one.hash_code) def__getitem__(self,k): entry=self._dict[hash(k)] head=self._head head_next=head.next prev=entry.prev next=entry.next ifentry.previsnothead: ifhead.previsentry: head.prev=prev head.next=entry head_next.prev=entry entry.prev=head entry.next=head_next prev.next=next next.prev=prev returnentry.v defget_dict(self): returnself._dict if__name__=="__main__": cache=LRUCache(2) inner_dict=cache.get_dict() cache[1]=1 assertinner_dict.keys()==[1],"test1" cache[2]=2 assertsorted(inner_dict.keys())==[1,2],"test2" cache[3]=3 assertsorted(inner_dict.keys())==[2,3],"test3" cache[2] assertsorted(inner_dict.keys())==[2,3],"test4" assertinner_dict[hash(2)].next.v==3 cache[4]=4 assertsorted(inner_dict.keys())==[2,4],"test5" assertinner_dict[hash(4)].v==4,"test6"
总结
以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,如果有疑问大家可以留言交流,谢谢大家对毛票票的支持。