[关闭]
@eric1989 2017-01-15T06:21:03.000000Z 字数 11818 阅读 1293

Concurrenthashmap源码阅读(JDK8)

总体思路

JDK8版本的ConcurrentHashMap与前代的思路完全不同,不再采取分段锁的办法来提高并发.而是将并发粒度提高到了每一个槽位.由于槽位的分散粒度比分段锁大太多,因此很有效的降低了并发冲突.
简单的说,并发竞争在Node数组上每一个槽位.不同的槽位之间并没有并发竞争关系.而在一个槽位上执行读取操作是没有冲突的,数据的可见性通过Volatile修饰符来达成.而同一个槽位上的写操作冲突通过对首节点进行Sync加锁来完成互斥(还挺简单方便的).由于在同一个槽位上的元素都只能添加到末尾,因此锁住首节点就成为了一个非常方便的互斥手段.
在并发上的冲突降低主要就是依靠将冲突降低到了槽位的粒度来达成.由于没有分段锁这个概念,因为扩容的时候也可以多线程进行扩容(对比之前的版本,一个分段锁内只有一个线程在执行扩容操作).具体操作方式简单说,就是从当前Node数组的最大下标开始,每一个扩容的线程首先都通过cas获得一段属于该线程自身的下标范围,在这个下标范围内,这个线程的数据转移不会和其他的线程冲突.由于扩容是2N的方式扩容,在n槽位上的节点,扩容后或者在n槽位或者再2n槽位.因此只要每个线程的下标范围不重叠,就不会出现线程转移数据冲突的问题.也就是可以进行多线程协助扩容.

首先关注的放入数据的方法putVal(K key, V value, boolean onlyIfAbsent)

  1.   final V putVal(K key, V value, boolean onlyIfAbsent) {
  2.         if (key == null || value == null) throw new NullPointerException();
  3.         int hash = spread(key.hashCode());
  4.         int binCount = 0;
  5.         for (Node<K,V>[] tab = table;;) {
  6.             Node<K,V> f; int n, i, fh;
  7.             //如果table为null,则尝试初始化
  8.             if (tab == null || (n = tab.length) == 0)
  9.                 tab = initTable();
  10.             //经过hash计算,如果当前的槽位是空的,就尝试下cas将当前的值的包装node放入该槽位
  11.             else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
  12.                 //cas成功的话就可以走人了
  13.                 if (casTabAt(tab, i, null,
  14.                              new Node<K,V>(hash, key, value, null)))
  15.                     break;                   // no lock when adding to empty bin
  16.             }
  17.             //如果发现该节点是一个转移节点,则尝试帮助进行扩容过程
  18.             else if ((fh = f.hash) == MOVED)
  19.                 tab = helpTransfer(tab, f);
  20.             else {
  21.                 V oldVal = null;
  22.                 //首先锁定槽位上的元素(每个槽位上的node可能是以链表的形式存在也可能是以红黑树的形式存在,但无论如何,首节点确定后是不会更改的)
  23.                 synchronized (f) {
  24.                     //锁定成功后仍然需要再次确认,确认锁定前后是一致的
  25.                     if (tabAt(tab, i) == f) {
  26.                         //如果hash值大于0,意味着这是一个链条的node节点.
  27.                         if (fh >= 0) {
  28.                             //用于统计该链条上的节点数量
  29.                             binCount = 1;
  30.                             //for循环没有什么问题,就是不停的比对,直到找到为止,根据onlyIfAbsent是替换还是忽略
  31.                             for (Node<K,V> e = f;; ++binCount) {
  32.                                 K ek;
  33.                                 if (e.hash == hash &&
  34.                                     ((ek = e.key) == key ||
  35.                                      (ek != null && key.equals(ek)))) {
  36.                                     oldVal = e.val;
  37.                                     if (!onlyIfAbsent)
  38.                                         e.val = value;
  39.                                     break;
  40.                                 }
  41.                                 Node<K,V> pred = e;
  42.                                 if ((e = e.next) == null) {
  43.                                     pred.next = new Node<K,V>(hash, key,
  44.                                                               value, null);
  45.                                     break;
  46.                                 }
  47.                             }
  48.                         }
  49.                         else if (f instanceof TreeBin) {
  50.                             Node<K,V> p;
  51.                             binCount = 2;
  52.                             if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
  53.                                                            value)) != null) {
  54.                                 oldVal = p.val;
  55.                                 if (!onlyIfAbsent)
  56.                                     p.val = value;
  57.                             }
  58.                         }
  59.                     }
  60.                 }
  61.                 //如果链条长度超过了一定阀值,则将链条转化为红黑树
  62.                 if (binCount != 0) {
  63.                     if (binCount >= TREEIFY_THRESHOLD)
  64.                         //红黑树本身和并发无关,略过(其实是题主看不懂,手动滑稽)
  65.                         treeifyBin(tab, i);
  66.                     if (oldVal != null)
  67.                         return oldVal;
  68.                     break;
  69.                 }
  70.             }
  71.         }
  72.         //完成插入后就开始增加总数了
  73.         addCount(1L, binCount);
  74.         return null;
  75.     }

