c++ - 为什么 python 的 dict 实现为哈希表，而 std::map 是基于树的？

Question

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

c++的map vs python的dict

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

一棵树保证有 O(log n)。
而哈希表没有任何保证，除非由于可​​能的冲突而事先知道输入。
我倾向于认为哈希表的性能会随着问题规模的增大而接近 O(n)。
因为我还没有听说过随着问题大小的增长动态调整其表大小的哈希函数。

因此，哈希表只对特定范围的问题大小有用，这就是为什么大多数数据库使用树而不是哈希表。

Answer 1

新的 C++ 标准具有 std::unordered_map 类型 which is a hash table . IIRC 他们也希望它进入以前的标准，但是在讨论期间没有足够的时间，所以它被遗漏了。然而，大多数流行的编译器多年来都以一种或另一种方式提供它。

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

---

至于你对哈希表的理解不准确:

I haven't heard of a hash function that dynamically adjust its table size as problem size grows

所有重要的哈希表实现都会动态调整自身以适应不断增长的输入，方法是分配更大的数组并重新散列所有键。虽然这个操作很昂贵，但如果设计得当(很少做)，性能仍然可以摊销 O(1)。