导读：

1、什么是哈希表

2、为什么会有哈希冲突

3、四种解决哈希冲突的办法

4、常见哈希冲突面试题

什么是哈希表

哈希表是一种数据结构，它是在数组和链表的基础上演化而来，既具有数组快速访问的优点，又具有链表方便插入和删除的优点。它能够快速定位到想要查找的记录，而不需要和表中存在的记录逐一进行比较来进行查找。

哈希表通过某种函数使元素的存储位置与它的关键码之间能够建立一一映射的关系，在查找时通过该函数可以很快找到该元素。

哈希表

为什么会有哈希冲突

哈希是通过对数据进行再压缩，提高查找效率的一种解决方法。通过哈希算法产生的哈希值数量是有限的，而需要计算哈希的原始值是无限的，根据抽屉原理，这势必导致存在不同的原始值通过同一个哈希算法得到同一个哈希值的情况。

哈希冲突

如何解决哈希冲突问题

哈希冲突是必然存在的，那么该如何解决冲突问题呢？

开放地址法

开放地址法就是一旦发生冲突，就去寻找下一个空的地址。只要列表足够大，空的散列地址总能找到，并将记录存入。

那么问题来了，我们要以哪种方式去寻找下一个空地址呢？常用查找的方式：

1、线性探测：步长为1，不断向后查找。

2、二次探测：步长依次为1^2 , -1^2 , 2^2 , -2^2 ....，不断查找。

3、随机探测：步长是伪随机数（随机因子和随机次数相同，得到的随机数也相同），不断查找。

线性探测的示例：

开放地址法

开放地址法中具有相同哈希值的数据所在的位置是会相互影响的，这就意味着在删除数据的时候，就不能直接删除数据。

比如上图中的哈希表，如果删除元素了7，地址7也就会被释放出来，这个时候如果再次插入15的时候，发现地址7是空着的，就会把15存入到地址7里，这就导致哈希表里不同的位置存放了两个15。如果想要删除数据，就需要采用标记删除，不是直接删除。

链地址法

这是一种非常常见的方法，简单理解就是把存在哈希冲突的数据，以单向链表的方式来存储，链地址法能够很好的解决数据删除的问题。

链地址法

再哈希法

再哈希法需要提前设计好一组哈希算法，当发现第一种哈希算法计算结果出现冲突时，就使用第二种哈希算法。以此类推，直到不冲突为止。这种方式在冲突的时候，需要计算多次哈希，计算性能会差一些。

再哈希法

公共溢出区法

这种方式可以简单的理解为：冲突的数据就不要来捣乱了，一边待着去。哈希表被分为基本表和溢出表两个部分，凡是存在冲突的元素，一律放入到溢出表中。

公共溢出区法

常见面试题

HashMap中是如何解决哈希冲突

在HashMap中是通过链式寻址的方式解决哈希冲突的，它会把哈希冲突的数据记录在链表里。在JDK8之后，在满足一定条件后链表会转换为红黑树，以便提高查询和插入的效率。链表转红黑树必须满足两个条件：

1、链表原始个数达到8个。

2、HashMap的槽位slot达到64个。

解决哈希冲突的方式有哪些，他们都有什么优缺点

这个问题上文已经基本说明了，就不再赘述了。

为什么布隆过滤器删除数据比较困难

布隆过滤器使用一组哈希函数计算得到一组哈希值，哈希值所对应的二进制位设置为1。如果要从布隆过滤器中删除数据，是不是直接删除这些哈希值所对应的二进制位全部设置为0呢？显然是不能这么做的，因为每一种哈希算法都存在哈希冲突的情况，同一位上的1可能是多个输入经过哈希计算后设置的。如果真要对布隆过滤器的数据进行删除，可以使用Counting Bloom Filter，这将会占用大量的空间。