【解决哈希冲突】

哈希冲突

如果两个不同的 key 通过哈希函数得到了相同的索引，这种情况就叫做「哈希冲突」。

哈希冲突不可能避免，只能在算法层面妥善处理出现哈希冲突的情况。

哈希冲突是一定会出现的，因为这个 hash 函数相当于是把一个无穷大的空间映射到了一个有限的索引空间，所以必然会有不同的 key 映射到同一个索引上。

哈希冲突的解决办法

出现哈希冲突的情况怎么解决？两种常见的解决方法，一种是拉链法，另一种是线性探查法（也经常被叫做开放寻址法）。

就是纵向延伸和横向延伸两种思路：

1、拉链法：

拉链法相当于是哈希表的底层数组并不直接存储 value 类型，而是存储一个链表，当有多个不同的 key 映射到了同一个索引（节点）上，这些 key -> value 对儿就存储在这个链表中，这样就能解决哈希冲突的问题。

2、开放寻址法

而线性探查法的思路是，一个 key 发现算出来的 index 值已经被别的 key 占了，那么它就去 index + 1 的位置看看，如果还是被占了，就继续往后找，直到找到一个空的位置为止。

比方说上图，key 的插入顺序是 k2, k4, k5, k3, k1，那么哈希表底层就会变成这样：