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

Question

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

Answer 1

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

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

内存消耗可能会高得多。如果您使用哈希表来替换数组，这当然是正确的。 （当然，如果数组是稀疏的，那么哈希表可能会占用更少的内存。）
哈希表不能有效支持一些操作，例如迭代键在一定范围内的所有元素、查找键最大或最小的元素等等。
O(1) 复杂度为
4. 平均

   。对于某些极端情况（例如，所有数据都落入同一个桶中），效率会很低。

抛开所有这些，你

确实

仍然有一个很好的观点。哈希表有非常广泛的合适用例。这就是为什么它们是某些脚本语言（例如 Lua）中主要的内置数据结构。

Answer 2

Answer 3

• HashTable

  并不是所有人的答案。如果你的哈希函数没有很好地分配你的密钥，那么在最坏的情况下，

  hashMap

  可能会变成

  linkedList

  ，而插入、删除、搜索在最坏的情况下将需要

  O(N)

  。

• HashMap

  具有显着的内存占用，因此在某些用例中，您的内存比时间复杂度更宝贵，那么您

  HashMap

  可能不是最佳选择。

• HashMap

  不是范围查询或前缀查询的答案。这就是为什么大多数数据库供应商确实通过

  Btree

  实现索引，而不是仅通过范围或前缀查询的哈希来实现。

• HashTable

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

对于某些字符串处理应用程序（例如拼写检查），哈希表的效率可能低于尝试、有限自动机或 Judy 数组。此外，如果每个键都由足够小的位数表示，那么可以直接使用该键作为值数组的索引，而不是哈希表。请注意，这种情况下不会发生碰撞。

Answer 4

哈希表未排序（映射）

1. 哈希表不适合头/尾插入（链接列表/双端队列）
2. 哈希表需要开销来支持搜索（向量/数组）

Answer 5

Answer 6

无论如何，这只是当地代表，对吧？我的意思是，我可以在任何地方共享数据...API、IPC 或 RPC - 但不确定这些散列密钥有多大帮助，除非也嵌入了完整的字符串。

这意味着您只是为了自己的娱乐而花费了大量时间来回散列字符串。

我就把它留在这里...