HashMap | 利用白话文讲解其底层知识点

你知道 HashMap 底层的数据结构是什么吗？

简单来说是底层最核心的是一个数组，首先它会对 key 进行一个 hash 计算，然后根据这个 hash 值对数组进行取模(取模的结果一定是在 0～数组的长度之间)，就会定位到数组里的一个下标为index位置上。

JDK1.8 中对 Hash 算法和寻址算法是如何优化的。

首先来说 Hash 算法：

先看源码：

 /* ---------------- Static utilities -------------- */
    /**     * Computes key.hashCode() and spreads (XORs) higher bits of hash     * to lower.  Because the table uses power-of-two masking, sets of     * hashes that vary only in bits above the current mask will     * always collide. (Among known examples are sets of Float keys     * holding consecutive whole numbers in small tables.)  So we     * apply a transform that spreads the impact of higher bits     * downward. There is a tradeoff between speed, utility, and     * quality of bit-spreading. Because many common sets of hashes     * are already reasonably distributed (so don't benefit from     * spreading), and because we use trees to handle large sets of     * collisions in bins, we just XOR some shifted bits in the     * cheapest possible way to reduce systematic lossage, as well as     * to incorporate impact of the highest bits that would otherwise     * never be used in index calculations because of table bounds.     */    static final int hash(Object key) {        int h;        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);    }

源码解读：

1. 首先就是先拿到 key 的 HashCode，然后对 hashCode 做了一个二进制的位运算(右移 16 位)

假设有这样一个 key 的 hash 值转换为二进制后的结果是：

1111 1111 1111 1111 1111 1010 0111 1100

2. 上面这个做二进制右移 16 位也就是

0000 0000 0000 0000 1111 1111 1111 1111

简单来说也就是把原有的二进制右移 16 位，右移 16 位后就需要把高 16 位使用 0 站位，原有的高 16 位向后移动 16 位即可(上述例子比较特殊总共是 32 位，也就是高 16 位直接变成了低 16 位)

3. 紧接着就需要将原有的二进制和右移 16 位的二进制进行异或运算。

异或运算的结果为：

1111 1111 1111 1111 0000 0101 1000 0011

4. 最后将异或运算的结果转换为int值返回。

为什么要对这个 key 进行一个二进制的处理？具体优化的点在哪里？

这就需要结合 HashMap 的寻址算法来讲解，之前我们提到说是当 HashMap put 一个值的时候其操作就是计算 hashCode 并对数组的长度取模，定位到数组的一个位置，塞进去就可以了。 这里其实没有那么简单。它的寻址算法也做了一些优化，它并不是直接让你的 hash 值对数组的长度取模，而是让你的 hash 值的二进制进行优化后(也就是上面的经过右移 16 位后并进行了异或运算)再与这个数组的长度减一然后再进行一个与运算(&)。

为什么要进行一个与运算呢？

取模运算性能相对比较差一些，为了优化数组寻址的这个过程，就修改成了用这个 hash 值与数组长度的 n-1 进行与运算。在这里与运算的效果和取模的效果是一样的。这里有一个数学的知识点就是：一个数对2^n取模 == 一个数和 (2^n – 1)做按位与运算

X % 2^n = X & (2^n – 1) 2^n 表示 2 的 n 次方

假设我们如果不使用优化后的 hash 值的二进制位的话，在某些情况下与数组的长度(n-1)进行与运算，有可能意味着高 16 位之间的与运算是可以忽略的。核心的点在于低 16 位的与运算。这样就等于 hash 值的二进制的高 16 位没有参与到与运算里面。这样会有一个问题：两个二进制在比较特殊的情况下两个低 16 位比较相似，导致与数组长度计算的结果可能会很相近。 而优化后的低 16 位是融合了高 16 位的元素的。这样其实避免了 hash 冲突。因为 hash 值一旦一样就会产生这样的问题。

为什么与运算要比取模运算的效率高？

总的来说，因为它可以直接在 CPU 的硬件电路上执行，而取模运算需要转换成 10 进制再运算。与运算比取模运算更高效，因为它基于位操作，利用了硬件支持、简单的操作和数学性质。当需要对位进行逻辑操作或执行对 2 的幂次方取模等操作时，与运算是一种更好的选择。然而，需要根据具体的情况和需求来选择合适的运算操作。

HashMap 性能优化小结：

Hash 算法的优化主要表现在对每个 Hash 值，在它的低 16 位中，让高低 16 位进行了异或运算，让它的低 16 位融合了高低 16 位的特征。从而尽量避免一些可能会出现的 hash 冲突，会导致元素进入数组的同一个位置

寻址算法的优化：使用与运算代替了取模，提升性能。

简单来说就是 HashMap 在 put、get 的时候进行了 hash 算法的优化，避免了 hash 冲突，同时寻址算法也进行了优化。

HashMap 是如何解决 Hash 碰撞的问题的？

首先要知道什么是 Hash 碰撞，通俗的讲就是当两个 key 运算出来的 hash 值与数组长度 n-1 进行与运算之后发现定位出来的位置是一样的。这就是 Hash 碰撞、Hash 冲突。

HashMap 是通过在两个 key 计算出的同一个位置上挂一个链表，在这个链表放入多个元素。让多个 key-value 对，同时放在数组的同一个位置上。

后面在 get 的时候，如果发现该位置挂了一个链表，只要遍历这个链表找到自己的 key-value 就可以了。

这里就会有一个性能问题？

假设你的链表随着时间的推移变得很长，在后续遍历的时候，性能就会比较差，时间复杂度是 O(n)。所以 HashMap 做了一个优化，如果链表达到了一定的长度之后，会将其转换为红黑树，红黑树的好处就是遍历的时候时间间复杂度是 O(logn)，性能会比链表高一些。

为什么采用红黑树而不采用其他数据结构。

以典型的 AVL 树为例，AVL 树是一种高度平衡的二叉树，所以查找效率非常高，但是有就有弊，AVL 树为了维持这种高度的平衡，就要付出很大的代价，就是每次插入、删除都要做调整，比较复杂且耗时，所以综合考虑虽然红黑树读取略逊于 AVL 树，但是维护强于 AVL，空间开销与 AVL 类似，内容极多时略优于 AVL，维护优于 AVL，所以红黑树是有着良好的稳定性和完整的功能综合实力强，在诸如 STL 的场景中需要稳定的表现。

HashMap 是如何扩容的

说到扩容就要提到 rehash 的概念。rehash 的过程可以保证 HashMap 的性能，当 HashMap 中的元素数量过多时，rehash 可以提高 HashMap 的查找效率。

当 HashMap 中的元素数量超过了负载因子``（load factor）乘以容量时，就会触发扩容操作，这个过程涉及到重新计算元素的哈希值和确定在新数组中的位置。

在扩容的时候会创建一个新的两倍大小的数组（默认情况下，HashMap的初始容量是16，扩容时将容量翻倍，同时也会进行 rehash，假设在为扩容之前在同一个位置上有 3 个元素(使用链表进行处理)，扩容之可能就在不同的位置上了。扩容的时候会将元素与新的数组长度进行与运算。重新定义在元素在新数组长度的具体哪个位置。这里有一个规律是如果与运算的结果中多出来了一个 bit 的 1，那么 idnex 就等于index+oldCap，如果没有多的话那还是原来的 index。通过这个方式就避免了在 rehash 的时候位运算。从而提高 rehash 的效率。

如有问题，欢迎加微信交流：w714771310，备注- 技术交流 。或关注微信公众号【码上遇见你】。