哈希桌子与二进制树

Question

在实施字典时（“我想通过客户ID查找客户数据”），使用的典型数据结构是散布表和二进制搜索树。我知道例如，C ++ STL库使用（平衡）二进制搜索树实现词典（它们称其为地图），并且.NET Framework在引擎盖下使用哈希表。

这些数据结构的优点和缺点是什么？在某些情况下还有其他选择吗？

请注意，我对钥匙具有强大基础结构的情况并不特别感兴趣，例如，它们都是1到n或其他东西之间的整数。

Answer 1

可以在这个主题上写一本论文；我只是要介绍一些明显的观点，我将对其他数据结构进行讨论至少（确实有很多变体）。在整个答案中，$ n $是字典中的键数。

简短的答案是 哈希表在大多数情况下更快, ，但在他们最糟糕的情况下可能很糟糕。 搜索树 有很多优势，包括 驯服最坏的行为, ，但在典型情况下有些较慢。

平衡的二进制搜索树 具有相当均匀的复杂性：每个元素在树上取一个节点（通常是4个单词），而基本操作（查找，插入，删除）取$ o（ mathrm {lg}（n）（n））$时间（保证渐近上限）。更确切地说，树中的访问需要$ mathrm {log} _2（n）$比较。

哈希表 有点变化。他们需要大约$ 2N $的指针。访问一个元素取决于哈希功能的质量。哈希功能的目的是分散元素。如果您想存储在其中的所有元素都有不同的哈希，则“工作”。如果是这种情况，那么基本操作（查找，插入，删除）采用$ o（1）$时间，具有相当小的常数（一个哈希计算加一个指针查找）。在许多典型情况下，这使其非常快。

哈希表的一般问题是不能保证$ O（1）$复杂性。

• 另外，有一个桌子变满了。当发生这种情况（或者更好的是在此发生之前）时，需要放大表，这需要移动其所有元素，以$ O（n）$成本。当添加许多元素时，这可能会引入“生涩”行为。
• 输入可能会在一些哈希值上碰撞。这很少发生，但是如果攻击者选择输入，则可能是一个安全问题：这是一种大大减慢某些服务器的方法。此问题导致一些编程语言实现（例如Perl和Python）从纯旧哈希表转换为构建哈希表时选择的随机数，以及构建哈希表的随机数，以及散布此随机数据井的哈希函数时选择的随机数（这增加了$ O（1）$中的乘法常数）或二进制搜索树。虽然您可以通过使用加密哈希来避免碰撞，但在实践中并不是因为加密哈希相对较慢计算。

当你投掷时 数据局部性 混音中，哈希表的确很差。它们之所以起作用，是因为它们将相关元素的相距较远，这意味着，如果应用程序查找顺序共享前缀的元素，则不会从缓存效果中受益。如果应用程序本质上是随机查找，则无关紧要。

支持搜索树的另一个因素是它们是 不变 数据结构：如果您需要取出树的副本并更改其中的一些元素，则可以共享大多数数据结构。如果您取出哈希表的副本，则需要复制全部指针。另外，如果您使用纯粹的功能性语言工作，则散布表通常不是一个选择。

当您超越字符串时，哈希表和二进制搜索树对键的数据类型提出不同的要求：哈希表需要哈希函数（从键到整数的函数，以至于$ k_1 equiv k_2 含义h（k_1） ）= h（k_2）$，而二进制搜索树需要总订单。有时可以缓存哈希，如果数据结构中有足够的空间存储键的空间；缓存比较结果（二进制操作）通常是不切实际。另一方面，比较可以从捷径中受益：如果键在前几个字节中通常有所不同，则负面比较可能非常快。

特别是，如果您需要 命令 在键上，例如，如果您想能够按字母顺序列出键，则没有帮助（您需要对它们进行分类），而您可以直接按顺序横穿搜索树。

您可以将二进制搜索树和哈希表组合起来 哈希树. 。 Hash树根据搜索树存储钥匙。例如，在纯粹的功能编程语言中，您想处理没有易于计算的订单关系的数据。

当键是字符串（或整数）时 特里 可以是另一个选择。 Trie是一棵树，但与搜索树的索引不同：您以二进制编写键，然后以0和右为1的键。因此，访问的成本与钥匙的长度成正比。可以压缩尝试以删除中间节点；这被称为 Patricia Trie或Radix树. 。 radix树可以胜过平衡树，尤其是当许多钥匙共享一个常见前缀时。