在C++中,如何处理哈希映射中的哈希冲突？

Question

在C++中,如何处理哈希映射中的哈希冲突？如果发生碰撞,将花费多少时间来搜索元素？

而且,什么是好的哈希函数？

Answer 1

根据您使用的系统,有许多不同的方法可以处理哈希映射中的冲突.以下是一些:

1. 如果使用封闭寻址,那么您可能会将每个项哈希到一个值的链接列表,所有这些值都具有相同的哈希码,然后遍历列表以查找相关元素.
2. 如果您使用线性探测,那么在哈希冲突之后,您将开始查看相邻的存储桶,直到找到您要查找的元素或空位.
3. 如果你使用二次探测,那么在哈希碰撞之后,你会看到远离搜索中的碰撞点的元素1,3,6,10,15,...,n(n + 1)/ 2,...一个空白点或有问题的元素.
4. 如果使用cuckoo哈希,则会维护两个哈希表,然后将与之冲突的元素替换为另一个表,重复此过程直到冲突解决或您必须重新哈希.
5. 如果使用动态完美散列,则可以从共享该散列码的所有元素构建完美的散列表.

您选择的具体实施取决于您.去做最简单的事情.我个人认为链式散列(封闭式寻址)是最容易的,如果这个建议有帮助的话.

至于什么是一个好的哈希函数,这实际上取决于你存储的数据类型.例如,字符串的散列函数通常与整数的散列函数非常不同.根据您想要的安全保证,您可能希望选择加密安全散列SHA-256,或者只是简单的启发式,如单个位的线性组合.设计一个好的哈希函数是非常棘手的,我建议在得出结论之前,先挖掘一下你将要散列的特定结构的建议.

希望这可以帮助!