哈希表与平衡二叉树
当我需要在散列表或二叉树" title="平衡二叉树">平衡二叉树之间进行选择以实现集合或关联数组时，应该考虑哪些因素？
回答：
通常来说，我不能回答这个问题。
问题是哈希表和平衡二叉树的类型很多，它们的性能差异很大。
因此，简单的答案是：它取决于您所需的功能。如果不需要排序，请使用哈希表，否则请使用平衡的二叉树。
对于更详尽的答案，让我们考虑一些替代方法。
哈希表（有关某些基础知识，请参阅Wikipedia的条目）
- 并非所有哈希表都将链接列表用作存储桶。一种流行的替代方法是使用“更好”的存储桶，例如二叉树或另一个哈希表（带有另一个哈希函数），…
- 一些哈希表根本不使用存储桶：请参阅开放式寻址（显然，它们还带有其他问题）
- 有一种叫做线性重新哈希的东西（它是实现细节的质量），它避免了“停止世界并重新哈希”的陷阱。基本上，在迁移阶段，您只能插入“新”表中，还将一个“旧”条目移到“新”表中。当然，迁移阶段意味着需要双重查询等。
二叉树
- 重新平衡的成本很高，您可以考虑使用“跳过列表”（对于多线程访问也更好）或“播放树”。
- 一个好的分配器可以将节点在内存中“打包”在一起（更好的缓存行为），即使这不能减轻指针查找问题。
- B树和变体还提供“包装”
我们不要忘记O（1）是渐近复杂性。对于少数元素，系数通常更重要（从性能角度而言）。如果您的哈希函数很慢，则尤其如此。
最后，对于集合，您可能还希望考虑概率数据结构，例如BloomFilters。
以上是 哈希表与平衡二叉树 的全部内容， 来源链接： utcz.com/qa/420021.html
