为什么 python 的 dict 是作为哈希表实现的，而 std::map 是基于树的？
为什么一种语言使用树而另一种语言使用哈希表来实现看似相似的数据结构？
c++ 的 map 与 python 的 dict
一个相关的问题是关于哈希表的性能。
请在下面评论我对哈希表的理解。
一棵树保证有 O(log n)。
而哈希表则无法保证，除非由于可能发生冲突而事先已知输入。
我倾向于认为随着问题规模变大，哈希表的性能将变得接近 O(n)。
因为我还没有听说过随着问题大小的增长而动态调整其表大小的哈希函数。
因此，哈希表仅对特定范围的问题大小有用，这就是为什么大多数数据库使用树而不是哈希表的原因。
Why one languages uses tree and another uses hash table for seemingly similar data structure?
c++'s map vs python's dict
A related question is about performance of hash table.
Please comment on my understanding of hash table below.
A tree is guaranteed to have O(log n).
Whereas hash table has no guarantee unless inputs are previously known because of possible collisions.
I tend to think hash table's performance would become close to O(n) as problem size gets bigger.
Because I haven't heard of a hash function that dynamically adjust its table size as problem size grows.
Hence, hash table is only useful for certain range of problem size, and that's why most DB uses tree than hash table.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
发布评论
评论（4）
您对哈希表（以及谁使用它们）的理解是有缺陷的。
问题是，哈希表是一个相当模糊的术语。在幕后有很多实现......但首先我们来谈谈 BST（二叉搜索树）的使用。
为什么 C++ 使用二叉搜索树？
C++是由委员会设计的，哈希表有多种可能的实现，导致特性差异很大，而BST（红黑树和AVL树）最流行的实现具有几乎相同的特性。因此，他们并没有彻底拒绝哈希表，他们只是无法确定要选择的特征和向用户公开的细节。
参见 James Kanze 的评论，该提案来得太晚了，James 提出了一个有趣的问题：为什么斯捷潘诺夫没有首先提出它。我仍然怀疑选择的数量是罪魁祸首。
为什么数据库使用搜索树？
首先，让我们选择一个数据库软件。我会选择 Oracle，因为它有广泛的文档记录，而且是 SQL 数据库的典型代表。 Oracle 提供两种类型的索引：位图和搜索树。
注意：它们不使用二进制搜索树，而是使用对 IO 和缓存更友好的 B+树
哈希表和搜索树之间有一个根本区别：后者是排序的。许多数据库操作都意味着排序：
- 获取第 n 个元素
- 获取前 n 个元素
- 获取 [a,b] 中的元素
在所有这些情况下，哈希表都是无用的。
此外，数据库需要处理巨大的数据集（通常），这意味着它们需要组织数据以最大限度地减少 IO（磁盘读/写）。在这里，搜索树的排序性质意味着（在索引中）可能一起访问的元素（因为它们共享很多）也将被分组在一起，而不是分散到磁盘的四个角。
最后，Oracle内部可以在其执行计划中使用哈希表。当您执行需要两组行的交集的操作时，优化引擎可能会决定将（临时）集存储在哈希表中是最快的方法。
现在，关于性能。
事实上，搜索树的性能众所周知且易于理解，O(log N) 非常好且整洁。
另一方面，正如我所说，有许多不同的哈希表实现可能，以及处理增长和收缩的策略......肯定更复杂。
一个简单的结构示例，哈希表可以使用：
- 开放寻址：哈希表是一个元素数组，哈希表示数组中放置元素的槽，如果槽已满，则有策略定位另一个插槽。搜索也使用相同的策略。
- Buckets：哈希表是指向桶的指针数组，散列表示桶中放置元素的槽位。假设桶可以无限增长。
这两种策略具有截然不同的特性，而后者的特性也取决于桶的实现（简单的实现是使用简单的链表）。
但即使您选择一个实现，它的性能也是基于哈希函数分布，而哈希函数分布根据输入序列本身而变化！
我个人的建议？要在 C++ 中的 unordered_map 和 map 之间进行选择，我只需问自己是否需要排序元素。如果我需要对它们进行排序，我会使用 map，否则我会使用 unordered_map。大多数时候，性能无论如何都一样好，所以这只是语义。
这或多或少是语言设计者的任意选择。在
对于 C++ 的情况，我怀疑（但不确定）动机是
定义严格的复杂性上限的愿望：设计一个好的
哈希函数并不是微不足道的，并且哈希函数的哈希表也很差
表现很差。另一个可能考虑的问题是
事实上，有一个已建立的排序运算符 (<)；那里
对于散列来说没有什么相似之处。
就 Python（以及许多其他语言）而言，很多时候，
键将是内置类型，例如 str （std::string 不是
在定义 STL 时可用），因此您可以确保足够的
哈希函数。当一切都是对象并且继承自
通用基类，您可以轻松定义标准接口hash，通过在通用基类中定义一个（虚拟）函数来实现。
最后，C++ 解决方案依赖于单个函数/运算符；一个哈希值
表需要两个（哈希函数和相等），其中必须
兼容，这样更容易出错。 Java 中的一个常见错误是
定义equals，但不定义hashCode；我怀疑有
犯同样错误的 Python 类（定义 __cmp__ 或__eq__，但不是 __hash__）。当然，看次数
人们搞乱了 C++ 中的 < 运算符，我不确定它是否那么安全
任何一个：-）。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
新的 C++ 标准具有
std::unordered_map类型 哈希表。 IIRC 他们也希望将其纳入之前的标准，但讨论期间没有足够的时间，因此将其排除在外。然而，多年来，大多数流行的编译器都以这种或那种方式提供它。换句话说，不用太担心。使用正确的数据结构来完成手头的任务。
至于你对哈希表的理解是不准确的：
所有严肃的哈希表实现都会通过分配更大的数组并重新散列所有键来动态调整自身以适应不断增长的输入。尽管此操作成本高昂，但如果设计得当（很少进行），性能仍可摊销为 O(1)。
The new C++ standard has the
std::unordered_maptype which is a hash table. IIRC they wanted it to get into the previous standard as well, but there was not enough time during the discussions so it was left out. However, most popular compilers provided it in one way or another for years.In other words, don't worry about it too much. Use the proper data structure for the task at hand.
As for your understanding of hash tables, it's inaccurate:
All serious hash table implementation dynamically adjust themselves for growing input, by allocating a larger array and re-hashing all the keys. Although this operation is expensive, if designed properly (to be done rarely enough) the performance is still amortized O(1).