说一说 HashMap 的工作原理

HashMap 是一种 KV 形式的数据结构，允许有一个 key 为 null，value 允许为 null。HashMap 的存储，使用的是哈希表，将 key 通过 Hash 函数运算之后，会获得一个存储键值对的位置。多个 key 经过 Hash 函数之后，计算得到的存储位置很有可能是相同的，这就叫做哈希冲突。

解决哈希冲突有多种方法，比如说开放地址发、再哈希法，以及链地址法。HashMap 就是采用链地址法来解决哈希冲突的。链地址法会在发生哈希冲突的时候，在数组的后面挂上一个链表，还有冲突就继续增加链表的长度。

Java 实现 HashMap 的时候，对链地址法进行了优化。Java8 在链表长度达到 8 的时候，会将链表转换为红黑树，因为查找链表的时间复杂度是 O(n)，而查找红黑树的时间复杂度是 O(logN)。

最后，由于 HashMap 的存储使用了数组，所以说，在其容量不足的情况下，肯定要涉及到扩容的操作。

总结，哈希表 => 链地址法 => 数组+链表/红黑树 => 扩容 => put()、get()、resize()。

以上。

再补充一下：HashMap 计算数组下标的方法，总共分成了 3 步：

1. 获取 key 的 hashCode 值；
2. 做移位运算，再让高位以地位做异或操作；
3. (n-1)&hash 计算出最终下标位置。

为什么要这么做呢？其实原因是要和操作步骤反着来看的：

1. HashMap 保证成倍扩容，在这个前提下，从数学上保证 (n-1)&hash 等效于取余操作
2. n-1是一个不大的数字，直接与 key 的 hashCode 做 & 操作，就只有 hashCode 的地位参与了运算。而我们使用 Hash 函数，希望 Hash 散列能够尽可能地均匀。
3. 所以才会加上一个移位运算h = key.hashCode()) ^ (h >>> 16，这样计算出来的 hash 值，是高位与地位做异或操作得到的。相当于在做 (n-1)&hash 时，key 的高位也参与到了运算中。