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

_Mryao 发布于 2013/12/18 22:32
阅读 1K+
收藏 0

 30. 下面哪个Map最适合用来实现LRU Cache?

A. Hashtable

B. TreeMap

C. HashMap

D. IdentityHashMap

E. WeakHashMap

这是一道笔试题来的,我自己想了下,到网上也搜索了下,大都使用LinkedHashMap.但是答案里并没有,求大神解脱!

加载中
0
_Mryao
_Mryao
晚上貌似都没人了~自己顶下。
0
狮子的魂
狮子的魂
LinkedHashMap
0
ueharaai
ueharaai
看了下api,确实是LinkedHashMap是最合适的,答案里面,只有hashtable可以用来实现linkedhaspmap,顾选A
0
优雅先生
优雅先生

我的浅薄看法:

IdentityHashMap比较键(和值)时使用引用相等性代替对象相等性,使用范围很窄。不太适合。

WeakHashMap是以弱键实现的基于哈希表的Map。对于一个给定的键,其映射的存在并不阻止垃圾回收器对该键的丢弃,并且这种丢弃是无法确定的,以为垃圾回收器进行垃圾回收本身具有不确定性。而LRU缓存是在缓存容量不足情况下移除最老的条目,是具有确定性的,所以不适合。

TreeMap是基于红黑树实现的,映射按键的自然顺序或者提供的Comparator进行排序,我觉得这个应该最适合用来实现LRU缓存的吧(相对题目中其他几个而言)?因为可以自定义一个按照最近使用频率排序的Comparator,这样条目就按照最近使用频率排列了,然后在缓存容量不足而需要移除最老的条目时也很简单。

Hashtable和HashMap除了前者是同步的,后者是非同步的,以及一个支持NULL KEY和NULL VALUE外,基本相同。这两个也应该都不太适合用作LRU Cache,移除旧条目效率比较低下,因为内部条目之间是无序的(确切来说,是根据indexForHash计算出一个hash值,然后hash值与桶个数进行与运算得到要存储的桶位置,桶就是bucket,每个桶中存的又是一个链表),需要额外自己去实现排序代码,而且删除老的条目时性能没有TreeMap好。

Catelyn
Catelyn
TreeMap是非同步的,如果使用集合工具类加上同步的话是否性能会比HashTable好呢,毕竟HashTable更简单些!并且HashTable的优势(甚至和ConcurrentHashMap相比)就是非常安全!
返回顶部
顶部