为什么不将哈希/哈希表用于所有事情？

Question

34

在计算机科学中，散列表的插入、删除和查找操作被认为具有O(1)的复杂度，这是最好的。因此，我想知道，既然哈希操作如此快速，为什么我们需要使用其他数据结构呢？为什么不能仅仅使用散列/散列表来完成所有操作呢？

- Donald

你说的“每个东西”是什么意思？哈希不能应用于每种数据结构。 - user2134086

1

我们确实有这样的东西，它被称为缓存。但是如果你想更进一步，已经有了各种各样的“内容可寻址内存”的提议。（但是在一般情况下，哈希并不像你想象的那么快。） - Hot Licks

2

实际上，哈希表的复杂度为O(log N)，但N是基于最大可能的表大小而非当前大小。 - Hot Licks

@Jeremy Bentham的“万物皆可哈希”意味着使用哈希/哈希表来解决所有问题。 - Donald

AWK语言使用哈希表来处理所有事情。对于许多事情，它都能很好地工作，但有时您需要执行哈希表不支持的操作。 - user448810

显示剩余2条评论

6个回答

8

你可以使用哈希来搜索元素，但是不能用它来快速找到最大的数字，你应该使用特定问题的数据结构。哈希不能解决所有问题。

- thinkinnight

6

HashTable 并不是适用于所有情况的。如果你的哈希函数无法很好地分配密钥, 那么最坏情况下HashMap可能会变成一个linkedList，插入、删除和搜索的时间复杂度将达到O(N)。
HashMap 的内存占用较大，因此在某些情况下，如果您更关注内存而非时间复杂度，则HashMap可能不是最佳选择。
HashMap 并不适用于范围查询或前缀查询。因此，大多数数据库供应商实现索引使用的是 Btree 而不仅仅是哈希用于范围或前缀查询。
HashTable 通常表现出较差的参考局部性，即要访问的数据在内存中似乎随机分布。
对于某些字符串处理应用程序（例如拼写检查），哈希表可能不如 tries、有限状态自动机或 Judy 数组高效。此外，如果每个密钥由足够少的位表示，则可以直接将该密钥用作值数组的索引，而不是哈希表。请注意，在这种情况下，不会发生碰撞。

- Trying

2

还应该指出哈希表在网络上可能存在的安全问题。如果有人知道哈希函数，那么他可以通过创建许多具有相同哈希码的项目来执行拒绝服务攻击。

- mattboy

2

- Glenn Teitelbaum

-1

我不明白，枚举/符号键不够节约吗？ ;) 直接使用原始字符串指针作为键怎么样？我一定忽略了哈希中的一些明显优势...但现在想想，它变得越来越没有意义。

反正这只是本地表示，对吧？我的意思是，我可以在任何地方共享数据...API、IPC或RPC——但不确定除非完整字符串也被嵌入，否则那些哈希键有多大帮助。

这意味着你只是为了自己的娱乐而花费了很多时间来回哈希字符串。

- Christoffer Bubach

我甚至不是在开玩笑，请你们投我反对票的人告诉我我错了哪里？如果你将哈希表与其他库或通过外部链接共享，那么你仍然需要嵌入完整的字符串，所以为什么不使用普通（或肥）指针，哈希似乎是不必要的（在大多数情况下）。 - Christoffer Bubach

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Alex D · Accepted Answer

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

大O复杂度并不是唯一重要的因素，常数因子也非常重要。您可以使用哈希表代替数组，将数组索引作为哈希键。在任一情况下，检索项的时间复杂度都是O(1)。但是相对于数组，哈希表的常数因子要高得多。
内存消耗可能会更高，如果您使用哈希表代替数组，则肯定是如此。（当然，如果数组是稀疏的，则哈希表可能需要更少的内存。）
哈希表不支持某些操作的效率很低，例如：迭代所有键在某个范围内的元素、查找最大键或最小键的元素等。
O(n) 的复杂度是“平均而言”的，对于某些极端情况（例如，所有数据都落入同一个桶中），它可能会变得低效。

除了这些问题，您的观点仍然是正确的。哈希表具有广泛适用的领域，这就是为什么它们是某些脚本语言（例如 Lua）中的主要内置数据结构。