面试：为了进阿里，死磕了ConcurrentHashMap源码和面试题(一)

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        volatile V val;  //使用了volatile属性
        volatile Node<K,V> next;  //使用了volatile属性
      ...
    }
复制代码

static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
        return (Node<K,V>)U.getObjectAcquire(tab, ((long)i << ASHIFT) + ABASE);
    }
    static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
                                        Node<K,V> c, Node<K,V> v) {
        return U.compareAndSetObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
    }
    static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
        U.putObjectRelease(tab, ((long)i << ASHIFT) + ABASE, v);
    }
复制代码

//计算索引的第一步，传入键值的hash值
    int hash = spread(key.hashCode());
    int binCount = 0; //保存当前节点的长度
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh; K fk; V fv;
        if (tab == null || (n = tab.length) == 0)
            tab = initTable(); //初始化Hash表
        ...
    }
复制代码

static final int spread(int h) {
        return (h ^ (h >>> 16)) & HASH_BITS; 
    }
复制代码

else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
              //利用CAS操作将元素插入到Hash表中
                if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value)))
                    break;  // no lock when adding to empty bin(插入null的节点，无需加锁)
            }
复制代码

else if ((fh = f.hash) == MOVED) //f.hash == -1 
        //hash为-1 说明是一个forwarding nodes节点，表明正在扩容
        tab = helpTransfer(tab, f);
复制代码

//当前节点加锁
 synchronized (f) {
 //判断下有没有线程对数组进行了修改
 if (tabAt(tab, i) == f) {
       //如果hash值是大于等于0的说明是链表
        if (fh >= 0) {
              binCount = 1;
              for (Node<K,V> e = f;; ++binCount) {
                    K ek;
                   //插入的元素键值的hash值有节点中元素的hash值相同，替换当前元素的值
                      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);
                            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;
                        }
                    }
                    else if (f instanceof ReservationNode)
                        throw new IllegalStateException("Recursive update");
                }
            }  
复制代码

if (binCount != 0) {
              //如果节点长度大于8,转化为树
              if (binCount >= TREEIFY_THRESHOLD)
                   treeifyBin(tab, i);
              if (oldVal != null)
                   return oldVal; 
               break;
         }
复制代码

addCount(1L, binCount);
复制代码

/**  
 * Hash表的初始化和调整大小的控制标志。为负数，Hash表正在初始化或者扩容;  
 * (-1表示正在初始化,-N表示有N-1个线程在进行扩容)  
 * 否则，当表为null时，保存创建时使用的初始化大小或者默认0;  
 * 初始化以后保存下一个调整大小的尺寸。  
 */  
 private transient volatile int sizeCtl;  
     //第一次put，初始化数组  
     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  
             //-1 表示正在初始化  
             else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {  
             ...  
         } finally {  
            sizeCtl = sc;  
         }  
            break;  
         }  
     }  
     return tab;  
 }
复制代码

else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {  
     //利用CAS操作将元素插入到Hash表中  
     if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value)))  
     break;  // no lock when adding to empty bin(插入null的节点，无需加锁)  
 }
复制代码

//当前节点加锁  
synchronized (f) {  
     //这里判断下有没有线程对数组进行了修改  
     if (tabAt(tab, i) == f) {  
     ......//do something  
 }
}
复制代码