initTable()

在看下面这段代码之前,首先需要关注类的一个控制属性

  1. //这个属性用来完成对table的初始化或者扩容的控制权的归属争夺.主要有以下三种状态
  2. //1. -1意味着当前正在执行table的初始化
  3. //2. -(1+n)意味着当前有n个线程在执行扩容
  4. //3. 如果是正数,则是扩容阀值.意味着总体容量到达该数字的时候需要进行扩容
  5. private transient volatile int sizeCtl;
  1. private final Node<K,V>[] initTable() {
  2.         Node<K,V>[] tab; int sc;
  3.         while ((tab = table) == null || tab.length == 0) {
  4.             //发现已经有别的线程获得初始化或者扩容权限,则自旋
  5.             if ((sc = sizeCtl) < 0)
  6.                 Thread.yield(); // lost initialization race; just spin
  7.             else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
  8.                 try {
  9.                     if ((tab = table) == null || tab.length == 0) {
  10.                         int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
  11.                         @SuppressWarnings("unchecked")
  12.                         Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
  13.                         table = tab = nt;
  14.                         //sc的值就是75%的总容量
  15.                         sc = n - (n >>> 2);
  16.                     }
  17.                 } finally {
  18.                     sizeCtl = sc;
  19.                 }
  20.                 break;
  21.             }
  22.         }
  23.         return tab;
  24.     }

addCount(long x, int check)

看这个方法前,需要了解下,在jdk8中为了解决高并发下的原子统计.对以前的AtoicInteger类进行了增强.通过空间换时间的方式提升了高并发下的性能,具体的原理可以看另外一篇文章
以下的三个参数合并在一起完成了统计的作用(作用类似LongAddr,不太明白为什么不直接使用)

  1. //这个参数用于CounterCell的扩容权争夺
  2. private transient volatile int cellsBusy;
  3. private transient volatile long baseCount;
  4. private transient volatile CounterCell[] counterCells;
  5.  @sun.misc.Contended static final class CounterCell {
  6.         volatile long value;
  7.         CounterCell(long x) { value = x; }
  8.     }
  1. private final void addCount(long x, int check) {
  2.         CounterCell[] as; long b, s;
  3.         //如果counterCells存在意味着存在竞争,
  4.         //如果直接cas增加总数失败意味着存在竞争
  5.         if ((as = counterCells) != null ||
  6.             !U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
  7.             CounterCell a; long v; int m;
  8.             boolean uncontended = true;
  9.             //如果无法取得某一个counterCeller,或者在counterCeller上的cas直接增加失败,则进入到完整的增加总数代码中,也就是fullAddCount
  10.             if (as == null || (m = as.length - 1) < 0 ||
  11.                 (a = as[ThreadLocalRandom.getProbe() & m]) == null ||
  12.                 !(uncontended =
  13.                   U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
  14.                 fullAddCount(x, uncontended);
  15.                 return;
  16.             }
  17.             if (check <= 1)
  18.                 return;
  19.             //统计下当前线程能看到的总数(在很高并发的情况下,可以认为任何线程看到的总数都是滞后的)
  20.             s = sumCount();
  21.         }
  22.         if (check >= 0) {
  23.             Node<K,V>[] tab, nt; int n, sc;
  24.             while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
  25.                    (n = tab.length) < MAXIMUM_CAPACITY) {
  26.                 //这个方法就一句,Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1))
  27.                 //具体的作用就是通过位运算的方式得到一个当前table的长度的一种"表示数字"
  28.                 int rs = resizeStamp(n);
  29.                 if (sc < 0) {
  30.                     if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
  31.                         sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
  32.                         transferIndex <= 0)
  33.                         break;
  34.                     if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
  35.                         transfer(tab, nt);
  36.                 }
  37.                 else if (U.compareAndSwapInt(this, SIZECTL, sc,
  38.                                              (rs << RESIZE_STAMP_SHIFT) + 2))
  39.                     transfer(tab, null);
  40.                 s = sumCount();
  41.             }
  42.         }
  43.     }

