一、计算初始容量
1）源代码
tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1) //计算c最近的2的N次方的值，作为初始容量 private static final int tableSizeFor(int c) { int n = c - 1; n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; }
2） 对与右移的知识请到我的另一篇文章中查看
3）或 运算符，只要有一个为1，则结果为1，否则为0
4）假设传进来的是25，二进制为011001
我们最终需要获得最大的二进制为 100000，作为集合的初始值 如何计算得到这个最大的二进制呢？ 答：终极思想用移位得出011111 然后 +1 如何得出 011111呢？思想：将最高位1以后的数字通过移位操作全都变成1， 将最高位1向右移动4次，每一次得到N位1（通过与原来数据或操作）保留下来 步骤： 1 取原始数据 011001 最高位的1 ，然后右移一位结果：001100 2 001100或操作 011001 = 011101 3 让数据011101 ，右移2位得到，然后重复1、2操作得到011111 4 最后的结果011111，加上1得到1000000 这个步骤基本上和上面的源代码相同，只不过这里只是执行了2个步骤，源代码中执行了4个步骤 为什么是4个步骤呢？ 因为正数二进制是32位，而我们想31位全都变成1，那必须执行4个步骤，然后最后+1
二、数据放入结合
/** Implementation for put and putIfAbsent */ final V putVal(K key, V value, boolean onlyIfAbsent) { //参数校验 if (key == null || value == null) throw new NullPointerException(); // 计算key对应的hash值，这个值会决定放入的数据对应，数组的那一个位置 int hash = spread(key.hashCode()); int binCount = 0; //赋值，并且无条件循环，直到满足一定条件才会退出 for (Node<K,V>[] tab = table;;) { Node<K,V> f; int n, i, fh; //判断数组是否已经初始化，如果没有则初始化数据结构 if (tab == null || (n = tab.length) == 0) //初始化数据结构 数组见下面的 三 tab = initTable(); // (n - 1) & hash 这个相当于数组的hash下标， 获取key对应数组下标位置是否有数据 else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { //没有数据，则使用创建一个Node对象，然后case将数据赋值到数组对应位置 if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null))) break; // no lock when adding to empty bin } else if ((fh = f.hash) == MOVED) tab = helpTransfer(tab, f); else { V oldVal = null; //锁住 key数组对应下标的第一个对象 synchronized (f) { //双重判断，以防f中途发生变化 if (tabAt(tab, i) == f) { //f 这个对象的hash值 大于0 ，当连表迁移的时候这个值会发生变化 if (fh >= 0) { binCount = 1; //遍历 查找到的这个连表 for (Node<K,V> e = f;; ++binCount) { K ek; //如果连表中一个对象的 key和hash与传进来的key和hash一样 if (e.hash == hash && ((ek = e.key) == key || (ek != null && key.equals(ek)))) { oldVal = e.val; if (!onlyIfAbsent)//如果 参数覆盖为false //用value覆盖原来对象的val 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 addCount(1L, binCount); return null; }
三、初始化数据结构
//方法可能会有多个线程进入 private final Node<K,V>[] initTable() { Node<K,V>[] tab; int sc; //线程进来以后，如果数组没有初始化则一直循环 while ((tab = table) == null || tab.length == 0) { //sizeCtl=-1<0 则集合正在初始化，当前线程让出cpu执行权限 if ((sc = sizeCtl) < 0) Thread.yield(); // lost initialization race; just spin //cas操作，只有一个线程可以设置sizeCtl值为-1，进入的线程会对数组进行初始化 else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) { try { //二次判断，防止初始化的线程初始化完成以后，改变 sizeCtl 数值以后，其他线程进入到这个方法再次进行初始化 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变量，这个table使用volatile修饰的，一旦赋值以后其他线程不会进入到这个while循环里面了 table = tab = nt; sc = n - (n >>> 2); } } finally { //恢复sizeCtl这个变量 sizeCtl = sc; } break; } } return tab; }
四、总数+1
//主线：计数需要baseCount+1，当有线程竞争的时候则计数放到counterCells里面 private final void addCount(long x, int check) { CounterCell[] as; long b, s; // 第一个线程和与第一个线程同时进到这个位置的线程 counterCells才能=null，后面的线程 (as = counterCells) != null一直为true // 即后面的线程才会执行 这段代码：!U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x) if ((as = counterCells) != null || //当counterCells已经被初始化的时候，每次过来的线程没有竞争的情况执行这个语句 将baseCount直接+1，如果+1执行失败，则执行内部代码块 !U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) { CounterCell a; long v; int m; boolean uncontended = true; // if (as == null || (m = as.length - 1) < 0 || //判断counterCells 这个变量为空 (a = as[ThreadLocalRandom.getProbe() & m]) == null || //判断 需要写入数值的counterCells数组对应的位置为空 !(uncontended = U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) { //将 counterCells数组对应的位置的CounterCell值+1 // 初始化counterCells，初始化counterCells对应下面的counterCell对象，或者在counterCells 对应节点数值+x操作 fullAddCount(x, uncontended); return; } if (check <= 1) return; //计算总数 counterCells和baseCount 数据相加 获取总数 s = sumCount(); } if (check >= 0) { Node<K,V>[] tab, nt; int n, sc; //计算得到的数据总数大于初始容量sizeCtl，并且table不为空，需要扩容了 while (s >= (long)(sc = sizeCtl) && (tab = table) != null && (n = tab.length) < MAXIMUM_CAPACITY) { int rs = resizeStamp(n); if (sc < 0) { //如果正在扩容 if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 || sc == rs + MAX_RESIZERS || (nt = nextTable) == null || transferIndex <= 0) break; if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) transfer(tab, nt); } //获取锁 else if (U.compareAndSwapInt(this, SIZECTL, sc, (rs << RESIZE_STAMP_SHIFT) + 2)) //扩容 transfer(tab, null); s = sumCount(); } } }
五、初始化counterCells，初始化counterCells对应下面的counterCell对象，或者在counterCells 对应节点数值+x操作
private final void fullAddCount(long x, boolean wasUncontended) { int h; if ((h = ThreadLocalRandom.getProbe()) == 0) { ThreadLocalRandom.localInit(); // force initialization h = ThreadLocalRandom.getProbe(); wasUncontended = true; } boolean collide = false; // True if last slot nonempty //循环配合cas操作 for (;;) { CounterCell[] as; CounterCell a; int n; long v; //判断counterCells 不为空，对数组进行数值+操作 if ((as = counterCells) != null && (n = as.length) > 0) { // 需要操作的counterCells的下标对象为空 if ((a = as[(n - 1) & h]) == null) { if (cellsBusy == 0) { // Try to attach new Cell //创建一个CounterCell CounterCell r = new CounterCell(x); // Optimistic create if (cellsBusy == 0 && U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) { //cellsBusy标识位设置为1，进行加锁 boolean created = false; try { // Recheck under lock CounterCell[] rs; int m, j; if ((rs = counterCells) != null && (m = rs.length) > 0 && rs[j = (m - 1) & h] == null) { //创建好的 CounterCell放到数组对应的位置 rs[j] = r; created = true; } } finally { cellsBusy = 0; } if (created) break; continue; // Slot is now non-empty } } collide = false; } else if (!wasUncontended) // CAS already known to fail wasUncontended = true; // Continue after rehash //对应的 CounterCell对象数据+x，如果成功则跳出循环 else if (U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x)) break; // 如果数组CounterCell[]的长度已经大于计算机cpu的核大小，则重新循环不会执行下面扩容 else if (counterCells != as || n >= NCPU) collide = false; // At max size or stale else if (!collide) //就是增加一次循环，增加数值+x的几率，如果失败则会执行下面的扩容 collide = true; else if (cellsBusy == 0 && U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) { try { //扩容CounterCell[]数组，以增加cpu的使用效率 if (counterCells == as) {// Expand table unless stale 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 } h = ThreadLocalRandom.advanceProbe(h); } //判断 锁标识位没有被占用，counterCells==null else if (cellsBusy == 0 && counterCells == as && U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {//加锁 boolean init = false; try { // Initialize table if (counterCells == as) { //初始化counterCells CounterCell[] rs = new CounterCell[2]; //创建一个CounterCell放入数组 rs[h & 1] = new CounterCell(x); counterCells = rs; init = true; } } finally { cellsBusy = 0; } //防止其他线程进来直接break了 if (init) break; } else if (U.compareAndSwapLong(this, BASECOUNT, v = baseCount, v + x)) break; // Fall back on using base } }
六、扩容
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) { int n = tab.length, stride; //计算最小扩容大小 if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE) stride = MIN_TRANSFER_STRIDE; // subdivide range if (nextTab == null) { // initiating try { @SuppressWarnings("unchecked") Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];//创建一个数组，容量为原来的2倍 nextTab = nt; } catch (Throwable ex) { // try to cope with OOME sizeCtl = Integer.MAX_VALUE; return; } //扩容后的数组 nextTable = nextTab; //需要转移的索引数量 transferIndex = n; } int nextn = nextTab.length; 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; //从最大索引位置计算，如果下一个迁移的索引已经为0，则退出循环 else if ((nextIndex = transferIndex) <= 0) { i = -1; advance = false; } 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; 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); } 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; 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; } } 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; } } } } } }