我不明白这个解释说明如果n是散列表中的元素数量而m是桶的总数，那么只有当n与theta（n）成比例时，散列表才具有平均的持续访问时间。为什么它必须成比例？
我不明白这个解释说明如果n是散列表中的元素数量而m是桶的总数，那么只有当n与theta（n）成比例时，散列表才具有平均的持续访问时间。为什么它必须成比例？
实际上m应该与n成比例。否则你可以，例如，只有一个桶，它就像一个未排序的集。
更确切地说，如果m与n成比例，即m = c * n，那么每个桶中的项目数将是n / m = 1 / c，这是常数。进入任何存储桶是一个O（1）操作（只是计算哈希码），然后通过存储桶的搜索是不变的顺序（你可以只通过存储桶中的项目进行线性搜索，这将是一个常量）。
因此，如果m = c * n，则算法的阶数为O（1）。
举一个相反的例子，假设我们有一个大小为tableSize的固定大小的表。然后每个桶中预期的项目数是n / tableSize，它是n的线性函数。通过存储桶的任何类型的搜索充其量只是一个树的O（log（n））（我假设你没有在存储桶中粘贴另一个哈希表，或者我们在该哈希表上有相同的参数），所以在这种情况下，它不会是O（1）。
实际上m应该与n成比例。否则你可以，例如，只有一个桶，它就像一个未排序的集。
更确切地说，如果m与n成比例，即m = c * n，那么每个桶中的项目数将是n / m = 1 / c，这是常数。进入任何存储桶是一个O（1）操作（只是计算哈希码），然后通过存储桶的搜索是不变的顺序（你可以只通过存储桶中的项目进行线性搜索，这将是一个常量）。
因此，如果m = c * n，则算法的阶数为O（1）。
举一个相反的例子，假设我们有一个大小为tableSize的固定大小的表。然后每个桶中预期的项目数是n / tableSize，它是n的线性函数。通过存储桶的任何类型的搜索充其量只是一个树的O（log（n））（我假设你没有在存储桶中粘贴另一个哈希表，或者我们在该哈希表上有相同的参数），所以在这种情况下，它不会是O（1）。
严格地说，哈希表访问的平均时间复杂度实际上是Ω（n1/3）。信息的传播速度不能超过光速，这是一个常数。由于空间有三个维度，存储 n 数据位要求某些数据位于n的数量级上1/3 来自CPU。
更多详情 在我的博客中。
碰撞的可能性更高，因此必须扫描具有相同散列密钥的项目列表的发生率也更高。
访问时间是不变的，因为访问基于哈希值的计算，然后是常量查找以查找适当的桶。假设散列函数在桶之间均匀分配项目，则访问任何单个项目所花费的时间将等于访问其他项目的时间，而不管n。
常数并不一定意味着持续低。平均访问时间与散列函数的均匀分布和桶的数量有关。如果您有数千个项目均匀分布在少量存储桶中，那么您可以快速找到存储桶，然后循环查看存储桶中的大量项目。如果您对项目有很大比例的桶，但是哈希函数错误会将更多项目放在某些桶中而不是其他桶中，则较大桶中项目的访问时间将比其他项目的访问时间慢。
一个合理大小的哈希表，其中有足够的插槽用于存储的每个元素以及足够的额外空间，将具有散列函数执行大多数工作选择插槽和非常少的冲突，其中不同的元素具有相同的散列。一个非常拥挤的哈希表会有很多冲突，并且会降级为基本上线性搜索，其中几乎每个查找都将是一个具有相同哈希的错误项目，并且您将不得不继续搜索正确的哈希表（哈希表）查找仍然必须在选择第一个插槽后检查密钥，因为它所查找的密钥在存储时可能发生了冲突。
确定命中碰撞比率的确切因素是项目数与散列大小的比率（即，随机选择的时隙将被填充的百分比）。