是在哈希表O（1）中查找吗？ [英] Is a lookup in a hash table O(1)?

问题描述

如果哈希表包含N个不同的项，并且未过载，则N个项的哈希值必须具有大约lg（N）位，否则太多的项将获得相同的哈希值。

If a hash table holds N distinct items, and is not overloaded, then the hashes for the N items must have have approximately lg(N) bits, otherwise too many items will get the same hash value.

但是通常说哈希表查找平均需要O（1）时间。

But a hash table lookup is usually said to take O(1) time on average.

可能会在O（1）的时间内生成lg（N）位，所以散列表复杂度的标准结果是错误的。

It's not possible to generate lg(N) bits in O(1) time, so the standard results for the complexity of hash tables are wrong.

我的推理有什么问题？

推荐答案

您的推理有问题的是使用了时间的冲突定义。

What is wrong with your reasoning is the use of conflicting definitions of "time".

当说哈希表中的查询花费O（1）的时间时，通常意味着需要花费O（1） comparisons （即比较）的次数。查找一个项目，该对象在上面被常量限制。在时间的概念下，用于计算哈希的实际时间（如您将以秒为单位的时间）不会引起变化。

When one says that lookup in a hash table takes O(1) time, one usually means that it takes O(1) comparisons, that is, the number of comparisons required to find an item is bounded above by a constant. Under this idea of "time", the actual time (as in the thing you would measure in seconds) used to compute the hash causes no variation.

比较中的测量时间是一个近似值，尽管它可能无法像以秒为单位进行度量那样反映真实性，但仍可以提供有关哈希表行为的有用信息。

Measuring time in comparisons is an approximation that, while it may not reflect reality in the same way that measuring it in seconds would, still provides useful information about the behaviour of the hash table.

对于大多数渐近复杂度算法描述，这种情况是正确的：人们经常使用时间来表示非常抽象的含义，这不是时间的非正式含义，但通常是操作次数的某种变化。 （这种操作通常不加说明，应该是显而易见的，或者从上下文中清楚可见）。

This sort of thing is true for most asymptotic complexity descriptions of algorithms: people often use "time" with a very abstract meaning that isn't the informal meaning of "time", but more often than not is some variation of "number of operations" (with the kind of operation often left unstated, expected to be obvious, or clear from context).

这篇关于是在哈希表O（1）中查找吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！