如果散列表包含N个不同的项,并且没有重载,则N个项的散列必须具有大约lg(N)位,否则太多项将获得相同的散列值.
但是哈希表查找通常被认为平均花费O(1)时间.
在O(1)时间内不可能生成lg(N)位,因此散列表复杂性的标准结果是错误的.
我的推理有什么问题？
你的推理有什么问题是使用了相互矛盾的"时间"定义.
当人们说哈希表中的查找花费O(1)时间时,通常意味着它需要进行O(1)比较,也就是说,查找项目所需的比较次数以常数为界.在"时间"这个概念下,用于计算哈希值的实际时间(如用秒测量的东西)不会产生任何变化.
在比较中测量时间是一种近似值,尽管它可能无法以与以秒为单位测量它的方式反映现实,但仍提供有关哈希表行为的有用信息.
对于算法的大多数渐近复杂性描述,这类事情都是正确的:人们经常使用具有非常抽象意义的"时间"而不是"时间"的非正式含义,但通常是"操作次数"的某些变化"(这种操作通常没有说明,预计是显而易见的,或从上下文中清楚).