这是我们分享散列表的第三篇，在第一篇中我们分享了散列表的基础原理和HashMap应用，在第二篇中我们分享了散列函数。你都还记得吗？那么这一篇一起来分享：散列冲突、以及散列冲突的解决方法。

#考考你：
1.你还记得什么是散列冲突吗？
2.你知道什么是开放寻址法吗？
3.你知道什么是拉链法吗？

案例散列冲突

我们说散列表数据结构，是数组的一种扩展，利用了数组支持按照下标随机访问的特性。那么这里就有一个讲究：如何把散列表的key，与数组的下标建立起对应关系。这里我们需要一个散列函数，即：hash(key) 。如下图示：

那要如何设计散列函数呢？有三个基本原则：

#设计散列函数基本原则：
1.通过散列函数，计算出的散列值，必定是非负整数
2.如果key1 = key2，那么必定hash(key1) = hash(key2)
3.如果key1 != key2，那么尽量hasy(key1) != hash(key2)

第一条与第二条，我们在上一篇散列函数中有详细解释，也很好理解，这里我们就只看第三条。关键在这里：如果key1 != key2，那么尽量hasy(key1) != hash(key2) 。

你有没有发现，我用了两个字：尽量。其实在内心我们是多么渴望：如果key不同，那么计算出的散列值就一定不同。但是很难办到，或者就说办不到。即便是业界知名的MD5、SHA哈希算法，也存在散列冲突。

因此，我们默认接受了散列冲突的存在。当然你也不同担心，针对散列冲突有相应的解决办法：开放寻址法、拉链法。

开放寻址法

什么是开放寻址法呢？

我们先看一个图，然后再通过文字描述，相信你就可以明白了。

说话：

#开放寻址法思想：
1.假设有一个散列表，散列表容量是：7
2.如上图示，填充了蓝色的块，表示已经存储了数据
3.未填充颜色的块，表示空闲
4.现在有一个元素：a，需要存储到散列中
5.a元素通过散列函数hash(key)，计算出散列值对应数组下标：5的位置
6.数组下标5的位置，已经填充了蓝色块（已经存有数据）
7.那么我们说：这就是散列冲突（不同的key，散列函数计算出了相同的散列值）
8.既然下标5的位置已经存储了其他数据，那a元素该如何处理呢？
9.我们只需要向前看，比如说看6的位置
10.6的位置也不巧，也存储了数据
11.而且6是数组的最后一个下标位置，如何继续向前呢？
12.我们可以从头再来，从0号位置开始看，0的位置也不巧，也存储了数据
13.那1的位置呢？刚好1的位置没有填充颜色，是空闲
14.于是将元素a，存储在下标1的位置
15.这就是整个开放寻址法的思想，很简单有没有？
16.但是你可能会发现开放寻址法有一个弊端：
   16.1.如果散列表中，空闲位置比较少，那么散列冲突的概率就会很大
   16.2.这个时候开放寻址法的效率就会很低
   16.3.因此开放寻址法，只适合于散列表规模小，散列元素少的场景

拉链法

什么是拉链法呢？

我们还是看一个图，然后再通过文字描述，相信你就可以明白了。

看图：

说话：

#拉链法思想：
1.假设有一个散列表，散列表容量是：5
2.如上图示，填充了蓝色的块，表示已经存储了数据
3.未填充颜色的块，表示空闲
4.在散列表的右边，对应每一个蓝色块，都有一个链表
5.0的位置链表有两个节点，表示0的位置存在散列冲突
6.2的位置链表有三个节点，表示2的位置存在散列冲突
7.这就是整个拉链法的思想，也很简单有没有？
8.我们来具体描述一下：
  8.1.拉链法的核心思想是，散列表对应数组的每一个下标位置，称为：slot槽
  8.2.每一个slot槽位，对应一条链表，用于解决散列冲突
  8.3.当不同的元素key，通过散列函数计算出了相同的散列值，存在散列冲突
  8.4.比如0 槽位发生了散列冲突，那么只需在0槽位的链表上增加一个节点即可
  8.5.这也就是拉链法名称的由来（链表==>拉链法），对吧
9.最后结论：
	拉链法适合于存储大规模散列元素的散列表场景。比如java中的HashMap，应用的就是拉链法处理散列冲突。当然在jdk8中，还结合了红黑树，你应该去看一下HashMap的源码了！