Java HashMap真的是O（1）吗？
我已经看到了一些关于Java的hashps和它们的O(1)查找时间的有趣声明。 有人能解释为什么这样吗？ 除非这些哈希algorithm与我所购买的任何哈希algorithm有很大的不同，否则肯定会存在一个包含冲突的数据集。
在这种情况下，查找将是O(n)而不是O(1) 。
有人可以解释他们是否是 O（1），如果是的话，他们是如何实现的？
HashMap的一个特殊之处在于，与平衡树不同，它的行为是概率的。 在这些情况下，就发生最坏情况事件的可能性而言，讨论复杂性通常是最有帮助的。 对于一个哈希映射来说，这当然是碰撞的情况下，地图碰巧有多满。 碰撞很容易估计。
碰撞 = n /容量
所以即使是less量元素的哈希映射也很可能会遇到至less一次碰撞。 大O符号可以让我们做更有说服力的事情。 观察任意的固定常数k。
O（n）= O（k * n）
我们可以使用这个特性来提高哈希映射的性能。 我们可以考虑最多2次碰撞的概率。
碰撞x 2 =（n /容量） 2
这是低得多。 由于处理一次额外碰撞的成本与大O性能无关，所以我们find了一种提高性能的方法，而不需要实际改变algorithm！ 我们可以generalzie这个
p 碰撞xk =（n /容量） k
现在，我们可以忽略一些任意数量的碰撞，最终碰撞的可能性比我们所说的要小得多。 通过select正确的k，可以将概率提高到任意小的水平，而不会改变algorithm的实际实现。
我们通过说散列图具有高概率的 O（1）访问来讨论这个问题
您似乎将平均情况（预期）运行时的最坏情况行为混淆在一起。 前者通常是散列表的O（n）（即不使用完美的散列），但这在实践中很less相关。
任何可靠的哈希表实现，加上一半体面哈希，在预期的情况下，具有非常小的因子（2，实际上）的检索性能O（1），在非常窄的变化范围内。
在Java中，HashMap通过使用hashCode来定位一个存储桶。 每个存储桶都是存储在该存储桶中的项目列表。 扫描项目，使用等于比较。 添加项目时，一旦达到一定的负载百分比，就会调整HashMap的大小。
所以有时需要比较几个项目，但通常比O（n）更接近O（1）。 出于实际的目的，这就是你应该需要知道的。
请记住，o（1）并不意味着每个查找只检查一个项目 – 这意味着检查的项目的平均数量与容器中的项目数量保持不变。 因此，如果平均需要4次比较才能在100个物品的容器中find物品，则还应该平均进行4次比较，以find10000个物品的容器中的物品，并且对于任何其他数量的物品特别是在散列表重新扫描的点，以及什么时候只有很less的项目）。
因此，只要每个桶的平均密钥数量保持在固定范围内，冲突就不会阻止容器进行o（1）操作。
我知道这是一个古老的问题，但实际上有一个新的答案。
你说得对，哈希映射并不是真正的O(1) ，严格地说，因为随着元素数量变得很大，最终你将无法在常量时间内进行search（并且O-notation是按照定义的数字可以得到任意大）。
但是并不是说实时复杂度是O(n) – 因为没有规则说桶必须作为线性列表来实现。
事实上，Java 8一旦超过阈值就会将存储桶实现为TreeMaps ，这使得实际时间O(log n) 。
如果桶的数量（称为b）保持不变（通常情况下），则查找实际上是O（n）。
当n变大时，每个桶中元素的数量平均为n / b。 如果冲突解决以一种常用的方式完成（例如链表），则查找是O（n / b）= O（n）。
O符号是关于当n越来越大时发生的事情。 应用于某些algorithm时可能会产生误导，哈希表就是一个例子。 我们根据我们期望处理的元素数量来select桶的数量。 当n与b的大小大致相同时，查找大致是恒定的，但是我们不能称之为O（1），因为O被定义为n→∞的极限。
O(1+n/k)其中k是桶的数量。
如果实现设置k = n/alpha那么它是O(1+alpha) = O(1)因为alpha是一个常数。
我们已经确定，散列表查找的标准描述是O（1），是指平均情况的预期时间，而不是严格的最坏情况的性能。 对于一个散列表来解决与链接的冲突（如Java的hashmap），这在技术上是一个好的散列函数的 O（1 +α），其中α是表的加载因子。 只要您存储的对象数量不超过表格大小的常数因子，就仍然保持不变。
也有人解释说，严格来说，构buildinput需要对任何确定性散列函数进行O（ n ）查找。 但是考虑最坏情况的预期时间也是有趣的，这与平均search时间不同。 使用链接这是O（1 +最长链的长度），例如当α= 1时Θ（log n / log log n ）。
如果您对理论上的方法感兴趣，以实现预期的最坏情况查找恒定时间，您可以阅读关于dynamic完美散列 ，它与另一个散列表recursion解决冲突！
只有你的散列函数非常好才是O（1）。 Java哈希表实现不能防止坏哈希函数。
无论您添加项目时是否需要增加表格，都与查询时间无关。
这基本上适用于大多数编程语言中的大多数哈希表实现，因为algorithm本身并不真正改变。
如果表中没有碰撞，则只需执行一次查找，因此运行时间为O（1）。 如果存在冲突，则必须进行多个查找，这会降低对O（n）的性能。
这取决于您select避免碰撞的algorithm。 如果您的实现使用单独的链接，那么在每个数据元素被哈希到相同的值（例如哈希函数的select不佳）的情况下会发生最糟糕的情况。 在这种情况下，数据查找与链接列表上的线性search（即O（n））没有区别。 然而，发生这种情况的可能性是微不足道的，查找最好，平均情况保持不变，即O（1）。
除了实际情况外，学者们认为HashMaps应该被认为具有不重要的性能影响（除非你的分析器另有告示）。
只有在理论情况下，当哈希码总是不同的，并且每个哈希码的桶也不同时，O（1）才会存在。 否则，它是恒定的顺序，即散列表的增量，其search顺序保持不变。
HashMap中的元素存储为链表（节点）的数组，数组中的每个链表都表示一个或多个键的唯一散列值的存储桶。
在HashMap中添加条目时，密钥的哈希码用于确定数组中的存储桶的位置，如下所示：
location = (arraylength - 1) & keyhashcode
这里＆代表按位AND运算符。
例如： 100 & "ABC".hashCode() = 64 (location of the bucket for the key "ABC")
在获取操作期间，它使用相同的方式确定密钥桶的位置。 在最好的情况下，每个哈希码是唯一的，并为每个密钥产生一个独特的桶，在这种情况下，get方法只花费时间来确定桶位置并检索常量O（1）的值。
在最坏的情况下，所有密钥都具有相同的哈希码并存储在同一个桶中，这导致遍历整个列表，导致O（n）。
在java 8的情况下，如果链接列表存储区的大小增加到8以上，那么链接列表存储区被replace为TreeMap，这将最坏情况的search效率降低到O（log n）。
当然，hashmap的性能将取决于给定对象的hashCode（）函数的质量。 但是，如果这个函数被实现，使得碰撞的可能性非常低，那么它将会有非常好的性能（这在每一个可能的情况下都不是严格的O（1），但是在大多数情况下）。
例如，Oracle JRE中的默认实现是使用一个随机数（存储在对象实例中以使其不会改变 – 但是也会禁用偏置locking，但是这是另一个讨论），所以碰撞的可能性是非常低。
