这种处理哈希冲突的方法是新的/独特的吗？

Question

这种处理哈希冲突的方法是新的/独特的吗？

haskellhashhashmaphashableunordered-containers

7

当处理哈希映射时，我看到了一些应对哈希冲突的策略，但我们想出了一些不同的方法。我想知道这是否是新的方法。

这个版本的哈希映射只在哈希和将要被哈希的数据结构可盐时才有效。（在 Haskell 的 hashable 中，我们建议实现这种方法。）

这个想法是，不是在哈希映射的每个单元格中存储列表或数组，而是存储一个递归的哈希映射。这个递归哈希映射的唯一区别在于使用不同的盐。这样，哈希映射的一个级别上的哈希冲突很可能不是下一个级别上的哈希冲突。因此，插入到这样的哈希映射中不再是 O(此哈希上的冲突数)，而是 O(递归发生冲突的级别数)，这很可能更好。

更详细的说明和实现可以在这里找到：

https://github.com/tibbe/unordered-containers/pull/217/files/58af4519ace34c5f7d3c1359907ff75e27b9cdb8#diff-ba23e0f18c79cb873ac5375367524cfaR114

- Syd Kerckhove

2

我觉得这更适合计算机科学堆栈交换。 - Mor A.

2

这种策略让我想起了杜鹃哈希；虽然不完全相同，但是值得查阅一下关于杜鹃哈希的文献，看看是否有类似的变体存在。 - Daniel Wagner

我要指出的是，你为额外哈希表分配的空间可以用来使顶级哈希表更稀疏，从而减少第一个哈希中发生碰撞的可能性。 - chepner

@chepner 不完全是；请记住哈希冲突受生日悖论的影响。 - leftaroundabout

@hnefatl 对，尽管这对许多应用程序可能并不重要。由于哈希映射中的元素访问通常是无序的，即使结构是一个平坦数组，您通常也会遇到大量的缓存未命中。 - leftaroundabout

显示剩余2条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- leftaroundabout · Accepted Answer

你的想法似乎与1984年Fredman，Komlós和Szemerédi的论文中提出的想法基本相同。正如维基百科所总结的：

FKS哈希利用具有两个级别的哈希表，其中顶层包含n个桶，每个桶都包含自己的哈希表。

与你的想法相比，本地哈希映射不是递归的，而是选择一个使其成为完美哈希的盐。在实践中，这通常会通过尝试第一个盐来实现（正如你所说），因此它是渐近恒定时间。