fullAddCount(long x, boolean wasUncontended)

以下的代码核心思路就是通过空间换时间的方式来提高高并发下的性能.如果使用一个long变量来统计,多cpu核心并行的cas必然导致大量的失败,那么只要将这些cas尽可能的分散的不同的地方,就可以减少失败进而提高性能.因为除了一个基本的long变量用于cas争夺,还需要额外的数量与cpu核心数相同的额外变量用于分散cas争夺.同时由于这些额外变量会在不同的核心共享,为了避免伪共享发生,还需要进行缓存行填充(这一点,jdk8通过内部的注解由jvm自动的完成了)

  1. private final void fullAddCount(long x, boolean wasUncontended) {
  2.         int h;
  3.         //获取线程内的随机数,线程内的随机数,这是为了避免random方法的竞争
  4.         if ((h = ThreadLocalRandom.getProbe()) == 0) {
  5.             ThreadLocalRandom.localInit();      // force initialization
  6.             h = ThreadLocalRandom.getProbe();
  7.             wasUncontended = true;
  8.         }
  9.         //这是一个局部变量用于表达是否与其他的线程发生了碰撞
  10.         boolean collide = false;                // True if last slot nonempty
  11.         for (;;) {
  12.             CounterCell[] as; CounterCell a; int n; long v;
  13.             if ((as = counterCells) != null && (n = as.length) > 0) {
  14.                 if ((a = as[(n - 1) & h]) == null) {
  15.                     //所在槽位为空,则尝试赋予一个初值.这里采取乐观心态,首先初始化出CounterCell,然后再抢夺控制权
  16.                     if (cellsBusy == 0) {            // Try to attach new Cell
  17.                         CounterCell r = new CounterCell(x); // Optimistic create
  18.                         if (cellsBusy == 0 &&
  19.                             U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
  20.                             //控制权抢夺成功后先重新判断一次
  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.                                     rs[j] = r;
  28.                                     created = true;
  29.                                 }
  30.                             } finally {
  31.                                 //这里面通过对volatile变量的写入,保证了数组中对应槽位的写入也是可见的.
  32.                                 cellsBusy = 0;
  33.                             }
  34.                             if (created)
  35.                                 break;
  36.                             continue;           // Slot is now non-empty
  37.                         }
  38.                     }
  39.                     collide = false;
  40.                 }
  41.                 else if (!wasUncontended)       // CAS already known to fail
  42.                     wasUncontended = true;      // Continue after rehash
  43.                 //尝试在对应的槽位上进行cas操作
  44.                 else if (U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))
  45.                     break;
  46.                 else if (counterCells != as || n >= NCPU)
  47.                     collide = false;            // At max size or stale
  48.                 else if (!collide)
  49.                     collide = true;
  50.                 //在对应的CounterCell上cas失败1或者2次(看wasUncontended和collide的值)后,尝试进行扩容
  51.                 else if (cellsBusy == 0 &&
  52.                          U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
  53.                     try {
  54.                         if (counterCells == as) {// Expand table unless stale
  55.                             CounterCell[] rs = new CounterCell[n << 1];
  56.                             for (int i = 0; i < n; ++i)
  57.                                 rs[i] = as[i];
  58.                             counterCells = rs;
  59.                         }
  60.                     } finally {
  61.                         cellsBusy = 0;
  62.                     }
  63.                     collide = false;
  64.                     continue;                   // Retry with expanded table
  65.                 }
  66.                 h = ThreadLocalRandom.advanceProbe(h);
  67.             }
  68.             //程序走到这里意味着CounterCell数组为null.那么尝试抢夺初始化权限
  69.             else if (cellsBusy == 0 && counterCells == as &&
  70.                      U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
  71.                 boolean init = false;
  72.                 try {                           // Initialize table
  73.                     //抢夺到权限后首先要判断是否是之前的情况,如果是的话,则可以进行初始化,并且完成对应CounterCell内部值的填充.
  74.                     if (counterCells == as) {
  75.                         //注意,这里的初始化大小是2,但是只有一个槽位被填充,而剩下一个是null.考虑设计意图也许是为了避免浪费
  76.                         CounterCell[] rs = new CounterCell[2];
  77.                         rs[h & 1] = new CounterCell(x);
  78.                         counterCells = rs;
  79.                         init = true;
  80.                     }
  81.                 } finally {
  82.                     cellsBusy = 0;
  83.                 }
  84.                 if (init)
  85.                     break;
  86.             }
  87.             //CounterCell数组为null,但是初始化控制权抢夺失败,则尝试下在基础的baseCount再执行一次cas
  88.             else if (U.compareAndSwapLong(this, BASECOUNT, v = baseCount, v + x))
  89.                 break;                          // Fall back on using base
  90.         }
  91.     }

