我正在处理一个效率至关重要的项目。由于需要根据键轻松查找节点的内存地址，因此哈希表非常有用。我预见到的唯一问题是这个哈希表将需要处理高达100万个条目。通常哈希表桶是一个链接列表，以便可以处理同一个桶中的多个条目。但在我看来，对于100万个条目，这些列表会变得非常慢。那么，实现这样的东西的常见方法是什么？也许可以将标准链表替换为跳表？
6个回答
3
如果每个桶的列表中有超过几个条目，那么散列表就失去了所有优势。通常使散列表扩展到数百万个条目的方法是使主散列数组可调整大小，因此即使有数百万个条目，桶列表也会保持较短的长度。
- zwol
6
我想改变哈希表的大小应该是一个相当昂贵的操作。是否有比遍历每个条目更好的方法？ - Ian Burris
@blcArmadillo：不需要调整大小，它的大小应在创建时确定。 - ruslik
@blcArmadillo - 从摊销的角度来看，如果您通过加倍等方式调整表格大小，则非常便宜。调整表格的时间复杂度为O(n)，但是您很少这样做。基本上，对于每个插入操作，您都会“收取”额外的一单位信用，以支付调整大小所需的费用-每个操作只收取固定数量的费用，并且当调整大小发生时，它将从“节省的时间”中支付。 - user180247
@ruslik - 在现实世界中，这并不是非常实用的。通常在开始之前你不知道需要插入多少项。我所知道的所有主要哈希表实现（Python、Java、C#、C++0x、Javascript等）都会根据插入的项目数量来调整它们的哈希表大小。 - user180247
@Steve314：你说得对，这很有道理，特别是对于通用库来说。 - ruslik
@blcArmadillo：如果您记住之前的大小并在进行键查找时在多个位置查找密钥，则可以避免移动现有条目。您还可以在较小表旁创建较大的表，并逐步将条目移到查找它们时。有很多技巧... - caf
3
如果你想要一个包含一百万条目的哈希表，通常你至少需要两百万个桶。我不记得所有的统计数字（关键词是“生日悖论”），但绝大多数的桶将会有零或一个项目。原则上，你可以非常不幸地在一个桶中得到所有项目，但你必须比那些似乎每隔一天就被雷击中的人更加不幸。
对于可扩展的哈希表，通常的技巧是按照一个固定百分比进行扩容——通常的教科书案例是将哈希表大小加倍。当哈希表中的项数达到哈希表大小的一定比例时，无论实际使用了多少桶，都应该这样做。这样做可以获得平摊期望为O(1)的插入、删除和搜索性能。
哈希表中每个桶中的链表只是处理冲突的一种方式——在单次操作意义下是不太可能发生的，但在一个重要的哈希表的生命周期内，它们确实会发生——特别是当哈希表超过一半满时。
链表并不是处理冲突的唯一方法——有很多关于这个主题的知识。Walter Bright（D编程语言的开发者）主张使用二叉树而不是链表来处理冲突，声称他的Dscript相对于Javascript从这个设计选择中获得了显著的性能提升。
当我问他时，他使用了简单（不平衡）的二叉树，因此最坏情况的性能与链表相同，但关键点在于二叉树处理代码很简单，哈希表本身使得构建大型不平衡树的可能性非常小。
原则上，你也可以使用Treaps、红黑树或AVL树。使用Splay树来处理冲突可能是一个有趣的选择。但总的来说，这只是一些库设计者和一些真正的狂热分子需要担心的次要问题。
对于可扩展的哈希表，通常的技巧是按照一个固定百分比进行扩容——通常的教科书案例是将哈希表大小加倍。当哈希表中的项数达到哈希表大小的一定比例时，无论实际使用了多少桶，都应该这样做。这样做可以获得平摊期望为O(1)的插入、删除和搜索性能。
哈希表中每个桶中的链表只是处理冲突的一种方式——在单次操作意义下是不太可能发生的，但在一个重要的哈希表的生命周期内，它们确实会发生——特别是当哈希表超过一半满时。
链表并不是处理冲突的唯一方法——有很多关于这个主题的知识。Walter Bright（D编程语言的开发者）主张使用二叉树而不是链表来处理冲突，声称他的Dscript相对于Javascript从这个设计选择中获得了显著的性能提升。
当我问他时，他使用了简单（不平衡）的二叉树，因此最坏情况的性能与链表相同，但关键点在于二叉树处理代码很简单，哈希表本身使得构建大型不平衡树的可能性非常小。
原则上，你也可以使用Treaps、红黑树或AVL树。使用Splay树来处理冲突可能是一个有趣的选择。但总的来说，这只是一些库设计者和一些真正的狂热分子需要担心的次要问题。
- user180247
3
另一种处理冲突的方法是布谷鸟哈希。 - caf
这个理论似乎排除了一对密钥在两个哈希函数中都发生冲突的可能性，或者由于冲突而使一个密钥的两个可能位置都不可用。这可能意味着我还没有深入研究它。我以前见过双哈希方案，但在五分钟前读到你的评论之前从未听说过“布谷鸟哈希”，所以我很可能错过了一些具体的技巧。 - user180247
@Steve314 好吧，这很容易通过递归处理（在其位置再次替换对象并重复）来解决，我想你已经知道了;) 我同意我不明白他们使用了什么魔术技巧来确保常量查找（至少不会影响链接哈希映射的工作方式）。 - Voo
1
在每个“桶”中，您可以使用一棵树而不是列表。（AVL或类似）
编辑：跳表也可以。 （看起来更快）- O（log n）是您的目标。
- sleeplessnerd
2
1严格来说，哈希表已经提供了O(1)的期望时间复杂度。如果你想要一个渐进改进，你需要一个保证平衡的树来处理冲突 - 一个具有最坏情况下O(log n)时间复杂度的树，以便哈希表本身的摊还最坏情况下的操作时间复杂度为O(log n)，而不是摊还最坏情况下的O(n)。因为跳表是随机化的，它无法提供这样的保证 - 尽管在实践中它可能会提供性能提升。 - user180247
在处理冲突的一个桶内结构中，时间复杂度为O(log n)。 - sleeplessnerd
1
总条目数并不重要，只有每个桶的平均条目数（N / 哈希表大小）才重要。使用具有更大域（例如20位或更大）的哈希函数来确保这一点。
当然，这将占用更多内存，但这是常见的内存与速度之间的权衡。
- ruslik
0
如果你的键具有正态分布（这是一个非常大的假设），那么用于耗尽哈希表中所有桶的插入次数的期望值为M*logM（自然对数，以e为底），其中M是桶的数量。
很惊讶在网上找不到这个信息！
我已经在我的博客上发布了同样的推导，并使用rand()进行了验证。它似乎是一个相当好的估计。
- Arvind
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接