为什么不为所有东西使用散列/哈希表？

Question

在计算机科学中,据说哈希表的插入,删除和搜索操作具有O(1)的复杂度,这是最好的.所以,我想知道,为什么我们需要使用其他数据结构,因为散列操作如此之快？为什么我们不能简单地使用哈希/哈希表来处理所有事情？

Answer 1

平均而言,散列表具有极好的插入,检索和删除时间复杂度.但:

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

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

3. 有些操作没有被散列表有效支持,例如迭代其键在一定范围内的所有元素,找到具有最大键或最小键的元素,等等.

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

Answer 2

您可以使用哈希来搜索元素，但是不能使用它来快速查找最大数量，例如，应针对特定问题使用数据结构。哈希不能解决所有问题。

Answer 3

• HashTable不是所有人的答案。如果您的散列函数不能很好地分配您的密钥，hashMap那么linkedList在最坏的情况下可能会变成插入，删除，搜索将O(N)在最坏的情况下进行。

• HashMap具有显着的内存占用，因此在某些用例中，您的内存比时间复杂度更宝贵，那么您HashMap可能不是最佳选择。

• HashMap不是范围查询或前缀查询的答案。这就是为什么大多数数据库供应商确实通过Btree而不是仅通过对范围或前缀查询进行散列来实现索引。

• HashTable 通常表现出较差的引用局部性，即要访问的数据在内存中似乎是随机分布的。

• 对于某些字符串处理应用程序，例如拼写检查，哈希表的效率可能低于尝试、有限自动机或 Judy 数组。此外，如果每个键由足够少的位表示，则可以将键直接用作值数组的索引，而不是哈希表。请注意，在这种情况下没有冲突。