一尘不染

为什么不对所有内容使用哈希/哈希表?

algorithm

在计算机科学中,据说哈希表的插入,删除和搜索操作的复杂度为O(1),这是最好的。因此,我想知道,既然哈希运算是如此之快,为什么还要使用其他数据结构呢?为什么我们不能仅对所有内容使用哈希/哈希表?


阅读 295

收藏
2020-07-28

共1个答案

一尘不染

平均而言,哈希表在插入,检索和删除方面确实具有出色的时间复杂度。但:

  1. Big-O并不是全部。该 常数因子 也是非常重要的。您可以使用哈希表代替数组,并将数组索引用作哈希键。无论哪种情况,检索项目的时间复杂度均为O(1)。但常数因子是 方式 为哈希表更高,而不是阵列。

  2. 内存消耗可能更高。如果使用哈希表替换数组,则肯定是这样。(当然,如果数组很稀疏,则哈希表可能会占用更少的内存。)

  3. 哈希表无法有效地支持某些操作,例如,对键在一定范围内的所有元素进行迭代,查找具有最大键或最小键的元素,等等。

所有这一切不谈,你 仍然有一个好点。哈希表具有非常广泛的合适用例。这就是为什么它们是某些脚本语言(例如Lua)中主要的内置数据结构的原因。

2020-07-28