你对哈希表的理解(以及谁使用它们)存在缺陷。
问题在于,哈希表是一个相当模糊的术语。底层有许多实现...但首先让我们谈谈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
。大多数情况下,性能都很好,所以这只是语义。