google的ConcurrentLinkedHashmap源代码解析
简述
ConcurrentLinkedHashMap 是google团队提供的一个容器。它有什么用呢?其实它本身是对
?
ConcurrentHashMap的封装,可以用来实现一个基于LRU策略的缓存。详细介绍可以参见?
?
http://code.google.com/p/concurrentlinkedhashmap
?
使用范例
public static void main(String[] args) {ConcurrentLinkedHashMap<Integer, Integer> map = new ConcurrentLinkedHashMap.Builder<Integer,Integer>().maximumWeightedCapacity(2).
weigher(Weighers.singleton()).build();
map.put(1, 1);map.put(2, 2);map.put(3, 3);System.out.println(map.get(1));//null 已经失效了System.out.println(map.get(2));}
?
?ConcurrentLinkedHashMap 的构造函数比较特殊,它采用了Builder(构造器,GOF模式之一)。
?
它本身也是实现了ConcurrentMap接口的,所以使用起来跟ConcurrentHashMap一样。我们先put
?
进去三个元素,然后获取第一个元素,果然是null,因为基于LRU(最近使用)算法,key=1的节
?
点已经失效了。
?
源代码解析
先来看看它的整体框架
它本质是额外维护了一个双向链表,每次读和写都要改变相应节点的位置,将其移至队列头。
?
什么时候判断容易已经满了,是根据weight。每个元素都有一个weight,每增加一个元素,weight累计。当达到最大值的时候,就需要剔除最少操作的那个元素了,并且触发相关的事件。
?
我们先来看put函数
?
V put(K key, V value, boolean onlyIfAbsent) { checkNotNull(value); final int weight = weigher.weightOf(key, value);//计算weight final WeightedValue<V> weightedValue = new WeightedValue<V>(value, weight); final Node node = new Node(key, weightedValue);//对数据进行包装,准备存入ConcurrentHashMap for (;;) { final Node prior = data.putIfAbsent(node.key, node); if (prior == null) {//这个key之前没有值 afterCompletion(new AddTask(node, weight));//更新后续操作 return null; } else if (onlyIfAbsent) { afterCompletion(new ReadTask(prior)); return prior.getValue(); }
?
AddTask 是判断是否容量满了,需要剔除其他元素
final class AddTask extends AbstractTask { final Node node; final int weight; @Override @GuardedBy("evictionLock") public void run() { weightedSize += weight; // ignore out-of-order write operations if (node.get().isAlive()) { evictionDeque.add(node); evict();//是否移除失效的 } } } void evict() { while (hasOverflowed()) { Node node = evictionDeque.poll(); // If weighted values are used, then the pending operations will adjust // the size to reflect the correct weight if (node == null) { return; } // Notify the listener only if the entry was evicted if (data.remove(node.key, node)) {//移除失效的 pendingNotifications.add(node); } node.makeDead(); } }?
get函数更简单一点,只是将这个key节点移至队列头
public V get(Object key) { final Node node = data.get(key); if (node == null) { return null; } afterCompletion(new ReadTask(node)); return node.getValue(); }
?
性能比较 vs ConcurrentHashMap
不用说了,肯定是ConcurrentHashMap要好一点了,因为本文的主角还要维护一个操作队列嘛:)
不过性能上不是差很多,见下图。
总结:
利用ConcurrentLinkedHashMap来做基于LRU的缓存,还是值得推荐的。我们可以定义它的容器大小,基于LRU,就可以保证较高的命中率了。
?
参考资料:
http://code.google.com/p/concurrentlinkedhashmap
1 楼 BuN_Ny 2012-05-18 不错。·~~~~~