一 特性

  • 在jdk7之中是使用分段锁来保证的（ReentrantLock + Segment + HashEntry） 将HashMap分成多个片段segment，每个段分配一把锁，在8之中使用CAS+Snchronized+Node+红黑树保证的，锁的粒度是Node 首节点
  • jdk1.7的结构
    • image.png
  • jdk1.8的结构
    • image.png


  • 二 属性

    ```java private static final int MAXIMUM_CAPACITY = 1 << 30;

    /* 默认大小 / private static final int DEFAULT_CAPACITY = 16;

// 最大数组长度-转数组使用 static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

  1. /** 最多的并行度
  2.  */
  3. private static final int DEFAULT_CONCURRENCY_LEVEL = 16;
  5. /**负载因子
  6.  */
  7. private static final float LOAD_FACTOR = 0.75f;
  9. /** 元素超过这个值会转换为红黑树
  10.  */
  11. static final int TREEIFY_THRESHOLD = 8;
  13.  /** 总元素最小的转换成树的条件 不满足这个只会扩容
  14.  */
  15. static final int MIN_TREEIFY_CAPACITY = 64;

// 扩容操作中，单个线程的最小步进 // 数据迁移通过分段迁移，由多线程协调执行，最小段数量为16，则如果长度为16，由一个线程进行扩容 private static final int MIN_TRANSFER_STRIDE = 16;

  1. // 扩容操作使用
  2. private static int RESIZE_STAMP_BITS = 16;
  4. //最大扩容线程数量

private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1;

  1. // 扩容操作使用，进行sizeCtl高低位移动，进行扩容线程数判断
  2. private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;

/* 实际存储的数组 / transient volatile Node[] table;

  1. /**
  2.  * 扩容的时候使用的下一个数组
  3.  */
  4. private transient volatile Node<K,V>[] nextTable;
  6. /** 统计数量
  7.  * races. Updated via CAS.
  8.  */
  9. private transient volatile long baseCount;
  11. // 用于和负数hash值进行 & 运算，将其转化为正数（绝对值不相等）
  12. static final int HASH_BITS = 0x7fffffff;

// ForwardingNode的hash值，ForwardingNode是一种临时节点，在扩进行中才会出现，并且它不存储实际的数据，ForwardingNode继承自Node，默认hash初始化为-1 static final int MOVED = -1;

// 红黑树的HASH值 static final int TREEBIN = -2;

// ReservationNode的hash值，ReservationNode是一个保留节点，就是个占位符 static final int RESERVED = -3;

/*

  • 非常重要的一个属性，源码中的英文翻译，直译过来是下面的四行文字的意思
  • sizeCtl = -1，表示有线程正在进行真正的初始化操作
  • sizeCtl = -(1 + nThreads)，表示有nThreads个线程正在进行扩容操作
  • sizeCtl > 0，表示接下来的真正的初始化操作中使用的容量，或者初始化/扩容完成后的阈值

  • sizeCtl = 0，默认值，此时在真正的初始化操作中使用默认容量 */ private transient volatile int sizeCtl;

    // 扩容任务的起始下标 private transient volatile int transferIndex;

    // CAS自旋锁标志位，用于初始化，或者counterCells扩容时使用 private transient volatile int cellsBusy;

    // 分段计数，记录 private transient volatile CounterCell[] counterCells;

  1. <a name="W7P87"></a>
  2. # 三 重要方法
  4. - tabAt(Node<K,V>[] tab, int i)
  5.    - 获取i索引处对象
  6. - casTabAt(Node<K,V>[] tab, int i,Node<K,V> c, Node<K,V> v)
  7.    - 把索引 i 处为C 的对象换成V  cas方式比较更新
  8. - setTabAt(Node<K,V>[] tab, int i, Node<K,V> v)
  9.    - 把 i 索引处对象设置为V
  10. - tableSizeFor
  11.    - 给一个传入的数，返回大于给定数字的最小的2的整数次方的数字
  12. <a name="S9VT1"></a>
  13. # 四 添加
  14. ```java
  15.     final V putVal(K key, V value, boolean onlyIfAbsent) {
  16.         if (key == null || value == null) throw new NullPointerException();
  17.         //将hash值进行扰乱   (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16)  这个是hashMap的
  18.         //                                    (h ^ (h >>> 16)) & HASH_BITS  
  19.         int hash = spread(key.hashCode());
  20.         int binCount = 0;
  21.         for (Node<K,V>[] tab = table;;) {
  22.             Node<K,V> f; int n, i, fh;
  23.             //这个是初始化阶段
  24.             if (tab == null || (n = tab.length) == 0)
  25.                 //还未初始化则先开始初始化
  26.                 tab = initTable();
  28.             //unSafe直接读取内存 如果指定位置是null 则直接插入
  29.             else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
  30.                 if (casTabAt(tab, i, null,
  31.                              new Node<K,V>(hash, key, value, null)))
  32.                     break;                   // no lock when adding to empty bin
  33.             }
  34.             //扩容阶段
  35.             else if ((fh = f.hash) == MOVED)
  36.                 tab = helpTransfer(tab, f);
  37.             else {
  38.                 V oldVal = null;
  39.                 //锁住发生hash冲突的第一个节点
  40.                 synchronized (f) {
  41.                     //加锁之后再重新检查下 避免其他线程对f进行了更改
  42.                     if (tabAt(tab, i) == f) {
  43.                         // 判断头结点的hash值 
  44.                         if (fh >= 0) {
  45.                             binCount = 1;
  46.                             //循环链表操作 这里binCount是下边使用进行树化使用
  47.                             for (Node<K,V> e = f;; ++binCount) {
  48.                                 K ek;
  49.                                 if (e.hash == hash &&
  50.                                     ((ek = e.key) == key ||
  51.                                      (ek != null && key.equals(ek)))) {
  52.                                     oldVal = e.val;
  53.                                     if (!onlyIfAbsent)
  54.                                         e.val = value;
  55.                                     break;
  56.                                 }
  57.                                 Node<K,V> pred = e;
  58.                                 //循环链表
  59.                                 if ((e = e.next) == null) {
  60.                                     pred.next = new Node<K,V>(hash, key,
  61.                                                               value, null);
  62.                                     break;
  63.                                 }
  64.                             }
  65.                         }
  66.                         //红黑树插入
  67.                         else if (f instanceof TreeBin) {
  68.                             Node<K,V> p;
  69.                             binCount = 2;
  70.                             if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
  71.                                                            value)) != null) {
  72.                                 oldVal = p.val;
  73.                                 if (!onlyIfAbsent)
  74.                                     p.val = value;
  75.                             }
  76.                         }
  77.                     }
  78.                 }
  79.                 if (binCount != 0) {
  80.                     if (binCount >= TREEIFY_THRESHOLD)
  81.                         treeifyBin(tab, i);
  82.                     if (oldVal != null)
  83.                         return oldVal;
  84.                     break;
  85.                 }
  86.             }
  87.         }
  88.         addCount(1L, binCount);
  89.         return null;
  90.     }
  92. // 初始化数组
  93.     private final Node<K,V>[] initTable() {
  94.         Node<K,V>[] tab; int sc;
  95.         while ((tab = table) == null || tab.length == 0) {
  96.             if ((sc = sizeCtl) < 0)
  97.                 Thread.yield(); // lost initialization race; just spin
  98.             //java的cas更新方法 读取传入对象在内存中偏移量为SIZECTL  的值与 sc作比较，相等则将-1赋值进入 表示正在初始化 不相等则返回false
  99.             // SIZECTL 这个是静态实例已经被初始化为  U.objectFieldOffset(k.getDeclaredField("sizeCtl"));
  100.             else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
  101.                 try {
  102.                     if ((tab = table) == null || tab.length == 0) {
  103.                         int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
  104.                         @SuppressWarnings("unchecked")
  105.                         Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
  106.                         table = tab = nt;
  107.                         // 16 - 4=12
  108.                         sc = n - (n >>> 2);
  109.                     }
  110.                 } finally {
  111.                     sizeCtl = sc;
  112.                 }
  113.                 break;
  114.             }
  115.         }
  116.         return tab;
  117.     }
  120.     //作用是找到指定位置i的值 使用的是UnSafe直接操作的内存 找到对应位置的偏移量
  121.     static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
  122.         return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
  123.     }
  125.     //cas的方式更新进去 先比较在更新
  126.     static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
  127.                                         Node<K,V> c, Node<K,V> v) {
  128.         return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
  129.     }
  132.     //当发生hash冲突 check传入的是链的大小
  133.    private final void addCount(long x, int check) {
  134.         CounterCell[] as; long b, s;
  135.         if ((as = counterCells) != null ||
  136.             //注意这里会把值累加到 baseCount上  也就是当发生并行访问冲突的时候才会用到下边的代码
  137.             !U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
  138.             CounterCell a; long v; int m;
  139.             boolean uncontended = true;
  140.             if (as == null || (m = as.length - 1) < 0 ||
  141.                 (a = as[ThreadLocalRandom.getProbe() & m]) == null ||
  142.                 !(uncontended =
  143.                   U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
  144.                 fullAddCount(x, uncontended);
  145.                 return;
  146.             }
  147.             if (check <= 1)
  148.                 return;
  149.             s = sumCount();
  150.         }
  151.         if (check >= 0) {
  152.             Node<K,V>[] tab, nt; int n, sc;
  153.             while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
  154.                    (n = tab.length) < MAXIMUM_CAPACITY) {
  155.                 int rs = resizeStamp(n);
  156.                 if (sc < 0) {
  157.                     if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
  158.                         sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
  159.                         transferIndex <= 0)
  160.                         break;
  161.                     if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
  162.                         transfer(tab, nt);
  163.                 }
  164.                 else if (U.compareAndSwapInt(this, SIZECTL, sc,
  165.                                              (rs << RESIZE_STAMP_SHIFT) + 2))
  166.                     transfer(tab, null);
  167.                 s = sumCount();
  168.             }
  169.         }
  170.     }
  172. // 树化的过程中同样是锁头结点
  173.     private final void treeifyBin(Node<K,V>[] tab, int index) {
  174.         Node<K,V> b; int n, sc;
  175.         if (tab != null) {
  176.             if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
  177.                 tryPresize(n << 1);
  178.             else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
  179.                 synchronized (b) {
  180.                     if (tabAt(tab, index) == b) {
  181.                         TreeNode<K,V> hd = null, tl = null;
  182.                         for (Node<K,V> e = b; e != null; e = e.next) {
  183.                             TreeNode<K,V> p =
  184.                                 new TreeNode<K,V>(e.hash, e.key, e.val,
  185.                                                   null, null);
  186.                             if ((p.prev = tl) == null)
  187.                                 hd = p;
  188.                             else
  189.                                 tl.next = p;
  190.                             tl = p;
  191.                         }
  192.                         setTabAt(tab, index, new TreeBin<K,V>(hd));
  193.                     }
  194.                 }
  195.             }
  196.         }
  197.     }

  • initTable

    • 综上在经过第一次初始化之后，sizeCtl的值变为12

      五treeifyBin

      1. // 树化的过程中同样是锁头结点
      2. private final void treeifyBin(Node<K,V>[] tab, int index) {
      3.    Node<K,V> b; int n, sc;
      4.    if (tab != null) {
      5.        //必须大于 64才会进行树化 否则会进行扩容
      6.        if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
      7.            tryPresize(n << 1);
      8.        else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
      9.            //这里如果插入过程中发生了根节点的变动 这里是将根节点的值进行了改变，而不是对象 所以锁根节点并未失效
      10.            synchronized (b) {
      11.                if (tabAt(tab, index) == b) {
      12.                    TreeNode<K,V> hd = null, tl = null;
      13.                    for (Node<K,V> e = b; e != null; e = e.next) {
      14.                        TreeNode<K,V> p =
      15.                            new TreeNode<K,V>(e.hash, e.key, e.val,
      16.                                              null, null);
      17.                        if ((p.prev = tl) == null)
      18.                            hd = p;
      19.                        else
      20.                            tl.next = p;
      21.                        tl = p;
      22.                    }
      23.                    //红黑树插入 在构造函数之中
      24.                    setTabAt(tab, index, new TreeBin<K,V>(hd));
      25.                }
      26.            }
      27.        }
      28.    }
      29. }

      六 addCount

      ```java // 数量的统计
      private final void addCount(long x, int check) { CounterCell[] as; long b, s; //这里一旦发生过并发冲突之后就不会添加baseCount了 就会直接进入下边的流程 if ((as = counterCells) != null ||

      1.    //这里是并发的情况下可能会设置失败 会进入下边的流程
      2.    !U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
      3.    CounterCell a; long v; int m;
      4.    boolean uncontended = true;
      5.    if (as == null || (m = as.length - 1) < 0 ||
      6.        (a = as[ThreadLocalRandom.getProbe() & m]) == null ||
      7.        !(uncontended =
      8.          U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
      9.        fullAddCount(x, uncontended);
      10.        return;
      11.    }
      12.    if (check <= 1)
      13.        return;
      14.    s = sumCount();

      } if (check >= 0) {

      1.    Node<K,V>[] tab, nt; int n, sc;
      2.    //这里使用while循环主要是避免并发量高的时候连续进行扩容 所以是这样的
      3.    while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
      4.           (n = tab.length) < MAXIMUM_CAPACITY) {
      5.        int rs = resizeStamp(n);
      7.        //当出现并发的时候会进入这里 这里没看懂
      8.        if (sc < 0) {
      9.            if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
      10.                sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
      11.                transferIndex <= 0)
      12.                break;
      13.            if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
      14.                transfer(tab, nt);
      15.        }
      16.        else if (U.compareAndSwapInt(this, SIZECTL, sc,
      17.                                     (rs << RESIZE_STAMP_SHIFT) + 2))
      18.            transfer(tab, null);
      19.        s = sumCount();
      20.    }

      } }

  1. private final void fullAddCount(long x, boolean wasUncontended) {
  2.     int h;
  3.     //这里是获得当前线程的一个随机值
  4.     if ((h = ThreadLocalRandom.getProbe()) == 0) {
  5.         ThreadLocalRandom.localInit();      // force initialization
  6.         h = ThreadLocalRandom.getProbe();
  7.         wasUncontended = true;
  8.     }
  9.     boolean collide = false;                // True if last slot nonempty
  10.     for (;;) {
  11.         CounterCell[] as; CounterCell a; int n; long v;
  12.         if ((as = counterCells) != null && (n = as.length) > 0) {
  13.             //这里对应位置 CounterCell 的值为null 则新创建
  14.             if ((a = as[(n - 1) & h]) == null) {
  15.                 //这里使用 cellsBusy 锁避免并发问题 先判断能否访问，不能的话会回到for循环的开始继续执行
  16.                 if (cellsBusy == 0) {            // Try to attach new Cell
  17.                     CounterCell r = new CounterCell(x); // Optimistic create
  18.                     if (cellsBusy == 0 &&
  19.                         //锁住 自旋锁
  20.                         U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
  21.                         boolean created = false;
  22.                         try {               // Recheck under lock
  23.                             CounterCell[] rs; int m, j;
  24.                             if ((rs = counterCells) != null &&
  25.                                 (m = rs.length) > 0 &&
  26.                                 rs[j = (m - 1) & h] == null) {
  27.                                 //将值赋值进去
  28.                                 rs[j] = r;
  29.                                 created = true;
  30.                             }
  31.                         } finally {
  32.                             cellsBusy = 0;
  33.                         }
  34.                         if (created)
  35.                             break;
  36.                         continue;           // Slot is now non-empty
  37.                     }
  38.                 }
  39.                 collide = false;
  40.             }
  41.             //这里判断如果不进行累加 则直接在原来的CounterCell 上CAS的方式更新对应的值
  42.             else if (!wasUncontended)       // CAS already known to fail
  43.                 wasUncontended = true;      // Continue after rehash
  44.             else if (U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))
  45.                 break;
  46.             //下边的代码是如果当前 CounterCell超过NCPU数量 则会进行扩容 扩容为两倍
  47.             else if (counterCells != as || n >= NCPU)
  48.                 collide = false;            // At max size or stale
  49.             else if (!collide)
  50.                 collide = true;
  51.             else if (cellsBusy == 0 &&
  52.                      U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
  53.                 try {
  54.                     if (counterCells == as) {// Expand table unless stale
  55.                         //具体扩容操作并赋值进入
  56.                         CounterCell[] rs = new CounterCell[n << 1];
  57.                         for (int i = 0; i < n; ++i)
  58.                             rs[i] = as[i];
  59.                         counterCells = rs;
  60.                     }
  61.                 } finally {
  62.                     cellsBusy = 0;
  63.                 }
  64.                 collide = false;
  65.                 continue;                   // Retry with expanded table
  66.             }
  67.             h = ThreadLocalRandom.advanceProbe(h);
  68.         }
  69.         // 这里是初始化 counterCells的过程 默认长度是2  cellsBusy 是控制并行访问的
  70.         else if (cellsBusy == 0 && counterCells == as &&
  71.                  U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
  72.             boolean init = false;
  73.             try {                           // Initialize table
  74.                 if (counterCells == as) {
  75.                     CounterCell[] rs = new CounterCell[2];
  77.                     //这里会把数量存储到 CounterCell中
  78.                     rs[h & 1] = new CounterCell(x);
  79.                     counterCells = rs;
  80.                     init = true;
  81.                 }
  82.             } finally {
  83.                 cellsBusy = 0;
  84.             }
  85.             if (init)
  86.                 break;
  87.         }
  88.         else if (U.compareAndSwapLong(this, BASECOUNT, v = baseCount, v + x))
  89.             break;                          // Fall back on using base
  90.     }
  91. }
  1. 对应的结构如下所示<br />![image.png](https://cdn.nlark.com/yuque/0/2021/png/1253306/1633361972565-937a54bd-5107-46b7-b386-a4c2a96066ef.png#clientId=uaafdf15a-41f6-4&from=paste&height=201&id=u47f13058&margin=%5Bobject%20Object%5D&name=image.png&originHeight=201&originWidth=675&originalType=binary&ratio=1&size=11407&status=done&style=none&taskId=ubefd6d74-dacf-488d-8c0f-6cb6c83beee&width=675)
  2. <a name="QP9qS"></a>
  3. # 七 transfer
  4. ```java
  5.  private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
  6.         int n = tab.length, stride;
  7.          //这里相当于是计算cpu核心数 看最多几个线程同时进行扩容 这里假设计算的结果是2
  8.         if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
  9.             stride = MIN_TRANSFER_STRIDE; // subdivide range
  11.          // 这里是初始化操作 初始化下一个数组
  12.         if (nextTab == null) {            // initiating
  13.             try {
  14.                 @SuppressWarnings("unchecked")
  15.                 Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
  16.                 nextTab = nt;
  17.             } catch (Throwable ex) {      // try to cope with OOME
  18.                 sizeCtl = Integer.MAX_VALUE;
  19.                 return;
  20.             }
  21.             nextTable = nextTab;
  22.             transferIndex = n;
  23.         }
  25.         int nextn = nextTab.length;
  26.          //正在扩容的节点会被赋值 fwd
  27.         ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
  28.         boolean advance = true;
  29.         boolean finishing = false; // to ensure sweep before committing nextTab
  31.          //bound的作用相当于为每个线程分区，扩容是按照分区进行的   
  32.         for (int i = 0, bound = 0;;) {
  33.             Node<K,V> f; int fh;
  35.             //这里while循环的作用主要是找到当前线程可扩容的区域
  36.             while (advance) {
  37.                 int nextIndex, nextBound;
  38.                 if (--i >= bound || finishing)
  39.                     advance = false;
  40.                 else if ((nextIndex = transferIndex) <= 0) {
  41.                     i = -1;
  42.                     advance = false;
  43.                 }
  44.                 //当另一个线程也来找可扩容的区域的时候 区域的划分是使用  TRANSFERINDEX 来进行控制的
  45.                 else if (U.compareAndSwapInt(this, TRANSFERINDEX, nextIndex,nextBound = (nextIndex > stride ?nextIndex - stride : 0))) {
  46.                     bound = nextBound;
  47.                     i = nextIndex - 1;
  48.                     advance = false;
  49.                 }
  50.             }
  51.             //这里代表当前线程没有找到可扩容的区域 代表已经扩容完成
  52.             if (i < 0 || i >= n || i + n >= nextn) {
  53.                 int sc;
  54.                 if (finishing) {
  55.                     nextTable = null;
  56.                     table = nextTab;
  57.                     sizeCtl = (n << 1) - (n >>> 1);
  58.                     return;
  59.                 }
  60.                 if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
  61.                     if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
  62.                         return;
  63.                     finishing = advance = true;
  64.                     i = n; // recheck before commit
  65.                 }
  66.             }
  68.             // 如果扩容的节点是null 则直接赋值fwd
  69.             else if ((f = tabAt(tab, i)) == null)
  70.                 advance = casTabAt(tab, i, null, fwd);
  71.             else if ((fh = f.hash) == MOVED)
  72.                 advance = true; // already processed
  73.             else {
  74.                 //扩容的时候锁住当前要扩容的节点
  75.                 synchronized (f) {
  76.                     if (tabAt(tab, i) == f) {
  77.                         Node<K,V> ln, hn;
  78.                         if (fh >= 0) {
  79.                             int runBit = fh & n;
  80.                             Node<K,V> lastRun = f;
  81.                             for (Node<K,V> p = f.next; p != null; p = p.next) {
  82.                                 int b = p.hash & n;
  83.                                 if (b != runBit) {
  84.                                     runBit = b;
  85.                                     lastRun = p;
  86.                                 }
  87.                             }
  88.                             if (runBit == 0) {
  89.                                 ln = lastRun;
  90.                                 hn = null;
  91.                             }
  92.                             else {
  93.                                 hn = lastRun;
  94.                                 ln = null;
  95.                             }
  96.                             for (Node<K,V> p = f; p != lastRun; p = p.next) {
  97.                                 int ph = p.hash; K pk = p.key; V pv = p.val;
  98.                                 if ((ph & n) == 0)
  99.                                     ln = new Node<K,V>(ph, pk, pv, ln);
  100.                                 else
  101.                                     hn = new Node<K,V>(ph, pk, pv, hn);
  102.                             }
  103.                             setTabAt(nextTab, i, ln);
  104.                             setTabAt(nextTab, i + n, hn);
  105.                             setTabAt(tab, i, fwd);
  106.                             advance = true;
  107.                         }
  108.                         else if (f instanceof TreeBin) {
  109.                             TreeBin<K,V> t = (TreeBin<K,V>)f;
  110.                             TreeNode<K,V> lo = null, loTail = null;
  111.                             TreeNode<K,V> hi = null, hiTail = null;
  112.                             int lc = 0, hc = 0;
  113.                             for (Node<K,V> e = t.first; e != null; e = e.next) {
  114.                                 int h = e.hash;
  115.                                 TreeNode<K,V> p = new TreeNode<K,V>
  116.                                     (h, e.key, e.val, null, null);
  117.                                 if ((h & n) == 0) {
  118.                                     if ((p.prev = loTail) == null)
  119.                                         lo = p;
  120.                                     else
  121.                                         loTail.next = p;
  122.                                     loTail = p;
  123.                                     ++lc;
  124.                                 }
  125.                                 else {
  126.                                     if ((p.prev = hiTail) == null)
  127.                                         hi = p;
  128.                                     else
  129.                                         hiTail.next = p;
  130.                                     hiTail = p;
  131.                                     ++hc;
  132.                                 }
  133.                             }
  134.                             ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
  135.                                 (hc != 0) ? new TreeBin<K,V>(lo) : t;
  136.                             hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
  137.                                 (lc != 0) ? new TreeBin<K,V>(hi) : t;
  138.                             setTabAt(nextTab, i, ln);
  139.                             setTabAt(nextTab, i + n, hn);
  140.                             setTabAt(tab, i, fwd);
  141.                             advance = true;
  142.                         }
  143.                     }
  144.                 }
  145.             }
  146.         }
  147.     }

