​Java Map中那些巧妙的设计

HashMap hashMap = new HashMap(2);hashMap.put("1", 1);hashMap.put("2", 2);hashMap.put("3", 3);

hashCode(key1) = 0000 0000 0000 1111 0000 0000 0000 0010hashCode(key2) = 0000 0000 0000 0000 0000 0000 0000 0010

hashCode(key1) ^ (hashCode(key1) >>> 16)0000 0000 0000 1111 0000 0000 0000 1101
hashCode(key2) ^ (hashCode(key2) >>> 16)0000 0000 0000 0000 0000 0000 0000 0010

cap = 3n = 2n |= n >>> 1       010  | 001 = 011   n = 3n |= n >>> 2       011  | 000 = 011   n = 3n |= n >>> 4       011  | 000 = 011   n = 3….n = n + 1 = 4

cap = 5n = 4n |= n >>> 1    0100 | 0010 = 0110  n = 6n |= n >>> 2    0110 | 0001 = 0111  n = 7….n = n + 1 = 8

0100 10100111 11111000 0000

i >>> 16  0000 0000 0000 0000 0000 0000 0000 0100   不为0
i >>> 24  0000 0000 0000 0000 0000 0000 0000 0000   等于0

i = 0000 0100 0000 0000 0000 0000 0000 0000

i = 0100 0000 0000 0000 0000 0000 0000 0000

i >>> 30  0000 0000 0000 0000 0000 0000 0000 0001   不为0i >>> 31  0000 0000 0000 0000 0000 0000 0000 0000   等于0

private final void fullAddCount(long x, boolean wasUncontended) {        int h;// 初始化probeif ((h = ThreadLocalRandom.getProbe()) == 0) {            ThreadLocalRandom.localInit();      // force initialization            h = ThreadLocalRandom.getProbe();            wasUncontended = true;        }// 用来控制扩容操作        boolean collide = false;                // True if last slot nonemptyfor (;;) {            CounterCell[] as; CounterCell a; int n; long v;// 【A】counterCells已经初始化完毕if ((as = counterCells) != null && (n = as.length) > 0) {// 【a1】对应位置的CounterCell未创建if ((a = as[(n - 1) & h]) == null) {// cellsBusy其实是一个锁，cellsBusy=0时表示无冲突if (cellsBusy == 0) {            // Try to attach new Cell// 创建新的CounterCell                        CounterCell r = new CounterCell(x); // Optimistic create// Double Check，加锁（通过CAS将cellsBusy设置1）if (cellsBusy == 0 &&                            U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {                            boolean created = false;try {               // Recheck under lock                                CounterCell[] rs; int m, j;// Double Checkif ((rs = counterCells) != null &&                                    (m = rs.length) > 0 &&                                    rs[j = (m - 1) & h] == null) {// 将新创建的CounterCell放入counterCells中                                    rs[j] = r;                                    created = true;                                }                            } finally {// 解锁，这里为什么不用CAS？因为当前流程中需要在获取锁的前提下进行，即串行执行，因此不存在并发更新问题，只需要正常更新即可                                cellsBusy = 0;                            }if (created)break;// 创建失败则重试continue;           // Slot is now non-empty                        }                    }// cellsBusy不为0，说明被其他线程争抢到了锁，还不能考虑扩容                    collide = false;                }//【a2】冲突检测else if (!wasUncontended)       // CAS already known to fail// 调用方addCount中CAS更新cell失败，有冲突，则继续尝试CAS                    wasUncontended = true;      // Continue after rehash
//【a3】对应位置的CounterCell不为空，直接CAS进行更新else if (U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))break;//【a4】容量限制else if (counterCells != as || n >= NCPU)// 说明counterCells容量的最大值为大于NCPU（实际机器CPU核心的数量）最小2的整数次幂。// 这里限制的意义在于，并发度是由CPU核心来决定，当counterCells容量与CPU核心数量相等时，理论上讲就算所有CPU核心都在同时运行不同的计数线程时，都不应该出现冲突，每个线程选择各自的cell进行处理即可。如果出现冲突，一定是哈希值的问题，因此采取的措施是重新计算哈希值（h = ThreadLocalRandom.advanceProbe(h)），而不是通过扩容来解决
// 当n大于NCPU时后面的分支就不会走到了                    collide = false;            // At max size or stale// 【a5】更新扩容标志位else if (!collide)// 说明映射到cell位置不为空，并且尝试进行CAS更新时失败了，则说明有竞争，将collide设置为true，下次迭代时执行后面的扩容操作，降低竞争度// 有竞争时，执行rehash+扩容，当容量大于CPU核心时则停止扩容只进行rehash                    collide = true;// 【a6】加锁扩容else if (cellsBusy == 0 &&                         U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {// 加锁扩容try {if (counterCells == as) {// Expand table unless stale// 扩容1倍                            CounterCell[] rs = new CounterCell[n << 1];for (int i = 0; i < n; ++i)                                rs[i] = as[i];                            counterCells = rs;                        }                    } finally {                        cellsBusy = 0;                    }                    collide = false;continue;                   // Retry with expanded table                }//【a7】更换哈希值                h = ThreadLocalRandom.advanceProbe(h);            }// 【B】counterCells未初始化完成，且无冲突，则加锁初始化counterCellselse if (cellsBusy == 0 && counterCells == as &&                     U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {                boolean init = false;try {                           // Initialize tableif (counterCells == as) {                        CounterCell[] rs = new CounterCell[2];                        rs[h & 1] = new CounterCell(x);                        counterCells = rs;init = true;                    }                } finally {                    cellsBusy = 0;                }if (init)break;            }// 【C】counterCells未初始化完成，且有冲突，则CAS更新baseCountelse if (U.compareAndSwapLong(this, BASECOUNT, v = baseCount, v + x))break;                          // Fall back on using base        }