HashMap

JDK 7 中 HashMap 的数据结构是数组+链表。

JDK 8 中 HashMap 的数据结构是数组+链表+红黑树。

它在链表长度大于8且数组长度大于64时候会把链表转换成红黑树

HashMap 的初始容量是 16，随着元素的不断添加，HashMap 就需要进行扩容，阈值是capacity * loadFactor，capacity 为容量，loadFactor 为负载因子，默认为 0.75。

扩容后的数组大小是原来的 2 倍，然后把原来的元素重新计算哈希值，放到新的数组中。

负载因子（load factor）是一个介于 0 和 1 之间的数值，用于衡量哈希表的填充程度。它表示哈希表中已存储的元素数量与哈希表容量之间的比例。

负载因子过高（接近 1）会导致哈希冲突增加，影响查找、插入和删除操作的效率。
负载因子过低（接近 0）会浪费内存，因为哈希表中有大量未使用的空间。

HashMap 的put过程：

1.他会先对key计算扰动hash，通过key.hashCode() ^ (key.hashCode() >>> 16)计算，这样的目的是为了高16位的熵混进去低16位，减少碰撞。

2.判断当前是不是第一次添加是的话就创建一个默认长度16，负载因子0.75的数组。

3.开始计算数组下标index，通过前面计算的hash & (n - 1)来确定位置这里的n是2的次幂

4.然后获取当前数组中对应的数据

5.数组为空，底层会创建一个键值对对象，直接放进去就行了

6.不为空

6.1.如果当前插入的键值对与数组的键值对哈希值一样，也就是插入的键值与插入后的键值一样就把调整当前元素指针，在后面进行替换操作

6.1.已经是TreeNode，走红黑树的添加或更新逻辑

6.2.是普通Node，走链表的添加或更新逻辑，如果达到树化条件，走树化逻辑

添加后、返回前检查容量是否达到扩容阈值，如果达到，进行扩容

为什么HashMap的容量是2的n次方

1.用位运算 `(n - 1) & hash` 快速代替取模 `% n`

在n为偶数时候 n - 1为奇数（n - 1）& hash等价于 hash % n 并且位运算比取模快得多

2.保证哈希值在桶上的分布尽可能均匀，避免部分桶永远用不到

2 幂次方刚好是偶数，偶数-1 是奇数，奇数的二进制最后一位是 1，也就保证了 hash &(length-1) 的最后一位可能为 0，也可能为 1（取决于 hash 的值），这样可以保证哈希值的均匀分布。

3.方便扩容时用 `oldCap` 这一位快速判断元素新位置（JDK1.8 的优化）

桶里每个节点的新位置只和这一位有关：

// oldCap 一定是 2 的幂，比如 16(10000b)
if ((hash & oldCap) == 0) {
    // 这位是 0：留在原来的 index
    newIndex = oldIndex;
} else {
    // 这位是 1：去到 index + oldCap
    newIndex = oldIndex + oldCap;
}

JDK 1.8 扩容时利用 hash & oldCap 这位来判断元素是留在原索引还是移动到 index + oldCap，极大简化了 rehash 的过程，这个优化也依赖容量是 2 的幂。

重写HashMap的equal和hashcode方法需要注意什么？

如果o1.equals(o2)，那么o1.hashCode() == o2.hashCode()总是为true的。
如果o1.hashCode() == o2.hashCode()，并不意味着o1.equals(o2)会为true。

HashMap 的扩容机制和扩容过程（JDK1.8）

1）何时扩容？

有个阈值：threshold = capacity * loadFactor
- 默认：capacity = 16，loadFactor = 0.75
- 所以初始 threshold = 12
当 size > threshold 时，进行扩容：
- 数组长度 ×2，比如 16 -> 32。

2）扩容过程（`resize()`）

创建一个新数组 newTable，长度 = 原来 2 倍。
遍历旧数组每个桶：
- 如果桶为空，跳过。
- 如果桶里只有一个节点，直接搬到新数组对应位置。
- 如果桶是红黑树，拆成两棵或调整后搬到新数组中。
- 如果桶是链表：
  - JDK1.8 做了一个优化：
    - 利用 e.hash & oldCap 的结果来判断节点在新数组中的位置：
      - 如果为 0：节点留在原位置 index。
      - 如果为 1：节点去到 index + oldCap。
  - 这样链表可以拆成两个链表，过程更快，也避免 1.7 里“倒序 + 死循环”的问题。

扩容是最重的操作：需要重新分布所有元素，所以尽量别频繁扩容（比如一开始就知道大概数量，可以传一个合适的 initialCapacity）。

HashMap 出现 Hash 冲突时怎么办？何时链表进化成红黑树？何时退化？

1）hash 冲突的解决方式

HashMap 使用的是 “拉链法”：
- 数组 + 链表/红黑树。
- 同一个桶上的多个元素通过 next 指针连成一条链，或组织成一棵红黑树。

2）链表 -> 红黑树（树化）的条件（JDK1.8）

满足 两个条件 才会树化：

单个桶中的链表长度 ≥ TREEIFY_THRESHOLD（默认 8）。
整个 table 的长度 ≥ MIN_TREEIFY_CAPACITY（默认 64）。

不满足第二个条件时，会优先选择扩容而不是树化。

原因：

如果表太小，说明整体碰撞重；这时扩容可以让数据分摊到更多桶里，比急着树化更划算。

3）红黑树 -> 链表（退化）的条件

当树中的节点个数 ≤ UNTREEIFY_THRESHOLD（默认 6）时，
remove树节点时，如果root、root.left、root.right、root.left.left有一个为null（在移除之前检查），也会退化成链表

JDK8为什么改用尾插法？

JDK8引入了红黑树，那么就可以插入时顺便遍历一遍当前桶有多少元素，决定是否转为红黑树
避免多线程下扩容可能产生的死循环

扩容的时候每个节点都要进行位运算吗？

不需要。HashMap 会通过 (e.hash & oldCap) 来判断节点是否需要移动，0 的话保留原索引；1 才需要移动到新索引（原索引 + oldCap）。

这样就避免了 hashCode 的重新计算，大大提升了扩容的性能。

所以，哪怕有几十万条数据，可能只有一半的数据才需要移动到新位置。另外，位运算的计算速度非常快，因此，尽管扩容操作涉及到遍历整个哈希表并对每个节点进行判断，但这部分操作的计算成本是相对较低的。

String的hashCode()如何设计的，为啥每次乘的是31

字符串中的每个字符都可以表现为一个数字，称为Si，其中i的范围是0 ~ n - 1
散列公式为：S0 * 31 ^ (n - 1) + S1 * 31 ^ (n - 2) + S2 * 31 ^ (n -3) + … + Sn-1 * 31 ^ (0)
31代入公式有较好的散列特性，并且31 * h可以被优化为 h << 5 - h
但这算法时间复杂度o(n)

哈希冲突解决方法:

拉链法:哈希冲突时，同一个哈希槽拉成一个链表，HashMap采用该方法开放寻址:寻找其他位置，这就保证了一个哈希槽最多存有一个元素线性探测:哈希冲突时，按顺序往后查找，直到找到第一个为空的槽位，ThreadLocalMap采用该方法二次探测:与线性探测类似，但有规律，比如每次步长是1，2，4，8，16。。。再哈希法:哈希冲突时，换个哈希函数再次哈希