哈希表—更多哈希冲突

冰冻非一日之寒

在java标准库中，底层处理哈希冲突的方法是连地址法，之前也详细介绍过这种方法。

而在哈希表中，除了链地址法，还有其他的几种解决哈希冲突的方法

开放地址法

对于链地址法，数组(哈希表)中的每一个地址，只包含哈希值(对应索引)等于这个地址的元素。开放地址法恰好相反，对每一个地址，所有哈希值(对应索引)的元素都有机会进来

对于如下的一个哈希表

哈希表—更多哈希冲突

哈希函数是哈希值对10取模

哈希表—更多哈希冲突

第一次，来了一个11的关键字，对于小范围的正整数，哈希值为其本身。代入哈希函数，计算出索引为1，存储索引为1的位置。

第二次，来了一个25的关键字，同理，存储到索引为5的位置

第三次，来了一个31，计算出索引为1。而1的位置已经有数字了，即有了哈希冲突，这个31该如何存储呢？

使用开放地址法，找到1位置的下一个位置即2。2位置若为空，就存储到2位置；2位置若不为空，继续向下寻找，直到找到一个空间的位置，存储即可

哈希表—更多哈希冲突

可以设想，假如又来了一个81，该存储到哪个位置呢？

答案是，3的位置

哈希表—更多哈希冲突

以上讲的是开放地址法中的线性探测法，即遇到哈希冲突寻找下一个地址时，地址不断+1

线性探测法的缺点是，当哈希表中出现整片空间被占时，需要不断寻找地址，显然浪费时间，效率低

所以，开放地址法又引出了新的寻找地址法。

平方探测法，遇到哈希冲突寻找新的地址时，+1  +4  +9  +16  +25……，以平方的方式进行寻址

二次哈希法，遇到哈希冲突时，采用另一个哈希函数来计算出，寻找新地址的步长。即加上多少来寻找新的地址

显然，在处现整片空间被占时，平方探测和二次哈希法效率会更高一些

线性探测、平方探测、二次哈希都属于开放地址法，只是计算步长的方式不同而已

开放地址法也会出现整个哈希表“快被占满”的情况，这时是需要扩容哈希表的。负载率，值哈希表中已存储数据的位置数与哈希表位置总数的比。哈希表是否需要扩容，取决于负载率的大小，当负载率超过一定程度时，就需要扩容哈希表了。

开放地址法背后的数组分析也是极其复杂的。我们只需记住结论即可，对于开放地址法来说，只要扩容的负载率选的合适，它的时间复杂度也能达到O(1)级别

再哈希法

顾名思义，再次使用哈希函数解决哈希冲突。即当遇到哈希冲突时，我们使用另一个哈希函数来计算哈希值，重新找一个空的地址

Coalesced Hashing

这种解决哈希冲突的方法是连地址法和开放地址法的结合，综合了它们的优点。

读者可自行了解其方法的内部实现。

哈希冲突就介绍到这里了～