[HashMap源码学习之路]---put方法中的hash方法介绍

我会带着你远行 2023-10-17 22:48 48阅读 0赞

### HashMap中的put方法中的hash方法 ###

以下是put方法的代码：

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

当我第一次看到这个地方的时候，首先好奇的是这个`hash` 方法到底干了什么，于是我点了进去，看到下边这样的东西，顿时懵了：

static final int hash(Object key) {
            int h;
            return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
        }

我懵的原因是因为我看到了`^` 、`16` ，这俩东西。到底是什么原因要做这样的操作呢？  
  在此之前，我们需要了解`hashCode` 是干嘛的，在上一篇文章里，我有写过关于`hashCode在HashMap中充当的作用` ，想了解的可以看这篇[\[HashMap源码学习之路\]—hashcode的作用及数组长度为什么是2的n次幂][HashMap_hashcode_2_n]  
  首先，说一下这个数字`16` ，对于我们得到的`hashCode` 值，它是`int` 类型，而`int` 类型，最大数转换成二进制的长度是`32` 位，对于它的一半是`16` ,这个概念，没毛病吧？  
![这里写图片描述][70]  
  那上边的`h>>>16` 换句话说，就是将int类型右移`16` 位，那对于这样的操作，我们会得到这个`int` 类型数的一个高`16` 位的数。举一个小的例子，比如右移`2` 位，以数字11为例，转换成2进制是`1011` ，它右移`2` 位，就是`0010`，具体如下：

11[十进制]  >>>2
    相当于 
    1011[二进制]  >>>2
    1011[二进制]  >>>2 右移2位
    会只剩下高2位数，即 0010[二进制]

再回到我们上边的代码，即：

(h = key.hashCode()) ^ (h >>> 16)

也就是说它这一步是将得到的`hashCode`值，对`高16位` （右移了16位得到的），然后再与原来的`hashCode` 值进行了`^` 运算。  
![这里写图片描述][70 1]  
  暂时再补充一点`^` 的介绍，它叫做`异或运算` ，关于异或运算的特点，可以看我的这个文章[java中异或运算的应用][java]，最好是百度一下这个，我也是百度的。这里只需要知道这样的特点即可：

异或的运算方法是一个二进制运算： 
    　　1^1=0 
    　　0^0=0 
    　　1^0=1 
    　　0^1=1 
    　　两者相等为0,不等为1. 
    总之，就是这样，
    n^0=n n^n=0，即任何数与0进行异或，为它本身;
    两个相同的数进行异或运算，会得到0。

到了这里，基本的概念我们都理解了，再回来看我们这行代码：

(h = key.hashCode()) ^ (h >>> 16)

大家知道，我们的`HashMap中的数组长度`，一般默认是`16` ,转换成二进制，无非也就是`10000` ，总共五位二进制数，结合上一篇文章中的介绍，HashMap在存取值的时候，依赖`hashCode` 值，经过我们这个`hash方法` 处理后的值，再与数组长度减一进行`与运算` 确定出元素所处数组的位置，即：`tab[i = (n - 1) & hash]` 这样的操作，**而在进行`与运算` 的时候，往往因为`数组长度减一` 这个数太小，造成整个`hashCode` 值的高位几乎不可能加入到运算中**。  
  因此，为了能够让`hashCode` 值，高位也能参与到`tab[i = (n - 1) & hash]` 这样的`与运算` 中，所以有了这样的`右移` ，而我觉得，正是因为`hashCode` 值是`int` 类型，最大为`32` 位，因此尽可能的`右移最大让所有数加入到运算中，却又不丢失数据` 的操作，那就只能是`16` 这个数！！！  
  而异或运算`^` 我理解的是，起到了打乱的作用，高`16` 位和低`16` 进行了这样的运算后，会使`hash` 值出现相同的情况更低，减少了`hash` 值的碰撞，进一步使`HashMap` 数据在数组中的落点更加均匀，拥有更大的利用率。关于异或运算`^` 仅是我理解的这样，如果有大神觉得不对，请帮我纠错下，谢谢了。

[HashMap_hashcode_2_n]: https://blog.csdn.net/wohaqiyi/article/details/81161735
[70]: https://img-blog.csdn.net/20180725083302774?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvaGFxaXlp/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 1]: https://img-blog.csdn.net/20180725083557371?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvaGFxaXlp/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[java]: https://blog.csdn.net/wohaqiyi/article/details/80931693