ConcurrentHashMap 小析

ConcurrentHashMap中主要实体类就是三个：ConcurrentHashMap（整个Hash 表）,Segment（桶），HashEntry（节点），对应上面的图可以看出之间的关系。
    get方法（请注意，这里分析的方法都是针对桶的，因为ConcurrentHashMap的最大改进就是将粒度细化到了桶上），首先判断了当前桶的数据 个数是否为0，为0自然不可能get到什么，只有返回null，这样做避免了不必要的搜索，也用最小的代价避免出错。然后得到头节点（方法将在下面涉及） 之后就是根据hash和key逐个判断是否是指定的值，如果是并且值非空就说明找到了，直接返回；程序非常简单，但有一个令人困惑的地方，这句 return readValueUnderLock(e)到底是用来干什么的呢？研究它的代码，在锁定之后返回一个值。但这里已经有一句V v = e.value得到了节点的值，这句return readValueUnderLock(e)是否多此一举？事实上，这里完全是为了并发考虑的，这里当v为空时，可能是一个线程正在改变节点，而之前的 get操作都未进行锁定，根据bernstein条件，读后写或写后读都会引起数据的不一致，所以这里要对这个e重新上锁再读一遍，以保证得到的是正确 值，这里不得不佩服Doug Lee思维的严密性。整个get操作只有很少的情况会锁定，相对于之前的Hashtable，并发是不可避免的啊！

V get(Object key, int hash) {
           if (count != 0) { // read-volatile
               HashEntry e = getFirst(hash);
               while (e != null) {
                   if (e.hash == hash && key.equals(e.key)) {
                       V v = e.value;
                       if (v != null)
                           return v;
                       return readValueUnderLock(e); // recheck
                   }
                   e = e.next;
               }
           }
           return null;
       }
 

        V readValueUnderLock(HashEntry e) {
           lock();
           try {
               return e.value;
           } finally {
               unlock();
           }
       }

       


    put操作一上来就锁定了整个segment，这当然是为了并发的安全，修改数据是不能并发进行的，必须得有个判断是否超限的语句以确保容量不足时能够 rehash，而比较难懂的是这句int index = hash & (tab.length - 1)，原来segment里面才是真正的hashtable，即每个segment是一个传统意义上的hashtable,如上图，从两者的结构就可以看 出区别，这里就是找出需要的entry在table的哪一个位置，之后得到的entry就是这个链的第一个节点，如果e!=null，说明找到了，这是就 要替换节点的值（onlyIfAbsent == false），否则，我们需要new一个entry，它的后继是first，而让tab[index]指向它，什么意思呢？实际上就是将这个新entry 插入到链头，剩下的就非常容易理解了。

V put(K key, int hash, V value, boolean onlyIfAbsent) {
           lock();
           try {
               int c = count;
               if (c++ > threshold) // ensure capacity
                   rehash();
               HashEntry[] tab = table;
               int index = hash & (tab.length - 1);
               HashEntry first = (HashEntry) tab[index];
               HashEntry e = first;
               while (e != null && (e.hash != hash || !key.equals(e.key)))
                   e = e.next;

                V oldValue;
               if (e != null) {
                   oldValue = e.value;
                   if (!onlyIfAbsent)
                       e.value = value;
               }
               else {
                   oldValue = null;
                   ++modCount;
                   tab[index] = new HashEntry(key, hash, first, value);
                   count = c; // write-volatile
               }
               return oldValue;
           } finally {
               unlock();
           }
       }

       



    remove操作非常类似put，但要注意一点区别，中间那个for循环是做什么用的呢？（*号标记）从代码来看，就是将定位之后的所有entry克隆并 拼回前面去，但有必要吗？每次删除一个元素就要将那之前的元素克隆一遍？这点其实是由entry的不变性来决定的，仔细观察entry定义，发现除了 value，其他所有属性都是用final来修饰的，这意味着在第一次设置了next域之后便不能再改变它，取而代之的是将它之前的节点全都克隆一次。至 于entry为什么要设置为不变性，这跟不变性的访问不需要同步从而节省时间有关，关于不变性的更多内容，请参阅之前的文章《线程高级---线程的一些编 程技巧》

 V remove(Object key, int hash, Object value) {
           lock();
           try {
               int c = count - 1;
               HashEntry[] tab = table;
               int index = hash & (tab.length - 1);
               HashEntry first = (HashEntry)tab[index];
               HashEntry e = first;
               while (e != null && (e.hash != hash || !key.equals(e.key)))
                   e = e.next;

                V oldValue = null;
               if (e != null) {
                   V v = e.value;
                   if (value == null || value.equals(v)) {
                       oldValue = v;
                       // All entries following removed node can stay
                       // in list, but all preceding ones need to be
                       // cloned.
                       ++modCount;
                       HashEntry newFirst = e.next;
                   *    for (HashEntry p = first; p != e; p = p.next)
                   *        newFirst = new HashEntry(p.key, p.hash, 
                                                         newFirst, p.value);
                       tab[index] = newFirst;
                       count = c; // write-volatile
                   }
               }
               return oldValue;
           } finally {
               unlock();
           }
       }

 

    static final class HashEntry {
       final K key;
       final int hash;
       volatile V value;
       final HashEntry next;

        HashEntry(K key, int hash, HashEntry next, V value) {
           this.key = key;
           this.hash = hash;
           this.next = next;
           this.value = value;
       }
   }

      



    以上，分析了几个最简单的操作，限于篇幅，这里不再对rehash或iterator等实现进行讨论，有兴趣可以参考src。

    接下来实际上还有一个疑问，ConcurrentHashMap跟HashMap相比较性能到底如何。这在Brian Goetz的文章中已经有过评测http://www.ibm.com/developerworks/cn/java/j-jtp07233/。

  补充一下：
