1、根本变量
// Unsafe mechanics//Unsafe类是用来做cas操作的，都是native办法，代码由C++实现，上面的变量示意对应变量的偏移//例如：public final native boolean compareAndSwapInt(Object o, long offset, int expected, int x);// 示意对象o偏移地位offset的变量如果和期望值expected相等，把变量值设置为xprivate static final sun.misc.Unsafe U;private static final long SIZECTL;private static final long TRANSFERINDEX;private static final long BASECOUNT;private static final long CELLSBUSY;private static final long CELLVALUE;private static final long ABASE;private static final int ASHIFT;1、table初始化
1、table会提早到第一次put时初始化，同过应用循环+CAS的套路，能够保障一次只有一个线程会初始化table。
2、在table为空的时候如果sizeCtl小于0，则阐明曾经有线程开始初始化了，其它线程通过Thread.yield()让出CPU工夫片，期待table非空即可。
3、否则应用CAS将sizeCtl的值换为-1，置换胜利则初始化table。
4、留神table的大小为sizeCtl，初始化后将sizeCtl的值设为n - (n >>> 2)即0.75n，这个值用来确定是否须要为table扩容。
//Initializes table, using the size recorded in sizeCtl.private final Node<K,V>[] initTable() { Node<K,V>[] tab; int sc; while ((tab = table) == null || tab.length == 0) { //判断是否曾经有线程在初始化，如果有则让出CPU，之后持续自旋判断 if ((sc = sizeCtl) < 0) Thread.yield(); // lost initialization race; just spin //cas操作设置sizeCtl的值 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") //初始化table Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n]; table = tab = nt; sc = n - (n >>> 2);//设置sizeCtl=0.75n } } finally { sizeCtl = sc; } break; } } return tab;}2、put操作（putVal办法）
1、首先计算key的hash值
2、判断table是否为空，如果是就初始化
3、依据hash值取余确定桶的地位，并判断桶是否为空，如果是空，通过cas操作设置进去
4、如果桶的第一个节点非空，并且hash=MOVED，阐明有线程正在进行扩容，调用helpTransfer帮忙扩容
5、对桶加锁并判断节点是链表还是树，依据不同状况插入节点
6、判断是否达到链表转树的阈值
7、统计节点数
final V putVal(K key, V value, boolean onlyIfAbsent) { if (key == null || value == null) throw new NullPointerException(); //1、首先计算key的hash值 int hash = spread(key.hashCode()); int binCount = 0; for (Node<K,V>[] tab = table;;) { Node<K,V> f; int n, i, fh; //2、判断table是否为空，如果是就初始化 if (tab == null || (n = tab.length) == 0) tab = initTable(); //3、依据hash值取余确定桶的地位，并判断桶是否为空，如果是空 //通过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 } //4、如果桶的第一个节点非空，并且hash=MOVED，阐明有线程正在进行扩容， //调用helpTransfer帮忙扩容 else if ((fh = f.hash) == MOVED) tab = helpTransfer(tab, f); else { V oldVal = null; //5、对桶加锁并判断节点是链表还是树，依据不同状况插入节点 synchronized (f) { if (tabAt(tab, i) == f) {//保障多线程环境下的安全性，再一次查看 if (fh >= 0) {//hash值大于0，阐明是一个链表 binCount = 1;//记录链表的元素个数 for (Node<K,V> e = f;; ++binCount) { K ek; //判断key是否已在链表中，如果是间接替换value if (e.hash == hash && ((ek = e.key) == key || (ek != null && key.equals(ek)))) { oldVal = e.val; if (!onlyIfAbsent) e.val = value; break; } //否则阐明是一个新Key，插入表尾 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) { //6、判断是否达到链表转树的阈值 if (binCount >= TREEIFY_THRESHOLD) treeifyBin(tab, i); if (oldVal != null) return oldVal; break; } } } //7、统计节点数 addCount(1L, binCount); return null;}3、链表转树
1、判断链表节点是否小于64，如果是优先应用扩容
2、对桶加锁
3、顺次把链表节点汇合转成树结点汇合
4、把树结点汇合转成红黑树，这颗红黑树是链表和树结构的联合，它同样通过next援用串成了一个链表
private final void treeifyBin(Node<K,V>[] tab, int index) {//将tab[index]链表转树 Node<K,V> b; int n, sc; if (tab != null) { //1、判断链表节点是否小于64，如果是优先应用扩容 if ((n = tab.length) < MIN_TREEIFY_CAPACITY) tryPresize(n << 1); //为了多线程环境下的安全性，再次判断该桶是否为空，hash>0示意是链表 else if ((b = tabAt(tab, index)) != null && b.hash >= 0) { synchronized (b) {//2、对桶加锁 if (tabAt(tab, index) == b) {//加锁后再次判断 TreeNode<K,V> hd = null, tl = null; //3、顺次把链表节点汇合转成树结点 for (Node<K,V> e = b; e != null; e = e.next) { TreeNode<K,V> p = new TreeNode<K,V>(e.hash, e.key, e.val, null, null); if ((p.prev = tl) == null) hd = p; else tl.next = p; tl = p; } //4、把树结点汇合转成红黑树 setTabAt(tab, index, new TreeBin<K,V>(hd)); } } } }}4、扩容
1、因为扩容容许并发操作，首先通过CPU数量，计算容许每个线程能解决的桶的数量stride，起码每个线程解决16个
2、申请nextTable数组
3、把nextTab设置为ForwardingNode,示意正在进行扩容操作
4、每个线程进来的线程去获取本人能解决区域，每个线程通过cas操作设置transferIndex变量，设置胜利则线程取得table中（transferIndex, transferIndex-strade)这一段的解决权限
相似下图这样的，反向调配的，先来的线程从前面获取桶段
5、循环顺次解决每一个桶：
5.1 如果以后桶首节点是链表，把链表节点重新分配到两个桶，一部分在原地位i，一分部在i+n地位
5.2 如果是红黑树，这里有点意思，同样是通过一个for像链表一样遍历，分成两局部，一个将放在i地位，一个将放在i+n地位。
那么问题来了，这里既然是树，为什么能够像链表一样操作呢？
这里是作者设计很奇妙的中央，拜服Doug lea大神，树的遍历十分不不便，而链表遍历很不便。TreeNode自身继承了Node，有一个next指针。当把链表节点数超过8，转成红黑树的时候，next指针不变，链表构造没有毁坏，所以这颗树自身是一个树和链表的结合体，既能够当链表用又能够当树用（这个设计有点相似LinkedHashMap，即时一个hashMap又是一个链表）。
相似下图这样的构造
这里被分成两个局部后，再依据这两个局部是否达到了树转列表的阈UNTREEIFY_THRESHOLD=6确定是转成链表还是组织成红黑树。private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) { int n = tab.length, stride; //取CPU的数量，确定每个线程迁徙的Node的数量，确保不会少于MIN_TRANSFER_STRIDE=16个 if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE) stride = MIN_TRANSFER_STRIDE; // subdivide range //申请数组nextTable if (nextTab == null) { // initiating try { @SuppressWarnings("unchecked") Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1]; nextTab = nt; } catch (Throwable ex) { // try to cope with OOME sizeCtl = Integer.MAX_VALUE; return; } nextTable = nextTab; transferIndex = n; } int nextn = nextTab.length; //把nextTab设置为ForwardingNode,示意正在进行扩容操作 ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab); boolean advance = true; boolean finishing = false; // to ensure sweep before committing nextTab for (int i = 0, bound = 0;;) { Node<K,V> f; int fh; while (advance) { int nextIndex, nextBound; if (--i >= bound || finishing) advance = false; else if ((nextIndex = transferIndex) <= 0) { i = -1; advance = false; } /** nextIndex从n开始 这里每个线程进来的时候通过cas操作设置transferIndex变量， 如果胜利示意该线程解决nextIndex-stride这一段桶的迁徙 即 i=[nextIndex-1, nextIndex-stride] 这一段桶 */ //不相等，阐明不到最初一个线程，间接退出transfer办法 else if (U.compareAndSwapInt (this, TRANSFERINDEX, nextIndex, nextBound = (nextIndex > stride ? nextIndex - stride : 0))) { bound = nextBound; i = nextIndex - 1; advance = false; } } //判断是否解决实现所有的桶 if (i < 0 || i >= n || i + n >= nextn) { int sc; if (finishing) { nextTable = null; table = nextTab; sizeCtl = (n << 1) - (n >>> 1); return; } if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) { if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT) return; finishing = advance = true; i = n; // recheck before commit } } else if ((f = tabAt(tab, i)) == null) advance = casTabAt(tab, i, null, fwd); else if ((fh = f.hash) == MOVED) advance = true; // already processed else { synchronized (f) { if (tabAt(tab, i) == f) { Node<K,V> ln, hn; //hash>0示意链表,链表节点重新分配到两个桶，一部分在原地位i，一分部在i+n地位 if (fh >= 0) { int runBit = fh & n; Node<K,V> lastRun = f; //找到低位和高位链表的各自的尾节点，配合前面用头插法 for (Node<K,V> p = f.next; p != null; p = p.next) { int b = p.hash & n; if (b != runBit) { runBit = b; lastRun = p; } } if (runBit == 0) { ln = lastRun; hn = null; } else { hn = lastRun; ln = null; } //循环将链表拆分成两个链表，头插法 for (Node<K,V> p = f; p != lastRun; p = p.next) { int ph = p.hash; K pk = p.key; V pv = p.val; if ((ph & n) == 0) ln = new Node<K,V>(ph, pk, pv, ln); else hn = new Node<K,V>(ph, pk, pv, hn); } //将拆分后的列表通过cas操作设置为对应的桶中 setTabAt(nextTab, i, ln); setTabAt(nextTab, i + n, hn); setTabAt(tab, i, fwd); advance = true; } //该桶存储的是红黑树 else if (f instanceof TreeBin) { TreeBin<K,V> t = (TreeBin<K,V>)f; TreeNode<K,V> lo = null, loTail = null; TreeNode<K,V> hi = null, hiTail = null; int lc = 0, hc = 0; //这里的代码比拟有意思 //因为这里的红黑树是一个树和链表的结合体，TreeNode同时也是一个Node //所以这里能够像链表一样遍历，应用这种构造是为了不便遍历 //顺次取出树的节点，依据节点hash的后果分到位置和高位链表 //前面把链表转成树，同时会放弃链表的构造 for (Node<K,V> e = t.first; e != null; e = e.next) { int h = e.hash; TreeNode<K,V> p = new TreeNode<K,V> (h, e.key, e.val, null, null); if ((h & n) == 0) { if ((p.prev = loTail) == null) lo = p; else loTail.next = p; loTail = p; ++lc; } else { if ((p.prev = hiTail) == null) hi = p; else hiTail.next = p; hiTail = p; ++hc; } } //把树拆分成了低位（放在地位i）和高位(地位i+n)链表，这里判断两个链表长度是否达到转成树的阈值 ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) : (hc != 0) ? new TreeBin<K,V>(lo) : t; hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) : (lc != 0) ? new TreeBin<K,V>(hi) : t; //拆分后的构造设置到相应的桶中 setTabAt(nextTab, i, ln); setTabAt(nextTab, i + n, hn); setTabAt(tab, i, fwd); advance = true; } } } } }}
5、统计元素数量
1、简略通过CouterCell数组的和，因为可能有其余线程在进行增删操作，这个数据并不是准确的。
final long sumCount() { CounterCell[] as = counterCells; CounterCell a; long sum = baseCount; if (as != null) { for (int i = 0; i < as.length; ++i) { if ((a = as[i]) != null) sum += a.value; } } return sum;}