为什么Python的字典实现是基于哈希表，而std::map是基于树的？

Question

为什么两种语言在看似相似的数据结构中，一种使用树而另一种使用哈希表？

C++中的map与Python中的dict。

一个相关的问题是关于哈希表性能的。
请评论下面我对哈希表的理解。

树结构可以保证O(log n)的时间复杂度。
而哈希表由于可能出现冲突，所以没有保证，除非事先知道输入值。
我倾向于认为，随着问题规模的增大，哈希表的性能将接近于O(n)。
因为我从未听说过一种哈希函数会随着问题规模的增长而动态调整其表大小。

因此，哈希表只适用于某个范围内的问题规模，这就是为什么大多数数据库使用树而不是哈希表的原因。

- eugene

---

而Haskell的Data.Map是基于大小平衡二叉树的。 - joaquin

通常你使用的哈希表比表格大小大很多倍，所以你可以调整表格大小并使用不同的模数。数据库使用树（不同的树）的原因是为了最小化磁盘访问并将实际结构的大部分保留在内存中，这样你就可以直接访问数据而不需要太多浪费的头部移动（虽然对于固态硬盘来说这个问题已经不重要了，但是减少磁盘访问仍然是一个主要因素）。 - Joey

@Joey：所以，当大小很大时，在内存中操作哈希表相当困难。另一方面，树在这方面自然是合适的。我理解你的意思了吗？ - eugene

当一棵不平衡的树变成一个列表时，树可以在O(n)的时间内工作。为了使树保持平衡并且在O(log n)的时间内工作，需要花费一些时间来平衡它。 - fogbit

Answer 1

新的C++标准具有std::unordered_map类型它是一个哈希表。我记得他们也想让它成为上一个标准的一部分，但在讨论期间没有足够的时间，所以被忽略了。然而，多数流行的编译器多年来都提供了它的某种形式。

换句话说，不要过于担心它。针对手头任务使用适当的数据结构。

---

关于你对哈希表的理解，是不准确的：

我没有听说过一个哈希函数可以动态地调整其表格大小以适应问题规模的增长。

所有严肃的哈希表实现都会根据输入的增长动态地进行调整，通过分配更大的数组并重新散列所有键。虽然这个操作很昂贵，但如果设计得当（要做得足够少），性能仍然是平摊O(1)的。

- Eli Bendersky

Answer 2

你对哈希表的理解（以及谁使用它们）存在缺陷。

问题在于，哈希表是一个相当模糊的术语。底层有许多实现...但首先让我们谈谈BST（二叉搜索树）的使用。

为什么C++使用二叉搜索树？ C++是由委员会设计的，哈希表有许多可能的实现，导致特征大不相同，而BST（红黑树和AVL树）的最流行的实现几乎具有相同的特征。因此，他们没有完全拒绝哈希表，他们只是无法解决要选择哪些特征和向用户公开哪些细节的问题。 请参见James Kanze的评论，建议到达得太晚了，而且James提出了一个有趣的问题，即Stepanov为什么不首先提出该建议。我仍然怀疑选择数量是罪魁祸首。

数据库为什么使用搜索树？

首先，让我们选定一个数据库软件。我选择Oracle，因为它被广泛记录并且是SQL数据库的典型代表。Oracle提供两种类型的索引：位图和搜索树。 注意：他们不使用二叉搜索树，而是使用B+树，这更加IO和缓存友好。 哈希表和搜索树之间存在根本差异：后者是有序的。许多数据库操作涉及排序：

- 获取第n个元素 - 获取前n个元素 - 获取[a，b]范围内的元素

在所有这些情况下，哈希表都无用。

此外，数据库需要处理庞大的数据集（通常情况下），这意味着它们需要组织数据以最小化IO（磁盘读写）。在这里，搜索树的排序特性意味着（在索引中）共享较多的元素也将被分组在一起，而不是散布在磁盘的各个角落。

最后，Oracle在其执行计划中可能会使用哈希表（Hash Tables）。当你执行一个需要交集的操作时，优化引擎可能会决定将（临时的）集合存储在哈希表中是最快的方法。

