如果哈希表保存 N 个不同的项，并且没有过载，则 N 个项的哈希值必须具有大约 lg(N) 位，否则太多项将获得相同的哈希值。
但是通常认为哈希表查找平均需要 O(1) 时间。
不可能在 O(1) 时间内生成 lg(N) 位，因此哈希表复杂度的标准结果是错误的。
我的推理有什么问题吗？
你的推理的问题在于使用了相互冲突的“时间”定义。
当人们说哈希表中的查找需要 O(1) 时间时，通常意味着它需要 O(1) 比较，也就是说，查找一项所需的比较次数以常数为界。在这种“时间”的概念下，用于计算哈希值的实际时间（如以秒为单位测量的时间）不会导致任何变化。
在比较中测量时间是一个近似值，虽然它可能无法像以秒为单位进行测量那样反映现实，但仍然提供有关哈希表行为的有用信息。
对于大多数算法的渐近复杂性描述来说，这种情况都是正确的：人们经常使用具有非常抽象含义的“时间”，这不是“时间”的非正式含义，但更常见的是“时间的数量”的某种变体操作”（这种操作通常没有说明，期望是显而易见的，或者从上下文中可以清楚地看出）。
分析基于哈希函数是固定的并且与表中实际存储的元素数量无关的假设。该分析不是说如果哈希表中有 N 个元素，哈希函数就会返回 lg N 位值，而是基于返回 k 位值的哈希函数，其中 k 是独立于N。 k 的典型值（例如 32 或 64）提供的哈希表远大于您实际需要的任何值。
所以从某种意义上来说，是的，一个包含 N 个元素的表需要一个返回 O(lg n) 位的哈希函数；但实际上，使用的常数远大于 lg n 的预期最大值。
当我们陈述哈希表插入的复杂性时，我们并不是在谈论哈希表插入的一些抽象概念。我们正在讨论一种用于哈希表插入的特定算法，或者更准确地说，是一类仅在不相关细节上有所不同的算法。
“哈希表插入”算法根据表中元素的数量生成可变长度哈希，因此当元素较多时需要更多时间进行哈希，这是不寻常的。除非明确说明，否则当我们给出“哈希表插入”的复杂性时，这不是我们所讨论的算法。
现在，为一种称为“RAM（随机存取机）”的计算机编写了一个普通的“哈希表插入”算法，这种计算机在时间复杂度方面与普通计算机相似。这使得我们对复杂性的陈述有用。但与普通计算机不同的是，RAM 没有指定的内存限制。然而，仍然假设地址大小的数字可以在恒定时间内进行操作，这也是真实计算机的一个特性。 在普通的哈希表实现中，哈希的大小是计算机地址大小的有界倍数，因此当您说“不可能在 O(1) 时间内生成 log(N) 位”时，您就错了。如果 log(N) 是机器地址大小的有界倍数，那么这是可能的，普通哈希表就是这种情况。
哈希表搜索是 O(1)。 我认为你正在混合插入（即 O(n)）和搜索。