Hash冲突是怎么回事

在这个文章正式开始之前，先几句话把这个问题说清楚了：我们常说的 Hash 冲突到底是怎么回事？

直接上个图片：

你说你看到这个图片的时候想到了什么东西？

有没有想到 HashMap 的数组加链表的结构？

对咯，我这里就是以 HashMap 为切入点，给大家讲一下 Hash 冲突。

接着我们看下面这张图：

假设现在我们有个值为 [why技术] 的 key，经过 Hash 算法后，计算出值为 1，那么含义就是这个值应该放到数组下标为 1 的地方。

但是如图所示，下标为 1 的地方已经挂了一个 eat 的值了。这个坑位已经被人占着了。

那么此时此刻，我们就把这种现象叫为 Hash 冲突。

HashMap 是怎么解决 Hash 冲突的呢？

链地址法，也叫做拉链法。

数组中出现 Hash 冲突了，这个时候链表的数据结构就派上用场了。

链表怎么用的呢？看图：

这样问题就被我们解决了。

其实 hash 冲突也就是这么一回事：不同的对象经过同一个 Hash 算法后得到了一样的 HashCode。

那么写到这里的时候我突然想到了一个面试题：

请问我上面的图是基于 JDK 什么版本的 HashMap 画的图？

为什么想到了这个面试题呢？

因为我画图的时候犹豫了大概 0.3 秒，往链表上挂的时候，我到底是使用头插法还是尾插法呢？

众所周知，JDK 7 中的 HashMap 是采用头插法的，即 [why技术] 在 [eat] 之前，JDK 8 中的 HashMap 采用的是尾插法。

这面试题怎么说呢，真的无聊。但是能怎么办呢，八股文该背还是得背。

面试嘛，背一背，不寒碜。

构建 HashCode 一样的 String

前面我们知道了，Hash 冲突的根本原因是不同的对象经过同一个 Hash 算法后得到了一样的 HashCode。

这句话乍一听：嗯，很有道理，就是这么一回事，没有问题。

比如我们常用的 HashMap ，绝大部分情况 key 都是 String 类型的。要出现 Hash 冲突，最少需要两个 HashCode 一样的 String 类。

那么我问你：怎么才能快速弄两个 HashCode 一样的 String 呢？

怎么样，有点懵逼了吧？

从很有道理，到有点懵逼只需要一个问题。

来，我带你分析一波。

我先问你：长度为 1 的两个不一样的 String，比如下面这样的代码，会不会有一样的 HashCode？

String a = "a";
String b = "b";

肯定是不会的，对吧。

如果你不知道的话，建议你去 ASCII 码里面找答案。

我们接着往下梳理，看看长度为 2 的 String 会不会出现一样的 HashCode？

要回答这个问题，我们要先看看 String 的 hashCode 计算方法，我这里以 JDK 8 为例：

我们假设这两个长度为 2 的 String，分别是 xy 和 ab 吧。

注意这里的 xy 和 ab 都是占位符，不是字符串。

类似于小学课本中一元二次方程中的未知数 x 和 y，我们需要带入到上面的 hashCode 方法中去计算。

hashCode 算法，最主要的就是其中的这个 for 循环。

h 初始情况下等于 0。

String 类型的底层结构是 char 数组，这个应该知道吧。

所以，value.length 是字符串的长度。val[] 就是这个 char 数组。

把 xy 带入到 for 循环中，这个 for 循环会循环 2 次。

第一次循环：h=0，val[0]=x，所以 h=31*0+x，即 h=x。

第二次循环：h=x，val[1]=y，所以 h=31*x+y。

所以，经过计算后， xy 的 hashCode 为 31*x+y。

同理可得，ab 的 hashCode 为 31*a+b。

由于我们想要构建 hashCode 一样的字符串，所以可以得到等式：

31x+y=31a+b

那么问题就来了：请问 x，y，a，b 分别是多少？

你算的出来吗？

你算的出来个锤子！黑板上的排列组合你不是舍不得解开，你就是解不开。

但是我可以解开，带大家看看这个题怎么搞。

数学课开始了。注意，我要变形了。