虽然ConcurrentHashMap是线程安全的，

看看下面一段代码：

ConcurrentHashMap<String,String> map; 
String getString(String name) { 
String x = map.get(name); 
if (x == null) {
x = new String();
map.put(name, x); 
} 
return x; 
}

如果你只调用get（），或只调用put（）时，ConcurrentHashMap是线程安全的。
但是，在你调用完get后，调用put之前，
如果有另外一个线程调用了map.put(name, x)，
你再去执行 map.put(name,x)，
就很可能把前面的操作结果覆盖掉了。
所以，即使在线程安全的情况下，代码一定要考虑周全,concurrentHashMap是原子性的, 然而可见性并不是一定的。

其他详情请看 http://www.ibm.com/developerworks/cn/java/j-jtp08223/

ConcurrentHashMap 使用了几个技巧来获得高程度的并发以及避免锁定，包括为不同的 hash bucket（桶）使用多个写锁和使用 JMM 的不确定性来最小化锁被保持的时间――或者根本避免获取锁。对于大多数一般用法来说它是经过优化的，这些用法往往会检索一个很可能在 map 中已经存在的值。事实上，多数成功的 get() 操作根本不需要任何锁定就能运行。（警告：不要自己试图这样做！想比 JMM 聪明不像看上去的那么容易。util.concurrent 类是由并发专家编写的，并且在 JMM 安全性方面经过了严格的同行评审。）

多个写锁

我们可以回想一下，Hashtable（或者替代方案 Collections.synchronizedMap） 的可伸缩性的主要障碍是它使用了一个 map 范围（map-wide）的锁，为了保证插入、删除或者检索操作的完整性必须保持这样一个锁，而且有时候甚至还要为了保证迭代遍历操作的完整性保持这样一 个锁。这样一来，只要锁被保持，就从根本上阻止了其他线程访问 Map，即使处理器有空闲也不能访问，这样大大地限制了并发性。

ConcurrentHashMap 摒弃了单一的 map 范围的锁，取而代之的是由 32 个锁组成的集合，其中每个锁负责保护 hash bucket 的一个子集。锁主要由变化性操作（put() 和 remove()） 使用。具有 32 个独立的锁意味着最多可以有 32 个线程可以同时修改 map。这并不一定是说在并发地对 map 进行写操作的线程数少于 32 时，另外的写操作不会被阻塞――32 对于写线程来说是理论上的并发限制数目，但是实际上可能达不到这个值。但是，32 依然比 1 要好得多，而且对于运行于目前这一代的计算机系统上的大多数应用程序来说已经足够了。&#160

map 范围的操作

有 32 个独立的锁，其中每个锁保护 hash bucket 的一个子集，这样需要独占访问 map 的操作就必须获得所有32个锁。一些 map 范围的操作，比如说size() 和 isEmpty()，也 许能够不用一次锁整个 map（通过适当地限定这些操作的语义），但是有些操作，比如 map 重排（扩大 hash bucket 的数量，随着 map 的增长重新分布元素），则必须保证独占访问。Java 语言不提供用于获取可变大小的锁集合的简便方法。必须这么做的情况很少见，一旦碰到这种情况，可以用递归方法来实现。