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);
    }

源码解读：

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

1111 1111 1111 1111 1111 1010 0111 1100

0000 0000 0000 0000 1111 1111 1111 1111

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

异或运算的结果为：

1111 1111 1111 1111 0000 0101 1000 0011

为什么要对这个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，备注- 技术交流 。或关注微信公众号【码上遇见你】。