为什么散列表的平均访问时间不变？

我不明白这个解释，它说如果n是散列表中元素的数量，m是桶的总数，那么只有当n与theta（n）成比例时，散列表的平均访问时间才是平均值。为什么它必须是成比例的？为什么散列表的平均访问时间不变？

2011-05-04 phoenix

实际上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）。

来源

2011-05-04 01:24:05

要添加到此答案，不仅在两者成比例时，而且当元素数（'n'）小于或等于桶数（'m'）时，可以获得常量访问时间。否则，我们有'O（1 + | k |）'的情况，其中k是第k个桶中元素的数量。 – 2011-05-04 01:28:56

这仍然是不变的访问时间。如果k是常数，则O（1 + | k |）= O（1）。 – 2011-05-04 02:18:27

如果我们使用开放寻址来解决冲突，而不是链接，那么几乎每个哈希表的分析都假设为？即使m与n成正比，平均常数访问时间是否仍然保持不变？ – sinoTrinity 2014-12-21 17:51:56

碰撞的可能性更高，因此必须扫描具有相同散列键的项目列表的发生率也更高。

来源

2011-05-04 01:26:34

访问时间是恒定的，因为访问基于哈希值的计算，然后通过查找来查找合适的存储桶。假设散列函数在桶之间均匀分配项目，那么访问任何单个项目所需的时间将等于访问其他项目的时间，而不管n是多少。

常量并不一定意味着虽然低。平均访问时间与散列函数的均匀分布和桶的数量有关。如果您有数千个物品均匀地分布在少量的桶中，您可以快速找到桶，然后循环通过桶中的很多物品。如果你有很大比例的桶到项目，但是一个坏的散列函数会把更多的项目放在一些桶中而不是其他桶中，那么大桶中的项的访问时间将比其他项的访问时间慢。

来源

2011-05-04 01:28:23

合理大小的哈希表，那里有足够的插槽，每次存储和大量的额外的空间元素，将有散列函数做了大部分工作选择插槽和极少数的碰撞，不同的元素具有相同的哈希。一个非常拥挤的散列表将会有很多冲突，并且会降级到基本的线性搜索，几乎每个查找都将是一个具有相同散列的错误项目，并且您必须继续搜索正确的项目（散列表查找仍然必须检查密钥，一旦它选择第一个槽，因为它所查找的密钥在存储时可能会发生冲突）。

什么决定了命中碰撞比是完全数的项的大小-的哈希的比率（即，百分比的机会，一个随机选择的时隙将被填充）。

来源

2011-05-04 01:32:19

严格地说，散列表访问的平均情况时间复杂度实际上是Ω（n ^1/3）。信息不能比光速快，这是一个常数。由于空间具有三个维度，存储数据的n位时，要求一些数据以一定距离位于Ñ^1/3的来自CPU的数量级上。

更多详细信息in my blog。

来源

2011-05-04 01:35:11

为什么散列表的平均访问时间不变？

回答

相关问题