transfer(Node[] tab, Node[] nextTab)

  1. private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
  2.         int n = tab.length, stride;
  3.         //计算出一个线程一次搬运的区间
  4.         if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
  5.             stride = MIN_TRANSFER_STRIDE; // subdivide range
  6.         if (nextTab == null) {            // initiating
  7.             try {
  8.                 @SuppressWarnings("unchecked")
  9.                 Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
  10.                 nextTab = nt;
  11.             } catch (Throwable ex) {      // try to cope with OOME
  12.                 sizeCtl = Integer.MAX_VALUE;
  13.                 return;
  14.             }
  15.             nextTable = nextTab;
  16.             transferIndex = n;
  17.         }
  18.         int nextn = nextTab.length;
  19.         ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
  20.         boolean advance = true;
  21.         boolean finishing = false; // to ensure sweep before committing nextTab
  22.         for (int i = 0, bound = 0;;) {
  23.             Node<K,V> f; int fh;
  24.             //这个循环用于确定本次可以转移的槽位的下标范围,主要是通过最后一个else if的cas来完成
  25.             while (advance) {
  26.                 int nextIndex, nextBound;
  27.                 //本次确定下标范围后还没有转移完成则继续转移
  28.                 if (--i >= bound || finishing)
  29.                     advance = false;
  30.                 //如果没有可以转移的内容了,则准备结束
  31.                 else if ((nextIndex = transferIndex) <= 0) {
  32.                     i = -1;
  33.                     advance = false;
  34.                 }
  35.                 //这个cas成功之后就确定了该线程搬运的槽位的下标范围
  36.                 else if (U.compareAndSwapInt
  37.                          (this, TRANSFERINDEX, nextIndex,
  38.                           nextBound = (nextIndex > stride ?
  39.                                        nextIndex - stride : 0))) {
  40.                     bound = nextBound;
  41.                     //i能够取值的范围从nextIndex-1到bound
  42.                     i = nextIndex - 1;
  43.                     advance = false;
  44.                 }
  45.             }
  46.             //这边i会大于n的情况主要是参与扩容的线程因为cpu调度的原因导致长时间失去cpu资源,恢复过来后,i=nextIndex-1就会比入参的tab.length要大了
  47.             if (i < 0 || i >= n || i + n >= nextn) {
  48.                 int sc;
  49.                 if (finishing) {
  50.                     nextTable = null;
  51.                     table = nextTab;
  52.                     sizeCtl = (n << 1) - (n >>> 1);
  53.                     return;
  54.                 }
  55.                 //每个扩容线程在结束扩容后都会执行这个语句来减少自己的计数sizectl的计数,而当最后的线程尝试退出后,sc会等于rs+1.这个值就意味着最后的线程正在提交扩容后的table前做最后一遍检查.
  56.                 //问题在于.这个检查的意义在什么地方,从代码上看不到为何需要检查
  57.                 if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
  58.                     //因为可能存在多个线程参与扩容,那么只有符合下面这个等式的,才是最后一个退出扩容动作的线程
  59.                     if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
  60.                         return;
  61.                     finishing = advance = true;
  62.                     //为什么要再次检查这边看不出原因
  63.                     i = n; // recheck before commit
  64.                 }
  65.             }
  66.             else if ((f = tabAt(tab, i)) == null)
  67.                 advance = casTabAt(tab, i, null, fwd);
  68.             else if ((fh = f.hash) == MOVED)
  69.                 advance = true; // already processed
  70.             else {
  71.                 synchronized (f) {
  72.                     if (tabAt(tab, i) == f) {
  73.                         Node<K,V> ln, hn;
  74.                         //如果该槽位上的是链表节点
  75.                         if (fh >= 0) {
  76.                             int runBit = fh & n;
  77.                             Node<K,V> lastRun = f;
  78.                             //遍历该槽位上的所有数据,并且确定出一个lastRun.这个lastRun用于该节点以及之后的节点具备相当hash特征(他们的hash值&n都等于一个相同的数字),那么这些节点是需要迁移到nextTable的相同槽位的
  79.                             for (Node<K,V> p = f.next; p != null; p = p.next) {
  80.                                 int b = p.hash & n;
  81.                                 if (b != runBit) {
  82.                                     runBit = b;
  83.                                     lastRun = p;
  84.                                 }
  85.                             }
  86.                             //这里的ln和hn是用来表达在扩容后原来i位置的节点,要么仍然在i位置,要么在i+n位置.这个是由于2n扩容的数学特性得到的,那么ln就是仍然在i位置的,hn就是在i+n位置的了.具体的说,如果本身hash&n==0,那么扩容后仍然在i位置,也就是ln.否则就是在i+n位置,也就是hn.
  87.                             if (runBit == 0) {
  88.                                 ln = lastRun;
  89.                                 hn = null;
  90.                             }
  91.                             else {
  92.                                 hn = lastRun;
  93.                                 ln = null;
  94.                             }
  95.                             //遍历槽位上的节点,分别得到最终的ln节点和hn节点
  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.                         //如果是红黑树节点,题主完全看不懂红黑树,这段代码放弃
  109.                         else if (f instanceof TreeBin) {
  110.                             TreeBin<K,V> t = (TreeBin<K,V>)f;
  111.                             TreeNode<K,V> lo = null, loTail = null;
  112.                             TreeNode<K,V> hi = null, hiTail = null;
  113.                             int lc = 0, hc = 0;
  114.                             for (Node<K,V> e = t.first; e != null; e = e.next) {
  115.                                 int h = e.hash;
  116.                                 TreeNode<K,V> p = new TreeNode<K,V>
  117.                                     (h, e.key, e.val, null, null);
  118.                                 if ((h & n) == 0) {
  119.                                     if ((p.prev = loTail) == null)
  120.                                         lo = p;
  121.                                     else
  122.                                         loTail.next = p;
  123.                                     loTail = p;
  124.                                     ++lc;
  125.                                 }
  126.                                 else {
  127.                                     if ((p.prev = hiTail) == null)
  128.                                         hi = p;
  129.                                     else
  130.                                         hiTail.next = p;
  131.                                     hiTail = p;
  132.                                     ++hc;
  133.                                 }
  134.                             }
  135.                             ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
  136.                                 (hc != 0) ? new TreeBin<K,V>(lo) : t;
  137.                             hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
  138.                                 (lc != 0) ? new TreeBin<K,V>(hi) : t;
  139.                             setTabAt(nextTab, i, ln);
  140.                             setTabAt(nextTab, i + n, hn);
  141.                             setTabAt(tab, i, fwd);
  142.                             advance = true;
  143.                         }
  144.                     }
  145.                 }
  146.             }
  147.         }
  148.     }

