[HashMap源码学习之路]---hashcode的作用及数组长度为什么是2的n次幂

你的名字 2023-10-17 22:43 36阅读 0赞

## HashMap中的hashcode作用 ##

HashMap是`Java` 中很重要的一个概念，工作中使用的频率也非常广泛，需要对其进行了解。  
  看源码是很枯燥的，但是看懂了，却有种豁然开朗的感觉，觉得特别棒，本篇只说`hashcode的作用及数组长度为什么是2的n次幂`。  
  首先点开HashMap的类，我是用开发工具`idea` ，新建了一个HashMap，点进去找到put方法。以jdk 1.8为例，如下：

public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

然后再点进`putVal` 方法，则会看到有下面的代码：

tab[i = (n - 1) & hash]

##### 1、`HashMap` 中为什么需要一个`hashCode` 值？ #####

原因就是需要用它来对`HashMap` 数组的位置来定位，如果向`HashMap` 里存一个数，单纯的依次使用`equals` 方法比较`key` 是否相同来确定当前数据是否已存储过，那效率非常低，而通过比较`hashCode` 值，效率就会大大提高，那它是如何定位数组位置呢，如果你使用的是jdk 1.8，那在`put方法中的putVal方法里会看到`如下内容：

对于上边的`n-1` 后边会说到，先说一下上边的写法，`&` 为二进制中的`与运算` ，它的运算特点是，两个数进行`&` ，如果都为1，则运算结果为1，否则为0。  
  因为`hashMap` 的数组长度都是`2的n次幂` ，那么对于这个数再减去1，转换成二进制的话，就肯定是最高位为`0`，其他位全是`1` 的数，那以数组长度为8为例（默认HashMap初始数组长度是16），那`8-1` 转成二进制的话，就是`0111` 。  
  那我们举一个随便的`hashCode`值，与`0111` 进行`与运算` 看看结果如何，如下：

第一个key：      hashcode值：10101000    
       与0111进行&运算        &       0111                                      
                                     0000  （十进制为0）
       ------------------------------------------               
     第二个key：      hashcode值：11101000    
       与0111进行&运算        &       0111      
                                     0000  （十进制为0）
     --------------------------------------------               
     第三个key：      hashcode值：11101010    
       与0111进行&运算        &       0111      
                                     0010  （十进制为2）

你可以随便变`hashcode` 值来测试，最终得到的数都会`小于8` ,当然会像上边一样，出现相同的数据，那样的话，就会以链表的形式存在那个数组元素上了。  
  回过头来再设想一下，那我们就可以通过把`key`转为`hashCode`值，然后与数组长度进行`与运算` ，来确定`HahsMap` 中当前`key对应的数据在数组中的位置` 。  
  原本，需要查找数组下的每个元素，以及他们对应的链，疯狂的调用`equals` 方法，誓死遍历出数据的方式，变成了仅仅是查找数组下的一个元素，然后，只需要`equals` 比较这一条链上的数据就可以了，这样`equals` 的使用次数降低了很多。  
  通过上边的说明，不知道大家是否理解到了`hashCode` 值，在`HashMap` 中的作用呢？

##### 2、为什么`hashMap` 的数组长度为`2的n次幂`？ #####

还是上边那行代码：

tab[i = (n - 1) & hash]

我们知道了`&` 的作用，但是`n-1` 到底是什么意思呢？  
其实上边，已经提到过了，就是`2的n次幂` 是很特殊的数，随便满足这个条件的数，对它减去1，转换成二进制，都会有这样的特点，即，`最高位为0，其他低位全为1` 。  
  就以数组长度分别为`8`和`7` 为例，看下边的情况：

###### 数字8减去1转换成二进制是`0111`，即下边的情况 ######

第一个key：      hashcode值：10101001    
       与0111进行&运算        &       0111                                      
                                     0001  （十进制为1）
       ------------------------------------------                           
     第二个key：      hashcode值：11101000    
       与0111进行&运算        &       0111      
                                     0000  （十进制为0）
    --------------------------------------------               
     第三个key：      hashcode值：11101110    
       与0111进行&运算        &       0111      
                                     0110  （十进制为6）

这样得到的数，就会完整的得到`原hashcode` 值的低位值，不会受到与运算对数据的变化影响。

###### 数字7减去1转换成二进制是`0110`，即下边的情况 ######

第一个key：      hashcode值：10101001    
       与0111进行&运算        &       0110                                      
                                     0000  （十进制为0）
       ------------------------------------------                           
     第二个key：      hashcode值：11101000    
       与0111进行&运算        &       0110      
                                     0000  （十进制为0）
    --------------------------------------------               
     第三个key：      hashcode值：11101110    
       与0111进行&运算        &       0111      
                                     0110  （十进制为6）

通过上边可以看到，当数组长度不为`2的n次幂` 的时候，`hashCode` 值与数组长度减一做`与运算` 的时候，会出现重复的数据，因为不为`2的n次幂` 的话，对应的二进制数肯定有一位为`0` ,这样，不管你的`hashCode` 值对应的该位，是`0` 还是`1` ,最终得到的该位上的数肯定是`0` ，这带来的问题就是`HashMap` 上的数组元素分布不均匀，而数组上的某些位置，永远也用不到。如下图所示：  
![这里写图片描述][70]  
  这将带来的问题就是你的`HashMap` 数组的利用率太低，并且链表可能因为上边的`(n - 1) & hash` 运算结果碰撞率过高，导致链表太深。（当然jdk 1.8已经在链表数据超过8个以后转换成了红黑树的操作，但那样也很容易造成它们之间的转换时机的提前到来）。  
  以上即是我理解的`HashMap`这方面的知识。

[70]: https://img-blog.csdn.net/20180723131422975?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvaGFxaXlp/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70