我已经看到一些关于 SO re Java hashmaps 及其O(1)
查找时间的有趣声明。有人可以解释为什么会这样吗?除非这些哈希图与我购买的任何哈希算法有很大不同,否则必须始终存在包含冲突的数据集。
在这种情况下,查找将是O(n)
而不是O(1)
.
有人可以解释他们是否是O(1),如果是,他们是如何实现的?
我已经看到一些关于 SO re Java hashmaps 及其O(1)
查找时间的有趣声明。有人可以解释为什么会这样吗?除非这些哈希图与我购买的任何哈希算法有很大不同,否则必须始终存在包含冲突的数据集。
在这种情况下,查找将是O(n)
而不是O(1)
.
有人可以解释他们是否是O(1),如果是,他们是如何实现的?
HashMap 的一个特殊特性是与平衡树不同,它的行为是概率性的。在这些情况下,根据最坏情况事件发生的概率来讨论复杂性通常是最有帮助的。对于哈希映射,这当然是关于映射恰好有多满的冲突的情况。碰撞很容易估计。
p碰撞= n / 容量
因此,即使元素数量适中的哈希映射也很可能至少会发生一次冲突。大 O 表示法允许我们做一些更有说服力的事情。对于任意的固定常数 k,请注意这一点。
O(n) = O(k * n)
我们可以使用这个特性来提高哈希映射的性能。相反,我们可以考虑最多 2 次碰撞的概率。
p碰撞 x 2 = (n / 容量) 2
这要低得多。由于处理一次额外碰撞的成本与 Big O 性能无关,因此我们找到了一种无需实际更改算法即可提高性能的方法!我们可以将其概括为
p碰撞 xk = (n / 容量) k
现在我们可以忽略一些任意数量的碰撞,最终得到比我们所考虑的更多碰撞的可能性微乎其微。您可以通过选择正确的 k 将概率提高到任意微小的水平,而所有这些都不会改变算法的实际实现。
我们通过说哈希映射具有高概率的 O(1) 访问来讨论这个问题
您似乎将最坏情况的行为与平均情况(预期)运行时混为一谈。对于一般的哈希表,前者确实是 O(n)(即不使用完美的哈希),但这在实践中很少相关。
任何可靠的哈希表实现,再加上一半像样的哈希,在预期的情况下,具有非常小的因子(实际上是 2)的 O(1) 检索性能,在非常窄的方差范围内。
在 Java 中,HashMap 是如何工作的?
hashCode
用于定位对应的桶【桶内容器模型】。equals
用于比较。因此,有时它必须与几个项目进行比较,但一般来说,它更接近O(1)而不是O(n)。
出于实际目的,这就是您需要知道的全部内容。
请记住,o(1) 并不意味着每次查找只检查单个项目 - 它意味着检查的项目的平均数量保持不变 wrt 容器中的项目数量。因此,如果在包含 100 个项目的容器中查找一个项目平均需要 4 次比较,那么在包含 10000 个项目的容器中查找一个项目也应该平均需要 4 次比较,对于任何其他数量的项目(总是有有点差异,尤其是在哈希表重新散列的点周围,以及当项目数量非常少时)。
因此,只要每个桶的平均键数保持在固定范围内,冲突就不会阻止容器进行 o(1) 操作。
我知道这是一个老问题,但实际上有一个新答案。
你说得对O(1)
,严格来说,哈希映射并不是真的,因为随着元素的数量变得任意大,最终你将无法在恒定时间内搜索(并且 O 表示法是根据可以任意大)。
但它并不意味着实时复杂度是O(n)
——因为没有规定桶必须作为线性列表来实现。
事实上,Java 8 将桶实现为TreeMaps
一旦它们超过阈值,这使得实际时间O(log n)
.
O(1+n/k)
其中k
是桶的数量。
如果实现设置k = n/alpha
那么它是O(1+alpha) = O(1)
因为它alpha
是一个常数。
如果桶的数量(称为 b)保持不变(通常情况下),那么查找实际上是 O(n)。
随着 n 变大,每个桶中的元素数平均为 n/b。如果以一种通常的方式(例如链表)解决冲突,则查找是 O(n/b) = O(n)。
O 表示法是关于当 n 越来越大时会发生什么。当应用于某些算法时,它可能会产生误导,哈希表就是一个很好的例子。我们根据期望处理的元素数量来选择存储桶的数量。当 n 的大小与 b 大致相同时,查找大致是恒定时间的,但我们不能将其称为 O(1),因为 O 是根据 n → ∞ 的限制定义的。
我们已经确定哈希表查找的标准描述为 O(1) 是指平均情况下的预期时间,而不是严格的最坏情况下的性能。对于通过链接解决冲突的哈希表(如 Java 的哈希图),这在技术上是 O(1+α) 且具有良好的哈希函数,其中 α 是表的负载因子。只要您存储的对象数量不超过表大小的常数因子,它仍然是常数。
还解释说,严格来说,可以构造需要 O( n ) 查找任何确定性哈希函数的输入。但考虑最坏情况的预期时间也很有趣,它不同于平均搜索时间。使用链接是 O(1 + 最长链的长度),例如当 α=1 时Θ(log n / log log n )。
如果您对实现恒定时间预期的最坏情况查找的理论方法感兴趣,您可以阅读动态完美哈希,它递归地解决与另一个哈希表的冲突!
只有当您的散列函数非常好时,它才是 O(1)。Java 哈希表实现不能防止不良哈希函数。
添加项目时是否需要增加表格与问题无关,因为它与查找时间有关。
HashMap 中的元素存储为链表(节点)的数组,数组中的每个链表代表一个桶,用于一个或多个键的唯一哈希值。
在 HashMap 中添加条目时,键的哈希码用于确定存储桶在数组中的位置,例如:
location = (arraylength - 1) & keyhashcode
这里 & 表示按位与运算符。
例如:100 & "ABC".hashCode() = 64 (location of the bucket for the key "ABC")
在获取操作期间,它使用相同的方式来确定密钥的存储桶的位置。在最好的情况下,每个键都有唯一的哈希码,并为每个键生成一个唯一的桶,在这种情况下,get 方法只花费时间来确定桶的位置并检索常数 O(1) 的值。
在最坏的情况下,所有键都具有相同的哈希码并存储在同一个桶中,这导致遍历整个列表,导致 O(n)。
在 java 8 的情况下,如果大小增长到超过 8,Linked List 存储桶将被替换为 TreeMap,这将最坏情况的搜索效率降低到 O(log n)。
这基本上适用于大多数编程语言中的大多数哈希表实现,因为算法本身并没有真正改变。
如果表中不存在冲突,则只需进行一次查找,因此运行时间为 O(1)。如果存在冲突,则必须进行多次查找,这会将性能降低到 O(n)。
这取决于您选择避免冲突的算法。如果您的实现使用单独的链接,那么最坏的情况会发生,即每个数据元素都被散列到相同的值(例如散列函数的选择不当)。在这种情况下,数据查找与链表上的线性搜索没有什么不同,即 O(n)。但是,这种情况发生的概率可以忽略不计,并且查找最佳和平均情况保持不变,即 O(1)。
只有在理论情况下,当哈希码总是不同并且每个哈希码的桶也不同时,O(1)才会存在。否则,它的顺序是恒定的,即在 hashmap 的增量上,它的搜索顺序保持不变。
当然,hashmap 的性能将取决于给定对象的 hashCode() 函数的质量。但是,如果实现该函数以使冲突的可能性非常低,它将具有非常好的性能(在所有可能的情况下,这并不是严格意义上的 O(1),但在大多数情况下都是如此)。
例如,Oracle JRE 中的默认实现是使用随机数(存储在对象实例中以便它不会改变 - 但它也禁用偏向锁定,但这是另一个讨论)所以发生冲突的机会是非常低。
除了学者,从实际的角度来看,HashMap 应该被认为具有无关紧要的性能影响(除非您的分析器另有说明。)