1. ConcurrentHashMap
1.1 HaspMap（JDK 1.8）
JDK 1.8 HashMap
- JDK 1.8 对 HashMap 进行了修改，最大的不同就是利用了红黑树，其由数组+链表+红黑树组成。
- JDK 1.7 中，查找元素时，根据 hash 值能够快速定位到数组的具体下标，但之后需要顺着链表依次比较才能查找到需要的元素，时间复杂度取决于链表的长度，为 O(N)。
- 为了降低这部分的开销，在 JDK 1.8 中，当链表中的元素超过 8 个以后，会将链表转换为红黑树，在这些位置进行查找的时候可以降低时间复杂度为 O(logN)。
- JDK 1.8 使用 Node（1.7 为 Entry） 作为链表的数据结点，仍然包含 key，value，hash 和 next 四个属性。
- 红黑树的情况使用的是 TreeNode。
- 根据数组元素中，第一个结点数据类型是 Node 还是 TreeNode 可以判断该位置下是链表还是红黑树。
- 核心成员变量于 1.7 类似，增加了核心变量，如下表。
| 属性 | 说明 |
|---|---|
| TREEIFY_THRESHOLD | 用于判断是否需要将链表转换为红黑树的阈值，默认为 8。 |
put 方法过程
public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } // onlyIfAbsent 如果是 true，那么只有在不存在该 key 时才会进行 put 操作。 final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; // 第一次 put 值的时候，会触发下面的 resize()，类似 java7 的第一次 put 也要初始化数组长度 // 第一次 resize 和后续的扩容有些不一样，因为这次是数组从 null 初始化到默认的 16 或自定义的初始容量 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // 找到具体的数组下标，如果此位置没有值，那么直接初始化一下 Node 并放置在这个位置就可以了 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else {// 数组该位置有数据 Node<K,V> e; K k; // 首先，判断该位置的第一个数据和我们要插入的数据，key 是不是"相等"，如果是，取出这个结点 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; // 如果该结点是代表红黑树的结点，调用红黑树的插值方法，本文不展开说红黑树 else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { // 到这里，说明数组该位置上是一个链表 for (int binCount = 0; ; ++binCount) { // 插入到链表的最后面(Java7 是插入到链表的最前面) if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); // TREEIFY_THRESHOLD 为 8，所以，如果新插入的值是链表中的第 9 个 // 会触发下面的 treeifyBin，也就是将链表转换为红黑树 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } // 如果在该链表中找到了"相等"的 key(== 或 equals) if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) // 此时 break，那么 e 为链表中[与要插入的新值的 key "相等"]的 node break; p = e; } } // e!=null 说明存在旧值的key与要插入的key"相等" // 对于我们分析的put操作，下面这个 if 其实就是进行 "值覆盖"，然后返回旧值 if (e != null) { V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; // 如果 HashMap 由于新插入这个值导致 size 已经超过了阈值，需要进行扩容 if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }
- put 方法的流程。
- 判断当前桶是否为空，空的就需要初始化（resize 中会判断是否进行初始化）。
- 根据当前 key 的 hashcode 定位到具体的桶中并判断是否为空，为空表明没有 hash 冲突直接在当前位置创建一个新桶。
- 如果当前桶有值（ hash 冲突），比较当前桶中的 key 和 key 的 hashcode 与写入的 key 是否相等，相等赋值给 e，在第 8 步的时候统一进行赋值及返回。
- 如果当前桶为红黑树，就按照红黑树的方式写入数据。
- 如果是链表，将当前的 key、value 封装成一个 新结点写入到当前桶的后面（形成链表）。
- 判断当前链表的大小是否大于预设的阈值（TREEIFY_THRESHOLD），大于时转换为红黑树。
- 如果在遍历过程中找到 key 相同时直接退出遍历。
- 如果 e != null 说明存在相同的 key，将值覆盖。
- 判断是否需要进行扩容。
数组扩容
- resize() 方法用于初始化数组或数组扩容，每次扩容后，容量为原来的 2 倍，并进行数据迁移
final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; if (oldCap > 0) { // 对应数组扩容 if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } // 将数组大小扩大一倍 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) // 将阈值扩大一倍 newThr = oldThr << 1; // double threshold } else if (oldThr > 0) // 对应使用 new HashMap(int initialCapacity) 初始化后，第一次 put 的时候 newCap = oldThr; else {// 对应使用 new HashMap() 初始化后，第一次 put 的时候 newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } if (newThr == 0) { float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold = newThr; // 用新的数组大小初始化新的数组 Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; // 如果是初始化数组，到这里就结束了，返回 newTab 即可 if (oldTab != null) { // 开始遍历原数组，进行数据迁移。 for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) != null) { oldTab[j] = null; // 如果该数组位置上只有单个元素，迁移这个元素就可以了 if (e.next == null) newTab[e.hash & (newCap - 1)] = e; // 如果是红黑树的处理 else if (e instanceof TreeNode) ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); else { // 这块是处理链表的情况， // 需要将此链表拆成两个链表，放到新的数组中，并且保留原来的先后顺序 // loHead、loTail 对应一条链表，hiHead、hiTail 对应另一条链表 Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; do { next = e.next; if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); if (loTail != null) { loTail.next = null; // 第一条链表 newTab[j] = loHead; } if (hiTail != null) { hiTail.next = null; // 第二条链表的新的位置是 j + oldCap newTab[j + oldCap] = hiHead; } } } } } return newTab; }
get 方法过程
- 计算 key 的 hash 值，根据 hash 值找到对应数组下标 hash & (length-1)。
- 判断数组该位置处的元素是否刚好就是需要的元素，如果不是，则走第 3 步。
- 判断该元素类型是否是 TreeNode，如果是，用红黑树的方法取数据，如果不是，走第 4 步。
- 遍历链表，直到找到相等（== 或 equals）的 key。
- 1.8 中对链表做了优化，修改为红黑树之后查询效率直接提高到了 O(logN)，但是 HashMap 原有的死循环问题还是存在。
- HashMap 扩容的时候会调用 resize() 方法，这里的并发操作容易在一个桶上形成环形链表，这样当获取一个不存在的 key 时，计算出的 index 正好是环形链表的下标就会出现死循环。
public V get(Object key) { Node<K,V> e; return (e = getNode(hash(key), key)) == null ? null : e.value; } final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k; if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { // 判断第一个结点是不是需要的 if (first.hash == hash && // always check first node ((k = first.key) == key || (key != null && key.equals(k)))) return first; if ((e = first.next) != null) { // 判断是否是红黑树 if (first instanceof TreeNode) return ((TreeNode<K,V>)first).getTreeNode(hash, key); // 链表遍历 do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } return null; }
1.2 ConcurrentHashMap（JDK 1.8）
JDK 1.8 ConcurrentHashMap
- 抛弃了 JDK 1.7 中原有的 Segment 分段锁，而采用了 CAS + synchronized 来保证并发安全性。
- 将 JDK 1.7 中存放数据的 HashEntry 改为 Node，但作用是相同的。
| 属性 | 说明 |
|---|---|
| table | 默认为 null，初始化发生在第一次插入操作，默认大小为 16 的数组，用来存储 Node 结点数据，扩容时大小总是 2 的幂次方。 |
| nextTable | 默认为 null，扩容时新生成的数组，其大小为原数组的两倍。 |
| sizeCtl | 默认为 0，用来控制 table 的初始化和扩容操作。-1 代表 table 正在初始化；-N 表示有 N-1 个线程正在进行扩容操作。 |
| ForwardingNode | 一个特殊的 Node 结点，hash 值为 -1，其中存储 nextTable 的引用。有 table 发生扩容的时候，ForwardingNode 发挥作用，作为一个占位符放在 table 中表示当前结点为 null 或者已经被移动。 |
static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; volatile V val; volatile Node<K,V> next; Node(int hash, K key, V val, Node<K,V> next) { this.hash = hash; this.key = key; this.val = val; this.next = next; } public final K getKey() { return key; } public final V getValue() { return val; } public final int hashCode() { return key.hashCode() ^ val.hashCode(); } public final String toString(){ return key + "=" + val; } public final V setValue(V value) { throw new UnsupportedOperationException(); } public final boolean equals(Object o) { Object k, v, u; Map.Entry<?,?> e; return ((o instanceof Map.Entry) && (k = (e = (Map.Entry<?,?>)o).getKey()) != null && (v = e.getValue()) != null && (k == key || k.equals(key)) && (v == (u = val) || v.equals(u))); } /** * Virtualized support for map.get(); overridden in subclasses. */ Node<K,V> find(int h, Object k) { Node<K,V> e = this; if (k != null) { do { K ek; if (e.hash == h && ((ek = e.key) == k || (ek != null && k.equals(ek)))) return e; } while ((e = e.next) != null); } return null; } }
put 方法过程
final V putVal(K key, V value, boolean onlyIfAbsent) { if (key == null || value == null) throw new NullPointerException(); // 键或值为空，抛出异常 // 键的hash值经过计算获得hash值，这里的 hash 计算多了一步 & HASH_BITS，HASH_BITS 是 0x7fffffff，该步是为了消除最高位上的负符号 hash的负在ConcurrentHashMap中有特殊意义表示在扩容或者是树结点 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) // 表为空或者表的长度为0 // 初始化表 tab = initTable(); else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { // 表不为空并且表的长度大于0，并且该桶不为空 if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null))) // 比较并且交换值，如tab的第i项为空则用新生成的node替换 break; // no lock when adding to empty bin } else if ((fh = f.hash) == MOVED) // 该结点的hash值为MOVED // 进行结点的转移（在扩容的过程中） tab = helpTransfer(tab, f); else { V oldVal = null; synchronized (f) { // 加锁同步 if (tabAt(tab, i) == f) { // 找到table表下标为i的结点 if (fh >= 0) { // 该table表中该结点的hash值大于0 // binCount赋值为1 binCount = 1; for (Node<K,V> e = f;; ++binCount) { // 无限循环 K ek; if (e.hash == hash && ((ek = e.key) == key || (ek != null && key.equals(ek)))) { // 结点的hash值相等并且key也相等 // 保存该结点的val值 oldVal = e.val; if (!onlyIfAbsent) // 进行判断 // 将指定的value保存至结点，即进行了结点值的更新 e.val = value; break; } // 保存当前结点 Node<K,V> pred = e; if ((e = e.next) == null) { // 当前结点的下一个结点为空，即为最后一个结点 // 新生一个结点并且赋值给next域 pred.next = new Node<K,V>(hash, key, value, null); // 退出循环 break; } } } else if (f instanceof TreeBin) { // 结点为红黑树结点类型 Node<K,V> p; // binCount赋值为2 binCount = 2; if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, value)) != null) { // 将hash、key、value放入红黑树 // 保存结点的val oldVal = p.val; if (!onlyIfAbsent) // 判断 // 赋值结点value值 p.val = value; } } } } if (binCount != 0) { // binCount不为0 if (binCount >= TREEIFY_THRESHOLD) // 如果binCount大于等于转化为红黑树的阈值 // 进行转化 treeifyBin(tab, i); if (oldVal != null) // 旧值不为空 // 返回旧值 return oldVal; break; } } } // 增加binCount的数量 addCount(1L, binCount); return null; }
- 判断存储的 key、value 是否为空，若为空，则抛出异常，否则，进入步骤 2。
- 计算 key 的 hash 值，随后进入自旋，该自旋可以确保成功插入数据，若 table 表为空或者长度为 0，则初始化 table 表，否则，进入步骤 3。
- 根据 key 的 hash 值取出 table 表中的结点元素，若取出的结点为空（该桶为空），则使用 CAS 将 key、value、hash 值生成的结点放入桶中。否则，进入步骤 4。
- 若该结点的的 hash 值为 MOVED（-1），则对该桶中的结点进行转移，否则，进入步骤 5。
- 对桶中的第一个结点（即 table 表中的结点）进行加锁，对该桶进行遍历，桶中的结点的 hash 值与 key 值与给定的 hash 值和 key 值相等，则根据标识选择是否进行更新操作（用给定的 value 值替换该结点的 value 值），若遍历完桶仍没有找到 hash 值与 key 值和指定的 hash 值与 key 值相等的结点，则直接新生一个结点并赋值为之前最后一个结点的下一个结点。进入步骤 6。
- 若 binCount 值达到红黑树转化的阈值，则将桶中的结构转化为红黑树存储，最后，增加 binCount 的值。
- 如果桶中的第一个元素的 hash 值大于 0，说明是链表结构，则对链表插入或者更新。
- 如果桶中的第一个元素是 TreeBin，说明是红黑树结构，则按照红黑树的方式进行插入或者更新。
- 在锁的保护下，插入或者更新完毕后，如果是链表结构，需要判断链表中元素的数量是否超过 8（默认），一旦超过，就需要考虑进行数组扩容，或者是链表转红黑树。
初始化数组
- 初始化方法中的并发问题是通过对 sizeCtl 进行一个 CAS 操作来控制的。
- 只有第一次使用才初始化，为了防止初始化后的首次操作就需要扩容（比如 putAll ），从而影响效率。
private final Node<K,V>[] initTable() { Node<K,V>[] tab; int sc; while ((tab = table) == null || tab.length == 0) { // 初始化数组的工作其它线程正在做 if ((sc = sizeCtl) < 0) Thread.yield(); // lost initialization race; just spin // CAS 一下，将 sizeCtl 设置为 -1，代表抢到了锁 else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) { try { if ((tab = table) == null || tab.length == 0) { // DEFAULT_CAPACITY 默认初始容量是 16 int n = (sc > 0) ? sc : DEFAULT_CAPACITY; // 初始化数组，长度为 16 或初始化时提供的长度 Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n]; // 将这个数组赋值给 table，table 是 volatile 的 table = tab = nt; // 如果 n 为 16 的话，那么这里 sc = 12 // 其实就是 0.75 * n sc = n - (n >>> 2); } } finally { // 设置 sizeCtl 为 sc sizeCtl = sc; } break; } } return tab; }
链表转红黑树
- treeifyBin 不一定就会进行红黑树转换，也可能是仅仅做数组扩容。
private final void treeifyBin(Node<K,V>[] tab, int index) { Node<K,V> b; int n, sc; if (tab != null) { // 表不为空 if ((n = tab.length) < MIN_TREEIFY_CAPACITY) // table表的长度小于最小的长度 // 进行扩容，调整某个桶中结点数量过多的问题（由于某个桶中结点数量超出了阈值，则触发treeifyBin） tryPresize(n << 1); else if ((b = tabAt(tab, index)) != null && b.hash >= 0) { // 桶中存在结点并且结点的hash值大于等于0 synchronized (b) { // 对桶中第一个结点进行加锁 if (tabAt(tab, index) == b) { // 第一个结点没有变化 TreeNode<K,V> hd = null, tl = null; for (Node<K,V> e = b; e != null; e = e.next) { // 遍历桶中所有结点 // 新生一个TreeNode结点 TreeNode<K,V> p = new TreeNode<K,V>(e.hash, e.key, e.val, null, null); if ((p.prev = tl) == null) // 该结点前驱为空 // 设置p为头结点 hd = p; else // 尾结点的next域赋值为p tl.next = p; // 尾结点赋值为p tl = p; } // 设置table表中下标为index的值为hd setTabAt(tab, index, new TreeBin<K,V>(hd)); } } } } }
数组扩容
- 扩容后数组容量为原来的 2 倍。
// 参数 size 传进来的时候就已经翻倍（例如 16） private final void tryPresize(int size) { // c：size 的 1.5 倍，再加 1，再往上取最近的 2 的 n 次方。 // 16 + 8 + 1 -> 32 -> 2^8 int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY : tableSizeFor(size + (size >>> 1) + 1); int sc; while ((sc = sizeCtl) >= 0) { Node<K,V>[] tab = table; int n; // 这个 if 分支和之前说的初始化数组的代码基本上是一样的，在这里，我们可以不用管这块代码 if (tab == null || (n = tab.length) == 0) { n = (sc > c) ? sc : c; if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) { try { if (table == tab) { @SuppressWarnings("unchecked") Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n]; table = nt; sc = n - (n >>> 2); // 0.75 * n } } finally { sizeCtl = sc; } } } else if (c <= sc || n >= MAXIMUM_CAPACITY) break; else if (tab == table) { int rs = resizeStamp(n); if (sc < 0) { Node<K,V>[] nt; if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 || sc == rs + MAX_RESIZERS || (nt = nextTable) == null || transferIndex <= 0) break; // 2. 用 CAS 将 sizeCtl 加 1，然后执行 transfer 方法 // 此时 nextTab 不为 null if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) transfer(tab, nt); } // 1. 将 sizeCtl 设置为 (rs << RESIZE_STAMP_SHIFT) + 2) // 调用 transfer 方法，此时 nextTab 参数为 null else if (U.compareAndSwapInt(this, SIZECTL, sc, (rs << RESIZE_STAMP_SHIFT) + 2)) transfer(tab, null); } } }
数据迁移
- 此方法支持多线程执行，外围调用此方法的时候，会保证第一个发起数据迁移的线程，nextTab 参数为 null，之后再调用此方法的时候，nextTab 不会为 null。
- 理解为有 n 个迁移任务，让每个线程每次负责一个小任务，每做完一个任务再检测是否有其他没做完的任务。
- Doug Lea 使用了一个 stride（步长），每个线程每次负责迁移其中的一部分，如每次迁移 16 个小任务。所以需要一个全局的调度者来安排哪个线程执行哪几个任务，这个就是属性 transferIndex 的作用。
- transfer 这个方法并没有实现所有的迁移任务，每次调用这个方法只实现了 transferIndex 往前 stride 个位置的迁移工作，其他的需要由外围来控制。
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) { int n = tab.length, stride; //根据cpu个数找出扩容时的数组跨度大小即最小分组 16 32 64增长 if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE) stride = MIN_TRANSFER_STRIDE; // subdivide range //普通扩容nextTab为空，竞争帮助扩容时有值，n<<1说明扩容2倍 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; //创建扩容的连接结点，结点hash是-1 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)//当前分组未转移完||扩容全部完成 --i完成数组逆序迁移 advance = false; else if ((nextIndex = transferIndex) <= 0) {//TRANSFERINDEX为0表示无下一个分组了 i = -1; advance = false; } else if (U.compareAndSwapInt (this, TRANSFERINDEX, nextIndex, nextBound = (nextIndex > stride ? nextIndex - stride : 0))) {//CAS TRANSFERINDEX 多线程时，advance死循环会找到不同的分组，以一个分组一个线程负责来进行扩容 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);//0.75 return; } if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {//减少一个扩容线程 if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)//根据前面addCount的+2这里就有-2 判断是否是最后一个正在扩容的线程 return; finishing = advance = true;//准备结束 i = n; // recheck before commit 赋值n让其进入本if进行是否结束的检查 } } else if ((f = tabAt(tab, i)) == null)//原数组i位置无结点 advance = casTabAt(tab, i, null, fwd);//cas插入扩容结点 多线程插入失败就循环重新检查 else if ((fh = f.hash) == MOVED)//实际是检查上一步为null时CAS是否成功 advance = true; // already processed 之后在上面的while中变更i后继续 else { synchronized (f) {//首结点上锁 if (tabAt(tab, i) == f) {//结点此时没本remove等干掉 Node<K,V> ln, hn; if (fh >= 0) {//不是树结点 //下面这段是在拆分本位置的链表 一拆为二(一链表正向一链表反向,0或非0谁在最后连续那它就是正向，另一个反向) map大小n是2的倍数 与计算只会有0和n本身 好想法 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);//拆后的链表1放在新数组i位置 setTabAt(nextTab, i + n, hn);//链表2放i+n位置 setTabAt(tab, i, fwd);//原数组i位置放扩容结点 advance = true;//i位置索引迁移完成 } 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; } } } } } }
get 方法过程
public V get(Object key) { Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek; int h = spread(key.hashCode()); if ((tab = table) != null && (n = tab.length) > 0 && (e = tabAt(tab, (n - 1) & h)) != null) { // 判断头结点是否就是我们需要的结点 if ((eh = e.hash) == h) { if ((ek = e.key) == key || (ek != null && key.equals(ek))) return e.val; } // 如果头结点的 hash 小于 0，说明 正在扩容，或者该位置是红黑树 else if (eh < 0) // 参考 ForwardingNode.find(int h, Object k) 和 TreeBin.find(int h, Object k) return (p = e.find(h, key)) != null ? p.val : null; // 遍历链表 while ((e = e.next) != null) { if (e.hash == h && ((ek = e.key) == key || (ek != null && key.equals(ek)))) return e.val; } } return null; }
- 计算 hash 值。
- 根据 hash 值找到数组对应位置: (n – 1) & h。
- 根据该位置处结点性质进行相应查找。
- 如果该位置为 null，那么直接返回 null。
- 如果该位置处的结点刚好就是需要的，返回该结点的值即可。
- 如果该位置结点的 hash 值小于 0，说明正在扩容，或者是红黑树。
- 如果以上 3 条都不满足，那就是链表，进行遍历比对即可。
1.2.1 ConcurrentHashmap 不支持 key 或者 value 为 null 的原因
- ConcurrentHashmap 和 Hashtable 都是支持并发的，当通过
get(k)获取对应的 value 时，如果获取到的是 null 时，无法判断是put(k,v)的时候 value 为 null，还是这个 key 从来没有做过映射。- HashMap 是非并发的，可以通过 contains(key) 来做这个判断。
- 支持并发的 Map 在调用
m.contains(key)和m.get(key)时，m 可能已经发生了更改。
- 因此 ConcurrentHashmap 和 Hashtable 都不支持 key 或者 value 为 null。
参考资源
http://www.importnew.com/28263.html
https://baijiahao.baidu.com/s?id=1607561719049934113&wfr=spider&for=pc
https://www.cnblogs.com/ITtangtang/p/3948786.html
https://blog.csdn.net/wo2niliye/article/details/69396812
https://blog.csdn.net/justloveyou_/article/details/72783008
https://blog.csdn.net/justloveyou_/article/details/62893086
https://www.cnblogs.com/dolphin0520/p/3932905.html
http://www.importnew.com/26049.html
https://blog.csdn.net/lin20044140410/article/details/79320587
http://ifeve.com/concurrenthashmap/