我在SO上看到一些有关Java哈希表及其O(1)查找时间的有趣说法。有人能解释下为什么会这样吗？除非这些哈希表与我曾经接触过的任何哈希算法大不相同，否则必定存在包含冲突的数据集。
如果是这样，查找时间将会是O(n)而不是O(1)。
有人能解释一下它们是否真的是O(1)，如果是，它们是如何做到的吗？
Java中的哈希表搜索是否真的是O(1)？
190
- paxdiablo
2
2我知道这可能不是一个答案，但我记得维基百科有一篇关于这个话题的非常好的文章。别错过性能分析部分。 - victor hugo
32大O符号为你正在进行的特定类型分析提供了一个上限。但仍需指明你是否感兴趣于最坏情况、平均情况等。 - Dan Homerick
15个回答
1
只有在理论情况下，当哈希码始终不同且每个哈希码的桶也不同时，O(1) 才存在。否则，它的时间复杂度将保持不变，即在 hashmap 增量的情况下，搜索的顺序仍然是恒定的。
- sn.anurag
1
这基本上适用于大多数编程语言中的大多数哈希表实现，因为算法本身并没有真正改变。
如果表中不存在冲突，您只需要进行一次查找，因此运行时间为O(1)。 如果存在冲突，则必须进行多次查找，这会将性能降至O(n)。
- Tobias Svensson
1
1这假设运行时间受查找时间的限制。在实践中，您会发现很多情况下哈希函数提供了边界（字符串）。 - Stephan Eggermont
1
这取决于您选择的算法来避免碰撞。如果您的实现使用分离链接，则最坏情况发生在每个数据元素都散列到相同的值（例如，哈希函数选择不当）。在这种情况下，数据查找与链表上的线性搜索没有区别，即O(n)。但是，发生这种情况的概率很小，查找的最佳和平均情况仍然保持恒定，即O(1)。
- Nizar Grira
0
当然，哈希表的性能将取决于给定对象的hashCode()函数的质量。但是，如果该函数的实现使得碰撞的可能性非常低，那么它将具有非常好的性能（在大多数情况下，这不是严格的O(1)，但在大多数情况下都是如此）。
例如，在Oracle JRE中的默认实现是使用随机数（存储在对象实例中，以便它不会改变 - 但它也禁用了偏向锁定，但这是另一个讨论），因此碰撞的机会非常低。
- Grey Panther
7
8这是错误的。哈希表中的索引将通过
hashCode % tableSize 来确定，这意味着可能会发生碰撞。您没有充分利用32位。这就是哈希表的重点...将大的索引空间缩小到一个小的空间。 - FogleBird2你不能保证不会发生冲突，因为地图的大小比哈希的大小小：例如，如果地图的大小为两个，则在尝试插入三个元素时（无论哈希如何），都会发生冲突。 - ChrisW
如果你的哈希表键是对象地址，那么你根本不需要哈希表。关键是要有一个相对较小的表（例如255个桶），并且具有均匀分布。然后您可以预测每个桶将包含大约相同数量的项。 - vgru
1我相信如果你不实现hashCode，它会使用对象的内存地址。但是标准Oracle Java的默认hashCode实际上是一个25位随机数存储在对象头中，因此64/32位并不重要。 - Boann
@Boann - 这完全正确，我会编辑回复以反映这一点。 - Grey Panther
显示剩余2条评论
0
除了学术方面，从实际角度来看，哈希映射应该被接受为具有无关紧要的性能影响（除非您的分析器告诉您不同）。
- Ryan Emerle
1
4在实际应用中，并非所有的哈希函数都是理想的，有些会很慢。一旦你将字符串用作键，就会注意到这一点。 - Stephan Eggermont
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接