helpTransfer(Node[] tab, Node f)

  1. final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
  2.         Node<K,V>[] nextTab; int sc;
  3.         //明确符合帮助扩容的基础条件后,尝试将自身线程加入到扩容线程中
  4.         if (tab != null && (f instanceof ForwardingNode) &&
  5.             (nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
  6.             int rs = resizeStamp(tab.length);
  7.             while (nextTab == nextTable && table == tab &&
  8.                    (sc = sizeCtl) < 0) {
  9.                    //(sc >>> RESIZE_STAMP_SHIFT) != rs意味着tab已经变化了
  10.                    //sc == rs + 1意味着扩容已经结束,最后一个要退出的线程正在执行检查流程
  11.                 if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
  12.                     sc == rs + MAX_RESIZERS || transferIndex <= 0)
  13.                     break;
  14.                 if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
  15.                     transfer(tab, nextTab);
  16.                     break;
  17.                 }
  18.             }
  19.             return nextTab;
  20.         }
  21.         return table;
  22.     }

获取元素的方式get(Object key)

获取元素的方式和之前的版本相差不多,都是通过hash定位到对应的槽位上进行操作.与之前相比就是现在的槽位上可能是一个链表元素,或者一个树元素,还有可能是一种代表正在扩容的特殊Node.

  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.                 //需要注意的就是这个地方,槽位上不是链表的时候,通过特殊节点的find方法来进行对应key的寻找,下面以扩容节点来作为说明
  12.                 return (p = e.find(h, key)) != null ? p.val : null;
  13.             while ((e = e.next) != null) {
  14.                 if (e.hash == h &&
  15.                     ((ek = e.key) == key || (ek != null && key.equals(ek))))
  16.                     return e.val;
  17.             }
  18.         }
  19.         return null;
  20.     }

