HashMap的同一链表中对象的hashcode真的一样吗？

约定不等于承诺〃 2023-02-14 02:36 8阅读 0赞

网上关于hashMap的面试题以及博客有很多，基本都大同小异，今天我们从一个新的角度来聊一下HashMap，首先我们通过一个面试问答来了解下：

Q：什么是哈希碰撞？

A：HashMap中2个对象产生相同的hashcode时就是哈希碰撞

Q：HashMap是如何解决哈希碰撞？

A：产生哈希碰撞的对象，以链表的形式存储在数组的同一个位置上

Q：HashMap的数组中同一链表上对象的hashcode都一样的吗？

A：**不是，而且大多数情况下都不一样**

那么问题来了，为什么HashMap中同一链表上对象的hashcode是不一样的呢？说到这里，我们首先熟悉下HashMap是如何产生一个数组下标的，先看下图HashMap存储对象的方法：

![2020072711211538.png][]

在509行中的红框中的代码我们可以看到下标 **i = (n - 1) & hash，**n 就是HashMap中数组的长度默认为16，hash就是通过对象key产生的hashcode。也就是下标是通过数组长度-1 和 hashcode 按位与产生的，现在我们假设有一个hash为1的，长度为16的数组，那么就是它产生的下标 **i =15 & 1** ，换算成二进制如下图：

![20200727113451909.png][]

我们知道按位与是只有对应的2个二进制位都为1时，结果位才为1，所以最后下标 **i=1。**那么如果又有一个hash为17的对象放进来时，会发生什么呢？我们还是先看下标**i =15 & 17**，换算成二进制如下图：

![20200727114226783.png][]

没错，**下标i还是等于1，这个时候由于1这个位置上已经有一个对象了，所以HashMap就会产生hash为1和hash为17都放在数组同一个位置链表上。**

那么为什么会发生这种情况？可能有的人已经懂了：**由于数组长度默认为16，n-1为15，它的后4位为1，所以只要产生的hash值后4位一样，其他位任意组合都会产生相同的下标。**那么为什么大多数情况下HashMap中同一个链表上的hashcode都不一样？这是因为Hashmap中的哈希函数也叫作散列函数，它的目的就是为了让HashMap中的对象散列分布，所以2个不同的对象产生相同的hashcode的概率是很低的.

这里，我也自定义了一个HashMap来测试这个问题：

![20200727163541153.png][]

![20200727163637631.png][]

第一张图的红框中是在产生了相同的下标时添加的打印代码，第二张图中的是测试方法，可以看到结果49和1569的二进制数的后4位都一样是0001，50和1570的二进制数的后4位都一样是0010.这个结果与我们的推论吻合。

最后的结论就是**HashMap中同一链表对象中的hashcode在大多数情况下是不一样的。**

**总结：**

** **其实这个问题是我在看hashMap的扩容方法时发现的。当时也是先有的想法，然后再实践发现的这个问题，所以在看源码时，如果我们可以抠更多的细节，还是可以发现很多知识盲区的。

[2020072711211538.png]: https://img-blog.csdnimg.cn/2020072711211538.png
[20200727113451909.png]: https://img-blog.csdnimg.cn/20200727113451909.png
[20200727114226783.png]: https://img-blog.csdnimg.cn/20200727114226783.png
[20200727163541153.png]: https://img-blog.csdnimg.cn/20200727163541153.png
[20200727163637631.png]: https://img-blog.csdnimg.cn/20200727163637631.png