如果哈希表包含N个不同的项，并且没有过载，则N个项的哈希值必须具有大约lg（N）位，否则太多的项将获得相同的哈希值。
但是通常认为哈希表查找平均需要O（1）时间。
无法在O（1）的时间内生成lg（N）位，因此散列表复杂性的标准结果是错误的。
我的推理怎么了？
您的推理有问题的地方是使用了相互矛盾的“时间”定义。
当有人说在哈希表中查找需要O（1）时间时，通常意味着它需要进行O（1）比较，也就是说，找到一个项目所需的比较次数以一个常量为界。在“时间”的概念下，用于计算哈希的实际时间（如您将以秒为单位进行度量）不会引起变化。
在比较中测量时间是一个近似值，尽管它可能无法像以秒为单位测量时间那样反映现实，但仍可提供有关哈希表行为的有用信息。
对于大多数算法的渐近复杂度描述，这种情况是正确的：人们经常使用“时间”来表示非常抽象的含义，这不是“时间”的非正式含义，但通常是“操作次数”的某种变体”（这种操作通常不加说明，应该是显而易见的，或者从上下文中清楚可见）。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句