google的ConcurrentLinkedHashmap源代码解析

原文地址：http://janeky.iteye.com/blog/1534352
简述
ConcurrentLinkedHashMap 是google团队提供的一个容器。它有什么用呢？其实它本身是对

ConcurrentHashMap的封装，可以用来实现一个基于LRU策略的缓存。详细介绍可以参见

http://code.google.com/p/concurrentlinkedhashmap

使用范例
Java代码  收藏代码
public static void main(String[] args) { 
ConcurrentLinkedHashMap<Integer, Integer> map = new  
<span style="white-space: pre;">    </span>ConcurrentLinkedHashMap.Builder<Integer,Integer>().maximumWeightedCapacity(2). 
Java代码  收藏代码
weigher(Weighers.singleton()).build(); 
Java代码  收藏代码
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函数

Java代码  收藏代码
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 是判断是否容量满了，需要剔除其他元素
Java代码  收藏代码
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节点移至队列头
Java代码  收藏代码
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