扩容节点的find方法如下

  1. Node<K,V> find(int h, Object k) {
  2.             // loop to avoid arbitrarily deep recursion on forwarding nodes
  3.             //这里的nextTable是类属性,所以必然是有值,代表的下一个转移数据的table,寻找数据的思路和普通的tab没有区别,只不过在寻找的过程也可能发现tab又扩容了,此时碰到ForwandingNode的话,则重新开始循环,而不是直接调用其节点的find方法.根据jdk的注解,这个是为了避免过深的方法嵌套.
  4.             outer: for (Node<K,V>[] tab = nextTable;;) {
  5.                 Node<K,V> e; int n;
  6.                 if (k == null || tab == null || (n = tab.length) == 0 ||
  7.                     (e = tabAt(tab, (n - 1) & h)) == null)
  8.                     return null;
  9.                 for (;;) {
  10.                     int eh; K ek;
  11.                     if ((eh = e.hash) == h &&
  12.                         ((ek = e.key) == k || (ek != null && k.equals(ek))))
  13.                         return e;
  14.                     if (eh < 0) {
  15.                         if (e instanceof ForwardingNode) {
  16.                             tab = ((ForwardingNode<K,V>)e).nextTable;
  17.                             continue outer;
  18.                         }
  19.                         else
  20.                             return e.find(h, k);
  21.                     }
  22.                     if ((e = e.next) == null)
  23.                         return null;
  24.                 }
  25.             }
  26.         }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注