为什么不使用哈希表/哈希表的一切？ [英] Why not use hashing/hash tables for everything?

问题描述

在计算机科学中，据说哈希表的插入，删除和搜索操作具有O（1）的复杂性，这是最好的。所以，我想知道，为什么我们需要使用其他数据结构，因为散列操作是如此之快？为什么我们不能简单地为所有东西使用哈希表？

解决方案

平均来说，哈希表有很好的时间插入，检索和删除的复杂性。但是：

1. Big-O的复杂性并不是一切。 常数因子也非常重要。您可以使用散列表代替数组，数组索引作为散列键。在任一情况下，检索项目的时间复杂度为O（1）。但是与数组相反，常数因子是散列表的方式。




2. 内存消耗可能会高得多。如果您使用散列表来替换数组，这一点是正确的。 （当然，如果数组是稀疏的，则散列表可能会占用更少的内存。）




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

所有这一切，你做仍然有一个好点。 Hashtables具有非常广泛的适用用例。这就是为什么他们是一些脚本语言的主要内置数据结构，如Lua。

In computer science, it is said that the insert, delete and searching operations for hash tables have a complexity of O(1), which is the best. So, I was wondering, why do we need to use other data structures since hashing operations are so fast? Why can't we just simply use hashing/hash tables for everything?

解决方案

Hash tables, on average, do have excellent time complexity for insertion, retrieval, and deletion. BUT:

1. Big-O complexity isn't everything. The constant factor is also very important. You could use hashtables in place of arrays, with the array indexes as hash keys. In either case, the time complexity of retrieving an item is O(1). But the constant factor is way higher for the hash table as opposed to the array.

2. Memory consumption may be much higher. This is certainly true if you use hash tables to replace arrays. (Of course, if the array is sparse, then the hash table may take less memory.)

3. There are some operations which are not efficiently supported by hash tables, such as iterating over all the elements whose keys are within a certain range, finding the element with the largest key or smallest key, and so on.

All of that aside, you do still have a good point. Hashtables have an extraordinarily broad range of suitable use cases. That's why they are the primary built-in data structure in some scripting languages, like Lua.

这篇关于为什么不使用哈希表/哈希表的一切？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！