concurrenthashmap

简介

　　１.7的ConcurrentHashMap最重要的一点就是Segment这个概念，每一个Segment就是一个小的HashMap，可以将这个理解为2级哈希表，一个总的Segment数组，每个数组里面存放一个类似Hashmap的结构，而加锁则是对Segment进行加锁。
Segment继承自ReentrantLock，所以我们可以很方便的对每一个Segment上锁
　　1.8的则抛弃其冗余的设计，采用Node + CAS + Synchronized来保证并发安全进行实现，分析下其如何实现的吧。
　　点到ConcurrentHashMap的put方法里面，分析下源码：

if (tab == null || (n = tab.length) == 0)
            tab = initTable();

　　当数组为空时，初始化数组。

private final Node<K,V>[] initTable() {
    Node<K,V>[] tab; int sc;
    while ((tab = table) == null || tab.length == 0) {
        if ((sc = sizeCtl) < 0)
            Thread.yield(); // lost initialization race; just spin
        else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
            try {
                if ((tab = table) == null || tab.length == 0) {
                    int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                    @SuppressWarnings("unchecked")
                    Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                    table = tab = nt;
                    sc = n - (n >>> 2);
                }
            } finally {
                sizeCtl = sc;
            }
            break;
        }
    }
    return tab;
}

　　初始化部分全部使用了CAS来完成线程安全。

else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
           if (casTabAt(tab, i, null,
                        new Node<K,V>(hash, key, value, null)))
               break;                   // no lock when adding to empty bin
       }

　　如果相应位置的Node还未初始化，则通过CAS插入相应的数据
　　然后判断其数组不为空，那么就对这个节点加锁，然后插入数据

synchronized (f) {
               if (tabAt(tab, i) == f) {
                   if (fh >= 0) {
                       binCount = 1;
                       for (Node<K,V> e = f;; ++binCount) {
                           K ek;
                           if (e.hash == hash &&
                               ((ek = e.key) == key ||
                                (ek != null && key.equals(ek)))) {
                               oldVal = e.val;
                               if (!onlyIfAbsent)
                                   e.val = value;
                               break;
                           }
                           Node<K,V> pred = e;
                           if ((e = e.next) == null) {
                               pred.next = new Node<K,V>(hash, key,
                                                         value, null);
                               break;
                           }
                       }
                   }
                   else if (f instanceof TreeBin) {
                       Node<K,V> p;
                       binCount = 2;
                       if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                      value)) != null) {
                           oldVal = p.val;
                           if (!onlyIfAbsent)
                               p.val = value;
                       }
                   }
               }
           }

　　判断，链表就用链表的方式添加，红黑树就用红黑树的方式添加。

if (binCount != 0) {
               if (binCount >= TREEIFY_THRESHOLD)
                   treeifyBin(tab, i);
               if (oldVal != null)
                   return oldVal;
               break;
           }

如果大于了一个阈值，就将链表转换为数组。
嗯就这样，也就是说，1.8的HashMap和ConcurrentHashMap都是大致一样的数据结构，只是其中是否加锁。