在散列字符串中解决冲突的最佳方法

我在一次采访中被问到了这个问题，并表示使用第二个函数，但面试官一直在探询其他答案。任何人有其他解决方案在散列字符串中解决冲突的最佳方法

来源

2012-02-05 user1190650

链接每个节点花费一个指针，并以丢失引用的局部地址为代价解决所有问题。（这也会通过二次哈希丢失） – wildplasser 2012-02-05 13:49:14

哈希为了什么目的？密码？ MD5文件散列？字典/ hashsets？ – doblak 2012-02-05 13:49:47

@Darjan for dictionaries – user1190650 2012-02-05 13:52:09

使用链表的散列桶。所以任何冲突都会得到妥善处理。

来源

2012-02-05 13:50:57 utopiabound

替代方法：您可能希望使用trie而不是散列表对字符串字典进行合并。

这种方法的好处在于你得到O(|S|)寻找/插入每个字符串的最坏情况下的复杂性[其中| S |是该字符串的长度]。需要注意的是哈希表可以让你只O(|S|)，平均情况下最坏的情况是O(|S|*n) [其中n是字典的大小。特里树也并不需要在负载平衡过高换汤不换药。

来源

2012-02-05 13:57:24 amit

假设我们不使用a perfect hash function（你通常没有）哈希告诉你：

如果哈希值是不同的，对象是不同的
如果散列是相同的，对象是可能是相同（如果使用了良好的散列函数），但可能仍然不同。

在哈希表中

因此，碰撞将一些额外的检查，如果该对象实际上是相同的或没有（这带来了一定的性能损失，但根据Amdahl's law，你还是收获了很多，解决了因碰撞很少发生好的散列函数）。在词典中，你只需要解决罕见的碰撞的情况下，确保你得到正确的对象了。

使用另一个非完美的散列函数不会解决任何问题，它只是减少（另一个）碰撞的机会。

来源

2012-02-05 14:03:26 doblak

“如果散列相同，则对象可能是相同的” - 只有当元素的数量对于散列桶的数量不是过多时才是如此。 – 2012-02-07 02:48:50

@TonyDelroy你是对的，在这种情况下，'可能'和'可能'不是正确的词，因为概率随分布而变化。这就是斜体的原因，但我对此不够具体。 – doblak 2012-02-07 10:33:04

在哈希串解决冲突 “连续插入”

假设插入

最好的办法是字符串，其内容是无法预测的，那么合理的选项是：

使用位移列表，因此您可以尝试从散列到桶的多个偏移量，直到找到空闲桶（由表大小进行修改）为止。排量列表可能看起来像{3，5，11，19 ...}等 - 最好要具有位移之间的差异不是其他位移序列的总和。
翻版使用不同的算法（但当时如果你碰巧两次等发生冲突你需要另一个算法）
根容器在桶，这样的碰撞字符串可以搜索。通常桶的数量应该类似于或大于元素的数量，因此每个桶的元素将相当小，并且通过数组/矢量进行蛮力搜索是合理的方法，但链接列表是也可信。

这些比较，位移列表往往是最快的（因为添加的偏移量是不是计算另一散列或支持分离的堆&分配更便宜，并且在大多数情况下，前一个或两个位移（其可以合理地通过一个少量的桶）足以找到一个空桶，因此内存使用的位置是合理的），尽管它们比替代哈希算法（应该接近＃个元素/＃桶进一步碰撞的可能性）更容易发生碰撞。对于位移列表和重新哈希表，您必须提供足够的重试次数，实际上，您不会指望彻底失败，为失败添加一些最后手段处理，或接受可能发生的失败。

来源

2012-02-07 06:47:30

在散列字符串中解决冲突的最佳方法

回答

相关问题