HashMap的整体架构
HashMap 底层的数据结构主要是：数组 + 链表 + 红黑树。
当链表的长度 >= 8 时，链表会转化成红黑树，当红黑树的大小 <= 6 时，红黑树会转化成链表，整体的数据结构如下：
图中左边竖着的是 HashMap 的数组结构，数组的元素可能是单个 Node，也可能是个链表，也可能是个红黑树。
从 HashMap 的类注释可以得到如下信息：
- 允许 null 值
- 不同于 HashTable，HashMap 是线程不安全的，我们可以在外部加锁，或者通过
Collections.synchronizedMap()来实现线程安全，它的实现是在每个方法上加上 synchronized 锁 load factor（负载因子）默认值是 0.75
0.75 是均衡了时间和空间损耗算出来的值，较高的值会减少空间开销（扩容减少，数组长度增长速度变慢），但增加了查找成本（hash 冲突增加，链表长度变长），不扩容的条件：需要的数组大小 < 数组容量 * load factor
如果有很多数据需要储存到 HashMap 中，建议 HashMap 的容量一开始就设置成足够的大小，这样可以防止在新增过程中不断的扩容，影响性能
- 在迭代过程中，如果 HashMap 的结构被修改，会快速失败 (fast-fail)
HashMap的部分底层源码
public class HashMap<K,V> extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable {private static final long serialVersionUID = 362498820763181265L;// 默认初始容量，必须是 2 的幂static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16// 最大容量，如果任意一个带参数的构造函数隐式指定了更高的值，则使用该值// 必须是 2 的幂static final int MAXIMUM_CAPACITY = 1 << 30;// 在构造函数中没有指定负载因子时使用的默认值static final float DEFAULT_LOAD_FACTOR = 0.75f;// 对于一个桶，使用树而不是链表的节点数阈值// 当向具有至少这么多节点的桶中添加元素时，链表将被转换为树// 该值必须大于 2，并且应该至少为 8，以符合在移除树时关于收缩时转换回普通链表的假设// 简而言之，桶上的链表长度 >= 8 时，链表转化成红黑树（这只是条件之一）static final int TREEIFY_THRESHOLD = 8;// 在调整大小操作期间取消树化(拆分)结构的节点数阈值// 该值应该小于 TREEIFY_THRESHOLD，并且在去除时检测收缩最多6个网格// 简而言之，桶上的红黑树大小 <= 6 时，红黑树转化成链表static final int UNTREEIFY_THRESHOLD = 6;// 桶可以被树型化的最小数组容量。 (另外，如果一个桶中有太多节点，则会调整数组的大小)// 该值应该至少 4 * TREEIFY_THRESHOLD，以避免调整大小和树化阈值之间的冲突// 简而言之，当数组容量 >= 64 时，链表才会转化成红黑树（这只是条件之一）static final int MIN_TREEIFY_CAPACITY = 64;// 链表的节点static class Node<K,V> implements Map.Entry<K,V> {final int hash;final K key;V value;Node<K,V> next;Node(int hash, K key, V value, Node<K,V> next) {this.hash = hash;this.key = key;this.value = value;this.next = next;}public final K getKey() { return key; }public final V getValue() { return value; }public final String toString() { return key + "=" + value; }public final int hashCode() {return Objects.hashCode(key) ^ Objects.hashCode(value);}public final V setValue(V newValue) {V oldValue = value;value = newValue;return oldValue;}public final boolean equals(Object o) {if (o == this)return true;if (o instanceof Map.Entry) {Map.Entry<?,?> e = (Map.Entry<?,?>)o;if (Objects.equals(key, e.getKey()) &&Objects.equals(value, e.getValue()))return true;}return false;}}/* ---------------- Fields -------------- */// 存放数据的数组// 数组在第一次使用时初始化，并根据需要调整大小// 在分配时，长度总是2的幂，我们也在某些操作中允许长度为零，以允许当前不需要的自举机制transient Node<K,V>[] table;// 保存缓存了的 entrySet// 注意 AbstractMap 字段用于 keySet() 和 values()transient Set<Map.Entry<K,V>> entrySet;// 此 HashMap 中包含的键值映射的数量// 可能不准(因为当你拿到这个值的时候，可能又发生了变化)transient int size;// 结构修改是指：改变 HashMap 中映射的数量或以其他方式修改其内部结构(例如，rehash)// 该字段用于使 HashMap 的集合视图上的迭代器快速失败 (见ConcurrentModificationException)transient int modCount;// 下一个要调整大小的大小值(容量 * 负载因子)// javadoc的描述在序列化时是 true// 如果表数组还没有被分配，这个字段保存初始数组容量，或者零表示 DEFAULT_INITIAL_CAPACITY// 扩容的门槛，有两种情况// 如果初始化时，给定数组大小的话，通过 tableSizeFor 方法计算，数组大小永远接近于 2 的幂// 如果是通过 resize 方法进行扩容，大小 = 数组容量 * 0.75// 简而言之，当 HashMap 中键值对的数量(size) > threshold时，执行 resize() 扩容int threshold;// HashMap 的负载因子final float loadFactor;/* ---------------- Public operations -------------- */// 构造一个具有指定初始容量和负载因子的空 HashMappublic HashMap(int initialCapacity, float loadFactor) {if (initialCapacity < 0)throw new IllegalArgumentException("Illegal initial capacity: " +initialCapacity);if (initialCapacity > MAXIMUM_CAPACITY)initialCapacity = MAXIMUM_CAPACITY;if (loadFactor <= 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException("Illegal load factor: " +loadFactor);this.loadFactor = loadFactor;this.threshold = tableSizeFor(initialCapacity);}// 构造一个具有指定初始容量和负载因子为默认值(0.75)的空 HashMappublic HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR);}// 构造一个初始容量为默认值(16)，负载因子为默认值(0.75)的空 HashMappublic HashMap() {// all other fields defaulted// 所有其他字段均为默认值this.loadFactor = DEFAULT_LOAD_FACTOR;}// 构造一个负载因子为默认值(0.75)，足够的初始容量保存指定 Map 的 HashMappublic HashMap(Map<? extends K, ? extends V> m) {this.loadFactor = DEFAULT_LOAD_FACTOR;putMapEntries(m, false);}}
HashMap的新增
新增 key，value 大概的步骤示意图如下：
put() 的底层源码实现如下：
// 将指定值与此映射中的指定键关联// 如果之前的映射包含键的映射，那么旧的值将被替换public V put(K key, V value) {return putVal(hash(key), key, value, false, true);}// onlyIfAbsent：如果为true，则 key 存在时不更改原有值// 如果 HashMap 中已经存在 key 的映射，但不想覆盖 value，可以选择 putIfAbsent()// putIfAbsent() 调用 putVal() 时 onlyIfAbsent 为 true// evict：如果为 false 则表示 HashMap 处于创建模式// 返回旧值，如果没有则返回 nullfinal V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {// tab 的引用指向 table 数组（HashMap 中存放数据的数组）Node<K,V>[] tab;// p 为 i 下标位置的 Node 值Node<K,V> p;// n 表示数组的长度，i 为数组索引下标int n, i;// 如果数组为空，使用 resize() 初始化if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;// 如果当前索引位置是空的（桶中无节点），直接生成新的节点在当前索引位置上if ((p = tab[i = (n - 1) & hash]) == null)// newNode() {return new Node<>(hash, key, value, next);}tab[i] = newNode(hash, key, value, null);// 如果桶中有节点，解决 hash 冲突else {// e 为当前节点的临时变量// 如果 HashMap 中原本存在此 key 的映射，最终 e 为此 Node，否则为 nullNode<K,V> e; K k;// 如果 key 的 hash 和值都和 p 的相等，即 HashMap 中原本存在此 key 的映射// 直接把当前下标位置的 Node 值赋值给临时变量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) {// p.next == null 表明 p 是链表的尾节点if ((e = p.next) == null) {// newNode() {return new Node<>(hash, key, value, next);}p.next = newNode(hash, key, value, null);// 当链表的长度 >= 8 时，链表转红黑树if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}// 链表遍历过程中，发现 HashMap 中原本存在此 key 的映射if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;// 更改循环的当前元素，使 p 在遍历过程中，一直往后移动p = e;}}// 如果 e != null 说明 HashMap 中原本存在此 key 的映射if (e != null) { // existing mapping for keyV oldValue = e.value;// 当 onlyIfAbsent 为 false 时，才会覆盖值if (!onlyIfAbsent || oldValue == null)e.value = value;// 回调函数，允许 LinkedHashMap 后置操作// HashMap 中，此方法为抽象方法;// LinkedHashMap 中，如果 accessOrder == true ，此方法将当前节点移动到链表尾部afterNodeAccess(e);// 返回老值return oldValue;}}++modCount;// 如果 HashMap 的实际大小 > 扩容的门槛，开始扩容if (++size > threshold)resize();// 回调函数，允许 LinkedHashMap 后置操作// HashMap 中，此方法为抽象方法;// LinkedHashMap 中，如果 accessOrder == true ，此方法可能会删除头节点（满足一定条件）afterNodeInsertion(evict);return null;}// 初始化或双倍扩容// 如果数组为空，则按照字段 threshold 中持有的初始容量目标分配// 否则，因为我们使用的是 2 的幂展开，所以每个桶中的元素必须保持在相同的索引，或者在新表中以2的偏移量幂移动。// 该方法最终将成员属性 table,threshold 更新，并返回更新后的 tablefinal Node<K,V>[] resize() {// oldTab 负责持有旧数组对象 tableNode<K,V>[] oldTab = table;// oldCap 负责持有旧数组的大小（容量）int oldCap = (oldTab == null) ? 0 : oldTab.length;// oldThr 负责持有旧的扩容阈值 thresholdint oldThr = threshold;// newCap 负责保存新数组的容量// newThr 负责保存新数组的扩容阈值int newCap, newThr = 0;if (oldCap > 0) {// 老数组大小 >= 最大容量（1 << 30），则不扩容，并设置下一个要调整大小的大小值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}// 将容量大小扩为 threshold 的值，具体的扩容逻辑在下面代码// 有参构造时，oldCap == 0，不执行上面 if 逻辑，且 threshold > 0，// 所有只有有参构造初始化扩容时执行此 else if 逻辑else if (oldThr > 0) // initial capacity was placed in thresholdnewCap = oldThr;// 无参构造只设置了 loadFactor 为默认值(0.75)，threshold 取 int 的默认值 0// 无参构造时，oldCap = 0，所以：无参构造初始化扩容时执行此 else 逻辑代码else {// zero initial threshold signifies using defaults// 零初始阈值表示使用默认值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;@SuppressWarnings({"rawtypes","unchecked"})Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];table = newTab;if (oldTab != null) {for (int j = 0; j < oldCap; ++j) {Node<K,V> e;if ((e = oldTab[j]) != null) {// 将数组对象置空，让 GC 进行垃圾回收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 { // preserve order// 维持秩序// loHead 表示老值,老值的意思是：扩容后该链表中计算出索引位置不变的元素// hiHead 表示新值，新值的意思是：扩容后计算出索引位置发生变化的元素Node<K,V> loHead = null, loTail = null;Node<K,V> hiHead = null, hiTail = null;Node<K,V> next;// 规避了 Java8 版本以下的成环问题// java7 是在 while 循环里面，单个计算好数组索引位置后，单个的插入数组中，在多线程情况下，会有成环问题// java8 是等链表整个 while 循环结束后，才给数组赋值，所以多线程情况下，也不会成环do {next = e.next;if ((e.hash & oldCap) == 0) {if (loTail == null)loHead = e;elseloTail.next = e;loTail = e;}else {if (hiTail == null)hiHead = e;elsehiTail.next = e;hiTail = e;}} while ((e = next) != null);if (loTail != null) {loTail.next = null;newTab[j] = loHead;}if (hiTail != null) {hiTail.next = null;newTab[j + oldCap] = hiHead;}}}}}return newTab;}
红黑树新增节点过程
- 首先判断新增的节点在红黑树上是不是已经存在，判断手段有如下两种
如果节点没有实现 Comparable 接口，使用 equals 进行判断
如果节点自己实现了 Comparable 接口，使用 compareTo 进行判断 - 新增的节点如果已经在红黑树上，直接返回；不在的话，判断新增节点是在当前节点的左边
还是右边，左边值小，右边值大 - 自旋递归 1 和 2 步，直到当前节点的左边或者右边的节点为空时，停止自旋，当前节点即为
我们新增节点的父节点 - 把新增节点放到当前节点的左边或右边为空的地方，并于当前节点建立父子节点关系
- 进行着色和旋转，结束
putTreeVal() 的底层源码实现如下：
// 红黑树新增节点// tab：HashMap 中存放数据的数组// h：key 的 hash 值final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,int h, K k, V v) {Class<?> kc = null;boolean searched = false;// 找到根节点TreeNode<K,V> root = (parent != null) ? root() : this;// 自旋for (TreeNode<K,V> p = root;;) {int dir, ph; K pk;if ((ph = p.hash) > h)dir = -1;else if (ph < h)dir = 1;else if ((pk = p.key) == k || (k != null && k.equals(pk)))return p;else if ((kc == null &&(kc = comparableClassFor(k)) == null) ||(dir = compareComparables(kc, k, pk)) == 0) {if (!searched) {TreeNode<K,V> q, ch;searched = true;if (((ch = p.left) != null &&(q = ch.find(h, k, kc)) != null) ||((ch = p.right) != null &&(q = ch.find(h, k, kc)) != null))return q;}dir = tieBreakOrder(k, pk);}TreeNode<K,V> xp = p;if ((p = (dir <= 0) ? p.left : p.right) == null) {Node<K,V> xpn = xp.next;TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);if (dir <= 0)xp.left = x;elsexp.right = x;xp.next = x;x.parent = x.prev = xp;if (xpn != null)((TreeNode<K,V>)xpn).prev = x;moveRootToFront(tab, balanceInsertion(root, x));return null;}}}
HashMap的查找
HashMap 的查找主要分为以下三步：
- 根据 hash 算法定位数组的索引位置，equals 判断当前节点是否是要查找的 key，是的话直接返回，否则进行第二步
- 判断当前节点有无 next 节点，有的话判断是链表类型，还是红黑树类型
- 分别走链表和红黑树不同类型的查找方法
```java
// 返回指定键映射到的值，如果该映射不包含此键的映射，则返回 null
// 返回 null 并不一定表示不包含此键的映射，也有可能此键映射到 null
// 可用 containsKey() 操作区分以上两种情况
public V get(Object key) {
Node
@Override
// 如果 key 对应的值不存在，返回期望的默认值 defaultValue
public V getOrDefault(Object key, V defaultValue) {
Node
final Node
---红黑树查找的思路：1. 从根节点递归查找1. 根据 hashcode，比较查找节点，左边节点，右边节点之间的大小，根本红黑树左小右大的特性进行判断1. 判断查找节点在第 2 步有无定位节点位置，有的话返回，没有的话重复 2，3 两步1. 一直自旋到定位到节点位置为止如果红黑树比较平衡的话，每次查找的次数就是树的深度<a name="J08qi"></a># HashMap的删除```javapublic V remove(Object key) {Node<K,V> e;return (e = removeNode(hash(key), key, null, false, true)) == null ?null : e.value;}final Node<K,V> removeNode(int hash, Object key, Object value,boolean matchValue, boolean movable) {Node<K,V>[] tab; Node<K,V> p; int n, index;if ((tab = table) != null && (n = tab.length) > 0 &&(p = tab[index = (n - 1) & hash]) != null) {Node<K,V> node = null, e; K k; V v;if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))node = p;else if ((e = p.next) != null) {if (p instanceof TreeNode)node = ((TreeNode<K,V>)p).getTreeNode(hash, key);else {do {if (e.hash == hash &&((k = e.key) == key ||(key != null && key.equals(k)))) {node = e;break;}p = e;} while ((e = e.next) != null);}}if (node != null && (!matchValue || (v = node.value) == value ||(value != null && value.equals(v)))) {if (node instanceof TreeNode)((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);else if (node == p)tab[index] = node.next;elsep.next = node.next;++modCount;--size;afterNodeRemoval(node);return node;}}return null;}
HashMap的迭代器
Map 对 key、value 和 entity（节点） 都提供了迭代的方法，假设我们需要迭代 entity，就可使用 HashMap.entrySet().iterator(); 直接返回 HashIterator。
HashMap 的迭代器源码实现如下：
abstract class HashIterator {// 下一个要返回的节点Node<K,V> next; // next entry to return// 当前节点，用于 remove()Node<K,V> current; // current entry// 期待的版本号int expectedModCount; // for fast-fail// 当前槽int index; // current slotHashIterator() {expectedModCount = modCount;Node<K,V>[] t = table;current = next = null;index = 0;// 将成员属性 next 指向第一个节点if (t != null && size > 0) { // advance to first entrydo {} while (index < t.length && (next = t[index++]) == null);}}public final boolean hasNext() {return next != null;}final Node<K,V> nextNode() {Node<K,V>[] t;Node<K,V> e = next;// 如果存在并发修改，则抛出 ConcurrentModificationExceptionif (modCount != expectedModCount)throw new ConcurrentModificationException();if (e == null)throw new NoSuchElementException();// 将成员属性 next 指向下一个节点// 如果 e.next 为 null，代表槽中只有一个节点 || 节点 e 为槽中最后一个节点if ((next = (current = e).next) == null && (t = table) != null) {// 成员属性 next 指向下一个槽中的第一个节点do {} while (index < t.length && (next = t[index++]) == null);}return e;}// 移除当前节点public final void remove() {Node<K,V> p = current;if (p == null)throw new IllegalStateException();// 如果存在并发修改，则抛出 ConcurrentModificationExceptionif (modCount != expectedModCount)throw new ConcurrentModificationException();// 将当前节点置为 nullcurrent = null;K key = p.key;removeNode(hash(key), key, null, false, false);expectedModCount = modCount;}}final class KeyIterator extends HashIteratorimplements Iterator<K> {public final K next() { return nextNode().key; }}final class ValueIterator extends HashIteratorimplements Iterator<V> {public final V next() { return nextNode().value; }}final class EntryIterator extends HashIteratorimplements Iterator<Map.Entry<K,V>> {public final Map.Entry<K,V> next() { return nextNode(); }}
HashMap的常见问题
说一下你对 HashMap 的了解
底层数据结构
HashMap 在 Java7 及之前版本底层数据结构是：数组 + 链表。
HashMap 在 Java8 及之后版本底层数据结构是：数组 + 链表 + 红黑树。
构造器相关
HashMap 的构造器的代码逻辑就是：给成员属性 loadFactor、threshold 赋值。
HashMap 和 ArrayList 类似，都是在第一次 add 时，才会执行初始化扩容操作。
说一下HashMap底层数据结构
答：HashMap 底层是数组 + 链表 + 红黑树的数据结构，数组的主要作用是方便快速查找，时间复杂度是 O(1)，数组默认大小是 16，数组的下标索引是通过 key 的 hashcode 计算出来的，数组元素叫做 Node，当多个 key 的 hashcode 一致，但 key 值不同时，单个 Node 就会转化成链表，链表的查询复杂度是 O(n)，当链表的长度 >= 8 并且数组的大小 > 64 时，链表就会转化成红黑树，红黑树的查询复杂度是 O(log(n))，简单来说，最坏的查询次数相当于红黑树的最大深度。
说一下HashMap的初始容量问题
不论传入的是否是 2 的幂次方，最终都会转化为 2 的幂次方。
说一下HashMap的hash算法
说一下HashMap中hash冲突时怎么办
答：hash 冲突指的是 key 值的 hashcode 计算相同，但 key 值不同的情况。
如果桶中元素原本只有一个或已经是链表了，新增元素直接追加到链表尾部；
如果桶中元素是链表，并且链表个数 >= 8 时，此时有两种情况：
- 如果数组大小 < 64，数组再次扩容，链表不转化成红黑树
- 如果数组大小 >= 64 时，链表就会转化成红黑树
这里不仅判断链表个数 >= 8，还判断了数组大小，数组容量 < 64 没有立即转化的原因，猜测主要是因为： 红黑树占用的空间比链表大很多，转化也比较耗时，所以数组容量小的情况下冲突严重，先尝试扩容，看能否通过扩容来解决冲突严重的问题
说一下HashMap是如何扩容的
答：扩容的时机
put 时，发现数组为空，进行初始化扩容
- 若在构造器中指定了初始容量，
threshold = 指定初始容量;则扩容为指定容量，且新threshold = 负载因子 * 指定初始容量（初始化时，会通过一个函数保证 throeshold一定为 2 次幂） - 若在构造器中未指定初始容量，则
threshold = 0;(基本数据类型的默认值) 默认扩容大小为 16，且新threshold = 0.75 * 16
put 成功后，发现现有数组大小 (size) > 扩容的门槛时 (threshold)，进行扩容，扩容为旧数组大小的 2 倍，且 新threshold = 旧threshold << 1
新数组初始化之后，需要将老数组的值拷贝到新数组上，链表和红黑树都有自己拷贝的方法。
链表个数 >= 8 时，链表要转化成红黑树的原因
这个问题的答案在源码注释中有说明
TREEIFY_THRESHOLD == 8 ，而不是更大或者更小的原因
在链表数据不多的时候，使用链表进行遍历也比较快，只有当链表数据比较多的时候，才会转化成红黑树，但红黑树需要占用的空间是链表的 2 倍，考虑到转化时间和空间损耗，所以我们需要定义出一个较大的转化的边界值。
在考虑设计 8 这个值时，我们参考了泊松分布概率函数，由泊松分布中得出结论，链表各个长度的命中概率为：
1: 0.30326533 2: 0.07581633 3: 0.01263606
4: 0.00157952 5: 0.00015795 6: 0.00001316
7: 0.00000094 8: 0.00000006
意思是，当链表的长度是 8 的时候，出现的概率是 0.00000006，不到千万分之一，大概为 
如果 TREEIFY_THRESHOLD 设置更大的话，满足链表转化成红黑树的概率更低，几乎不存在转化情况，那么设置 链表转化红黑树的逻辑代码就没有意义了。
链表转化成红黑树的原因
当链表个数太多，遍历可能比较耗时，转化成红黑树，可以使遍历的时间复杂度降低。
链表查询的时间复杂度是 O (n)，红黑树的查询复杂度是 O (log (n))。
但转化成红黑树，有空间和转化耗时的成本，我们通过泊松分布公式计算，正常情况下链表个数出现 8 的概率不到千万分之一，所以说正常情况下，链表的长度几乎不可能达到 8 ，而一旦到达 8 时，很有可能是 hash 算法出了问题，为了在这种情况下，让 HashMap 仍然有较高的查询性能，所以让链表转化成红黑树。
延伸问题：红黑树什么时候转变成链表
答：当节点的个数 <= 6 时，红黑树会自动转化成链表，主要还是考虑红黑树的空间成本问题，当节点个数 <= 6 时，遍历链表也很快，所以红黑树会重新变成链表。
HashMap的死循环问题
在 JDK7 上 HashMap 数据迁移时，会导致结点翻转，多线程操作时，可能会引发死循环 在 JDK8 上修改了数据迁移的算法，保证数据的顺便，不会出现死循环问题
Java7 及之前版本的 HashMap 采用的是头插法，即解决 hash 冲突时，将新节点作为头节点。
Java8 及之后版本的 HashMap 采用的是尾插法，即解决 hash 冲突时，将新节点作为尾结点。
Java7 及之前版本的 HashMap 被多个线程同时操作可能存在死循环的问题
Java7 的 put() 源码实现如下：
public V put(K key, V value) {if (key == null)return putForNullKey(value);// 算 Hash 值int hash = hash(key);// 确定数组索引位置int i = indexFor(hash, table.length);// 如果该 HashMap 中存在该 key 的映射，则替换旧的 valuefor (Entry<K,V> e = table[i]; e != null; e = e.next) {Object k;if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {V oldValue = e.value;e.value = value;e.recordAccess(this);return oldValue;}}modCount++;// 如果该 HashMap中不存在该 key 的映射，则新增一个节点addEntry(hash, key, value, i);return null;}// 将具有指定键、值和哈希码的新项添加到指定的存储桶中// 如果合适的话，该方法负责调整表的大小// 子类重写该方法以更改put方法的行为void addEntry(int hash, K key, V value, int bucketIndex) {if ((size >= threshold) && (null != table[bucketIndex])) {resize(2 * table.length);hash = (null != key) ? hash(key) : 0;bucketIndex = indexFor(hash, table.length);}createEntry(hash, key, value, bucketIndex);}// 将该 HashMap 重新散列到具有更大容量的新数组中// 当 HashMap 中的键数达到其阈值时，将自动调用此方法// 如果当前容量为 MAXIMUM_CAPACITY，则不调整 HashMap 的大小，而是将阈值设置为 Integer.MAX_VALUEvoid resize(int newCapacity) {Entry[] oldTable = table;int oldCapacity = oldTable.length;if (oldCapacity == MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return;}Entry[] newTable = new Entry[newCapacity];boolean oldAltHashing = useAltHashing;useAltHashing |= sun.misc.VM.isBooted() &&(newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);boolean rehash = oldAltHashing ^ useAltHashing;transfer(newTable, rehash);table = newTable;threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);}// 将所有 Entry 从当前表转移到 newTablevoid transfer(Entry[] newTable, boolean rehash) {int newCapacity = newTable.length;for (Entry<K,V> e : table) {while(null != e) {Entry<K,V> next = e.next;if (rehash) {e.hash = null == e.key ? 0 : hash(e.key);}// 死循环问题就出现在下面这四行代码上int i = indexFor(e.hash, newCapacity);e.next = newTable[i];newTable[i] = e;e = next;}}}
发生死循环情况（只要转移后 e2 和 next2 又进到了同一个桶里，就）：
当两个线程 t1、t2 同时进行 put() 操作，有可能出现两个线程都进行 resize() 扩容操作，当两个线程同时走到了 transfer() 后。
假设：线程 t2 执行到 transfer() 循环中的 Entry<K,V> next = e.next; 然后被调度挂起，接着线程 t1 完成 transfer() 转移操作。
此时 t2 被挂起后 table 情形如左下图所示，t1 完成 transfer() 转移操作后情形如右下图所示（只要转移后 e2 和 next2 又进到了同一个桶里，就一定会发生死循环）：
t2 被调度回来继续执行 e.next = newTable[i]; 后，此时线程 t1、t2 情形如左下图所示，执行 e = next;后，情形如右下图所示：
进行第二轮循环后，情形如下图所示：
当第三轮循环执行到 e.next = newTable[i];，情形如下图所示（链表已经形成环状）：
若有收获，就点个赞吧
0 人点赞
