我在SO上看到一些有关Java哈希表及其O(1)
查找时间的有趣说法。有人能解释下为什么会这样吗?除非这些哈希表与我曾经接触过的任何哈希算法大不相同,否则必定存在包含冲突的数据集。
如果是这样,查找时间将会是O(n)
而不是O(1)
。
有人能解释一下它们是否真的是O(1),如果是,它们是如何做到的吗?
我在SO上看到一些有关Java哈希表及其O(1)
查找时间的有趣说法。有人能解释下为什么会这样吗?除非这些哈希表与我曾经接触过的任何哈希算法大不相同,否则必定存在包含冲突的数据集。
如果是这样,查找时间将会是O(n)
而不是O(1)
。
有人能解释一下它们是否真的是O(1),如果是,它们是如何做到的吗?
这基本上适用于大多数编程语言中的大多数哈希表实现,因为算法本身并没有真正改变。
如果表中不存在冲突,您只需要进行一次查找,因此运行时间为O(1)。 如果存在冲突,则必须进行多次查找,这会将性能降至O(n)。
这取决于您选择的算法来避免碰撞。如果您的实现使用分离链接,则最坏情况发生在每个数据元素都散列到相同的值(例如,哈希函数选择不当)。在这种情况下,数据查找与链表上的线性搜索没有区别,即O(n)。但是,发生这种情况的概率很小,查找的最佳和平均情况仍然保持恒定,即O(1)。
当然,哈希表的性能将取决于给定对象的hashCode()函数的质量。但是,如果该函数的实现使得碰撞的可能性非常低,那么它将具有非常好的性能(在大多数情况下,这不是严格的O(1),但在大多数情况下都是如此)。
例如,在Oracle JRE中的默认实现是使用随机数(存储在对象实例中,以便它不会改变 - 但它也禁用了偏向锁定,但这是另一个讨论),因此碰撞的机会非常低。
hashCode % tableSize
来确定,这意味着可能会发生碰撞。您没有充分利用32位。这就是哈希表的重点...将大的索引空间缩小到一个小的空间。 - FogleBird除了学术方面,从实际角度来看,哈希映射应该被接受为具有无关紧要的性能影响(除非您的分析器告诉您不同)。