algorithm - 为什么不对所有内容都使用哈希/哈希表？

Question

在计算机科学中，据说哈希表的插入、删除和查找操作的复杂度为O(1)，这是最好的。所以，我想知道，既然散列运算这么快，为什么我们需要使用其他数据结构呢？为什么我们不能简单地对所有内容使用哈希/哈希表？

Answer 1

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

1. Big-O 复杂性并不是一切。 常数因子 也很重要。您可以使用哈希表代替数组，将数组索引作为哈希键。在任何一种情况下，检索项目的时间复杂度都是 O(1)。但是与数组相比，哈希表的常数因子方式更高。

2. 内存消耗可能会高得多。如果您使用哈希表代替数组，这当然是正确的。 (当然，如果数组是稀疏的，那么哈希表可能会占用更少的内存。)

3. 有一些操作是哈希表不能有效支持的，例如迭代所有键在一定范围内的元素，找到具有最大键或最小键的元素等。

4. O(n) 复杂度平均。对于某些极端情况(例如，所有数据都落在同一个桶中)，效率会很低。

除此之外，您确实还有一个很好的观点。哈希表具有非常广泛的合适用例。这就是为什么它们是某些脚本语言(例如 Lua)中的主要内置数据结构。