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

Question

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

c ++的地图与python的字典

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

树保证有O(log n).
哈希表无法保证,除非由于可​​能的冲突而先前已知输入.
随着问题规模越来越大,我倾向于认为哈希表的性能会接近O(n).
因为我没有听说过随着问题规模的增长动态调整其表大小的哈希函数.

因此,哈希表仅对某些问题大小范围有用,这就是大多数数据库使用树而不是哈希表的原因.

Answer 1

新的C++标准具有哈希表的std::unordered_map类型.IIRC他们希望它也能达到以前的标准,但是在讨论期间没有足够的时间,所以它被排除在外.但是,大多数流行的编译器多年来以这种或那种方式提供它.

换句话说,不要太担心它.使用适当的数据结构来完成手头的任务.

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

我没有听说过随着问题规模的增长动态调整其表大小的哈希函数

所有严重的哈希表实现通过分配更大的数组并重新散列所有键来动态调整自身以增加输入.虽然这种操作很昂贵,但如果设计得当(足够少),性能仍然是摊销的(1).

Answer 2

您对哈希表(以及使用它们的人)的理解是有缺陷的.

问题是,哈希表是一个相当模糊的术语.引擎盖下有许多实现......但首先让我们谈谈BST(二进制搜索树)的使用.

为什么C++使用二叉搜索树？

C++由commitee设计,有许多可能的哈希表实现导致广泛不同的特性,而最流行的BST(红黑树和AVL树)实现具有几乎相同的特征.因此,他们并没有彻底拒绝哈希表,他们只是无法决定选择的特征和向用户公开的细节.

看詹姆斯坎泽的评论,提案来得太晚了詹姆斯问了一个有趣的问题,为什么斯捷潘诺夫没有先提出它.我仍然怀疑选择的数​​量是罪魁祸首.

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

首先,让我们来看一个数据库软件.我会选择Oracle,因为它既有广泛记录,也有典型的SQL数据库.Oracle提供两种类型的索引:位图和搜索树.

注意:它们不使用BINARY搜索树,而是使用B +树,它们具有更多的IO和缓存友好性

哈希表和搜索树之间存在根本区别:后者是排序的.许多数据库操作意味着排序:

• 得到第n个元素
• 得到前n个元素
• 得到[a,b]中的元素

在所有这些情况下,哈希表都是无用的.

此外,数据库需要处理大量数据集(通常),这意味着他们需要组织数据以最小化IO(磁盘读/写).这里,搜索树的排序特性意味着(在索引中)可能一起访问的元素(因为它们共享很多)也将被组合在一起而不是分散到磁盘的四个角.

最后,内部 Oracle可能会在其执行计划中使用哈希表.当您执行需要两组行交集的操作时,优化引擎可能会决定将(临时)集存储在哈希表中是最快的方法.

现在,关于表现.

实际上,搜索树的性能通常是众所周知的,易于理解O(log N)很好而且整洁.

另一方面,正如我所说,有许多不同的哈希表实现可能,以及处理增长和收缩的策略......肯定更复杂.

一个简单的结构示例,哈希表可以使用:

• 打开寻址:哈希表是一个元素数组,哈希表示放置元素的数组的插槽,如果插槽已满,则有一个策略来定位另一个插槽.相同的策略用于搜索.
• 存储桶:哈希表是一个指向存储桶的指针数组,哈希表示存储元素的存储区的插槽.假设铲斗可以无限增长.

这两种策略具有极其不同的特性,后者的特性也取决于桶的实现(易于实现的是使用简单的链表).

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

我个人的建议？要挑之间unordered_map,并map在C++中,我简单地问自己,我是否需要排序的元素或没有.如果我需要它们进行排序我使用a map,否则我使用a unordered_map.大多数时候,表演都是一样好,所以它只是语义.

Answer 3

它或多或少是语言设计者的随意选择.在C++的情况下,我怀疑(但不确定)动机是为复杂性定义严格上限的愿望:设计一个好的哈希函数并不简单,并且散列表具有较差的散列函数表现很差.可能已经考虑的另一个问题是有一个已建立的运营商用于订购(<); 哈希没有类似的东西.

在Python(和许多其他语言)的情况下,很多时候,键将是内置类型,str(std::string在定义STL时不可用),因此您可以确保足够的散列函数.当一切都是一个对象,并从公共基类继承时,您可以hash通过在univeral基类中定义(虚拟)函数来轻松定义标准接口 .

最后,C++解决方案依赖于单个函数/运算符; 哈希表需要两个(哈希函数和相等),它必须兼容,这更容易出错.Java中的一个常见错误是定义equals,但不定义hashCode; 我怀疑有些Python会犯同样的错误(定义__cmp__或 __eq__不定义__hash__).当然,看到人们<用C++ 搞乱操作员的次数,我不确定它是否安全:-).