哪个Map最适合用来实现LRU Cache?

问题描述

前段时间面试碰到的一道题,最近进了这家公司了,再拿出来看看。求大神继续解脱。30.下面哪个Map最适合用来实现LRUCache?A.HashtableB.TreeMapC.HashMapD.IdentityHashMapE.WeakHashMap网上给的答案是A。为什么?大家一般如何实现这个最近最少使用cache?

解决方案

解决方案二:
就那几个可选的来说只能是A了因为是线程安全的不过个人认为应该用Mapmap=Collections.synchronizedMap(newLinkedHashMap());
解决方案三:
,平时很少用到
解决方案四:
连表HashMap最合适,可以修正排序位置.
解决方案五:
引用3楼guishuanglin的回复:

连表HashMap最合适,可以修正排序位置.

LinkedHashMap么?
解决方案六:
是的,我觉得LinkedHashMap很合适,这个本来在jdk说明中就有说可以用做lru的原始说明的.你可以查api
解决方案七:
你这个重点是cache既然是cache就一定要注意“容器”的线程安全方面的东西lru是你cache的实现算法,算法实现上要先保证数据的正确性,,再考虑性能所以,,,就像我在2#回复的一样了
解决方案八:
因为hashmap的实现原理是表(数组)+链表的形式来实现的,当查找一个key时,先计算hashcode,得到对应该的entry<K,V>,entry是链表结构,调用其next方法逐个entry来跟k比较,最终取得value。如果再次查找同一个key,就只计算hashcode即可取得value,因为在上次取的时候已经把entry的链表指针指向了这个value
解决方案:
LinkedHashMap双向链表
解决方案:
引用8楼xiongweiyu88的回复:

LinkedHashMap双向链表

能不能详细阐述下原因?这样的回答makenosense哦。
解决方案:
A.HashtableB.TreeMapC.HashMapD.IdentityHashMapE.WeakHashMap首先可以确定E不对D我没用过就不乱说了A不合适,不说有更好的ConcurrentHashMap,也不说Hashtable这个类本身已经被认为过时了,单从设计的角度来说,它本身不管三七二十一先加了锁,限制了你设计上的灵活度,或者说你设计上很可能不需要它这种加锁方式。Hashtable这种类,说它“线程安全”,它真的安全吗?CHashMap比A好,因为要想像A那样加锁,你随时可以用Collections.synchronizedMap(map)把你的map保护起来,HashMap本身不是线程安全的,正因为这样,你可以用任何最合适的方式来保护它,以实现线程安全。比较一下A和C,C是块漂亮的好砖,可以拿来盖房子,铺地板,怎么都好用,因为它不多管闲事;A是快自作聪明的坏砖,它身上先自己抹了水泥,——你有六面你知道我需要你哪一面抹水泥?B从效率上说,应该不如C合适。
解决方案:
LRU需要删除最近最少使用的元素,也就是说,需要排序功能找出最近最少使用的那个元素,所提供的几个选项里只有TreeMap适合。
解决方案:
如果只有上面的选择,我选择:HashMap,理由:1LinkedHashMap是HashMap的子类.2LinkedHashMap明确说明"很适合构建LRU缓存",实现了"从近期访问最少到近期访问最多的顺序".所以:如果用hashMap自己实现"MyLinkedHashMap"用来构建LRU更实际.

时间: 2016-06-17

哪个Map最适合用来实现LRU Cache?的相关文章

LeetCode: LRU Cache 最近最少使用算法 缓存设计

设计并实现最近最久未使用(Least Recently Used)缓存.   题目描述: Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set. get(key) - Get the value (will always be positive) of the key if the key

LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set. get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.set(

请问编程一个移动聊天(如微信)应用最适合用什么语言(java/C#/C++)

问题描述 请问编程一个移动聊天(如微信)应用最适合用什么语言(java/C#/C++) 我想编程一个移动聊天应用,请问有什么语言最适合编程移动聊天应用?如果我想要用C#来编程的话会有什么优势与劣势与JAVA相比的话 解决方案 (pc c++ c#) (android java c c++) 解决方案二: 得是iOS,android,wPhone这些吧 解决方案三: 用Java吧,可以直接用于android开发~最好的语言~ 解决方案四: 如果是pc桌面程序就用c++,如果是手机移动端-用安卓吧-

[LeetCode] LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set. get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1. set

Redis作为LRU Cache的实现

公有云Redis服务:https://www.aliyun.com/product/kvstore?spm=5176.8142029.388261.37.59zzzj 背景 Redis作为目前最流行的KV内存数据库,也实现了自己的LRU(Latest Recently Used)算法,在内存写满的时候,依据其进行数据的淘汰.LRU算法本身的含义,这里不做赘述,严格的LRU算法,会优先选择淘汰最久没有访问的数据,这种实现也比较简单,通常是用一个双向链表+一个哈希表来实现O(1)的淘汰和更新操作.但

大学生最适合用哪个系统:windows 7

如果你还在为适用什么系统而烦恼,那么这篇文章将告诉你,给你使用win7系统的四个理由.让你根据你的实际情况,来选择最适合你的系统. 1 游戏性更好 相信用过windows 7系统的人都知道,win 7系统的画面非常的美,如果你是玩3D之类的游戏.那么用win7系统你更能体验到该游戏的画面美.而win 7系统支持最新的DirectX 11技术,这让我们在玩游戏的适合更顺畅. 2 兼容性更好 win7出来了这么久,而且越来越成为主流.导致现在有些最新软件都只支持win7而不支持xp了.相比于其他不是

关于LRU缓存的实现算法讨论

业务模型 读.写.删的比例大致是7:3:1,至少要支持500w条缓存,平均每条缓存6k,要求设计一套性能比较好 的缓存算法. 算法分析 不考虑MemCached,Velocity等现成的key-value缓存方案,也不考虑脱离.NET gc自己管理内存,不考 虑随机读取数据及顺序读取数据的场景,目前想到的有如下几种LRU缓存方案 算法 分析 SortedDictionary .NET自带的,内部用二叉搜索树(应该不是普通树,至少是做过优化的树)实现的,检索为O (log n),比普通的Dicti

java LRU(Least Recently Used )详解及实例代码_java

java LRU(Least Recently Used )详解 LRU是Least Recently Used 的缩写,翻译过来就是"最近最少使用",LRU缓存就是使用这种原理实现,简单的说就是缓存一定量的数据,当超过设定的阈值时就把一些过期的数据删除掉,比如我们缓存10000条数据,当数据小于10000时可以随意添加,当超过10000时就需要把新的数据添加进来,同时要把过期数据删除,以确保我们最大缓存10000条,那怎么确定删除哪条过期数据呢,采用LRU算法实现的话就是将最老的数据

浅析LRU(K-V)算法缓存教程

LRU(Least Recently Used)算法是缓存技术中的一种常见思想,顾名思义,最近最少使用,也就是说有两个维度来衡量,一个是时间(最近),一个频率(最少).如果需要按优先级来对缓存中的K-V实体进行排序的话,需要考虑这两个维度,在LRU中,最近使用频率最高的排在前面,也可以简单的说最近访问的排在前面.这就是LRU的大体思想. 在操作系统中,LRU是用来进行内存管理的页面置换算法,对于在内存中但又不用的数据块(内存块)叫做LRU,操作系统会根据哪些数据属于LRU而将其移出内存而腾出空间