image.png

八 删除

  1.     final V replaceNode(Object key, V value, Object cv) {
  2.         int hash = spread(key.hashCode());
  3.         for (Node<K,V>[] tab = table;;) {
  4.             Node<K,V> f; int n, i, fh;
  5.             //删除位置是空的直接返回
  6.             if (tab == null || (n = tab.length) == 0 ||
  7.                 (f = tabAt(tab, i = (n - 1) & hash)) == null)
  8.                 break;
  9.             //要删除的节点正在扩容
  10.             else if ((fh = f.hash) == MOVED)
  11.                 tab = helpTransfer(tab, f);
  12.             else {
  13.                 V oldVal = null;
  14.                 boolean validated = false;
  15.                 //同样是锁住特定的节点
  16.                 synchronized (f) {
  17.                     if (tabAt(tab, i) == f) {
  18.                         if (fh >= 0) {
  19.                             validated = true;
  20.                             for (Node<K,V> e = f, pred = null;;) {
  21.                                 K ek;
  22.                                 if (e.hash == hash &&
  23.                                     ((ek = e.key) == key ||
  24.                                      (ek != null && key.equals(ek)))) {
  25.                                     V ev = e.val;
  26.                                     if (cv == null || cv == ev ||
  27.                                         (ev != null && cv.equals(ev))) {
  28.                                         oldVal = ev;
  29.                                         if (value != null)
  30.                                             e.val = value;
  31.                                         else if (pred != null)
  32.                                             pred.next = e.next;
  33.                                         else
  34.                                             setTabAt(tab, i, e.next);
  35.                                     }
  36.                                     break;
  37.                                 }
  38.                                 pred = e;
  39.                                 if ((e = e.next) == null)
  40.                                     break;
  41.                             }
  42.                         }
  43.                         else if (f instanceof TreeBin) {
  44.                             validated = true;
  45.                             TreeBin<K,V> t = (TreeBin<K,V>)f;
  46.                             TreeNode<K,V> r, p;
  47.                             if ((r = t.root) != null &&
  48.                                 (p = r.findTreeNode(hash, key, null)) != null) {
  49.                                 V pv = p.val;
  50.                                 if (cv == null || cv == pv ||
  51.                                     (pv != null && cv.equals(pv))) {
  52.                                     oldVal = pv;
  53.                                     if (value != null)
  54.                                         p.val = value;
  55.                                     else if (t.removeTreeNode(p))
  56.                                         setTabAt(tab, i, untreeify(t.first));
  57.                                 }
  58.                             }
  59.                         }
  60.                     }
  61.                 }
  62.                 if (validated) {
  63.                     if (oldVal != null) {
  64.                         if (value == null)
  65.                             addCount(-1L, -1);
  66.                         return oldVal;
  67.                     }
  68.                     break;
  69.                 }
  70.             }
  71.         }
  72.         return null;
  73.     }

九 获取

  1.     public V get(Object key) {
  2.         Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
  3.         int h = spread(key.hashCode());
  4.         if ((tab = table) != null && (n = tab.length) > 0 &&
  5.             (e = tabAt(tab, (n - 1) & h)) != null) {
  6.             if ((eh = e.hash) == h) {
  7.                 if ((ek = e.key) == key || (ek != null && key.equals(ek)))
  8.                     return e.val;
  9.             }
  10.             else if (eh < 0)
  11.                 return (p = e.find(h, key)) != null ? p.val : null;
  12.             while ((e = e.next) != null) {
  13.                 if (e.hash == h &&
  14.                     ((ek = e.key) == key || (ek != null && key.equals(ek))))
  15.                     return e.val;
  16.             }
  17.         }
  18.         return null;
  19.     }

十 spread

  1. //先保留hash值的高 16位特性，再与int的最大值进行与 相当于或得到int范围内能表示的数字
  2. static final int spread(int h) {
  3.         return (h ^ (h >>> 16)) & HASH_BITS;
  4.     }
  7. // (n - 1) & hash  实际使用  相当于对n-1取余操作