---

现在，关于性能。

确实，搜索树的性能通常是众所周知的，易于理解，O(log N) 很清晰易懂。

另一方面，正如我所说，有许多不同的哈希表实现可能存在，以及处理增长和缩小的策略... 这显然更加复杂。

结构的简单示例，哈希表可以使用：

• 开放地址法：哈希表是一个元素数组，哈希指示要将元素放入的数组位置，如果该位置已满，则使用一种策略来定位另一个位置。搜索也使用相同的策略。
• 桶：哈希表是指向桶的指针数组，哈希指示要将元素放入的桶的插槽。假设桶可以无限增长。

这两种策略具有非常不同的特征，后者的特征也取决于桶的实现方式（简单的实现方式是使用简单的链接列表）。

但即使你选择一个实现，它的性能也基于哈希函数分布，这取决于输入序列本身！

---

我的个人建议？在C++中选择unordered_map和map之间，我只是问自己是否需要排序元素。如果需要排序，则使用map，否则使用unordered_map。大多数情况下，性能都很好，所以这只是语义。

- Matthieu M.

---

回答不错，但为什么要加上最后一句话呢？我发现在大型数据集中，对于典型的查找需求（无需排序），unordered_map 比 map 快得多。 - Eli Bendersky

由于大多数初学者过于关注性能，当使用包含10个元素的序列时，他们会专注于大O表示法。如果需要性能，请测量（分析），否则只需选择支持您所需任务语义的容器，让生活更轻松。 - Matthieu M.

公平地说，我认为一个SO答案应该在一般意义上准确，而不是针对特定的用户群体（那些不理解性能和大O问题的初学者）。如果你确实要针对某个群体，至少要在括号或脚注中明确说明。否则，如果将其从上下文中剥离出来，答案就会显得不太正确。 - Eli Bendersky

部分历史知识：大多数C++并非由委员会设计；在很大程度上（有例外）委员会将现有实践标准化。很多库来源于Alexander Stepanov的STL，那么问题是为什么Stepanov选择了二叉树而不是哈希表呢？为什么没有人提出哈希表的建议，直到太晚——当这个提议被提出时，委员会非常支持它，但拒绝了它，因为已经太晚将这样的新内容整合到标准中。 - James Kanze

@JamesKanze：重新阅读我的回答，不清楚那是我的猜测。我已经删除了所有内容，并转向了您的评论。 - Matthieu M.

获取第n个元素，获取前n个元素，获取[a，b]范围内的元素。+1为新手提供教育！ - Jesvin Jose

Answer 3

这是语言设计者更或多或少随意的选择。在C++的情况下，我猜测（但不确定）的动机是希望定义严格的复杂性上限：设计一个好的哈希函数并不容易，具有较差哈希函数的哈希表性能非常差。另一个可能考虑的问题是已经有一个用于排序的运算符（<）；对于哈希，没有类似的东西。

在Python（和许多其他语言）的情况下，很多时候，键将是内置类型，比如str（在STL被定义时，std::string还不可用），因此可以确保有足够好的哈希函数。当一切都是对象，并继承自一个共同的基类时，您可以通过在通用基类中定义一个（虚拟）函数来轻松定义hash的标准接口。

最后，C++解决方案依赖于单个函数/运算符；哈希表需要两个（哈希函数和相等性），它们必须兼容，这更容易出错。在Java中的一个常见错误是定义了equals，但没有定义hashCode；我猜想有些Python类也会犯同样的错误（定义__cmp__或__eq__，但没有定义__hash__）。当然，考虑到人们在C++中搞砸<运算符的次数，我不确定它是否安全:-)。

- James Kanze

Answer 4

Python哈希表永远不会超过2/3的容量。它们在增长时进行调整（从大小8开始，然后每次增加四倍，直到50000，然后再翻倍）。这使得它们具有平摊O（1）插入，删除和查找。可能存在过多的冲突，但很少见。

- Raymond Hettinger