`
janeky
  • 浏览: 363457 次
  • 性别: Icon_minigender_1
  • 来自: 广州
社区版块
存档分类
最新评论

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

  • 大小: 7.3 KB
  • 大小: 46 KB
3
3
分享到:
评论
1 楼 BuN_Ny 2012-05-18  
不错。·~~~~~

相关推荐

Global site tag (gtag.js) - Google Analytics