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モードの1つ)を採用しています.
 
それ自体もConcurrentMapインタフェースを実現しているので、ConcurrentHashMapと同じように使用されています.まずはput
 
3つの要素を入れて、最初の要素を取得します.やはりnullです.LRU(最近使用されている)アルゴリズムに基づいて、key=1の節です.
 
時はもう失効した.
 
ソース解析
まず全体のフレームワークを見てみましょう

本質は、双方向チェーンテーブルを追加的に維持し、読み取りと書き込みのたびに対応するノードの位置を変更し、キューヘッダに移動することです.
 
いつ判断しやすいかはweightによる.各要素にはweightがあり、1つの要素を追加するたびに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