Java 散列表搜索真的是 O (1)吗？

在 Java 中，HashMap 是如何工作的？

• 使用 hashCode定位相应的桶[桶内容器模型]。
• 每个 bucket 是驻留在 bucket 中的项的列表(或从 Java8开始的树)。
• 使用 equals对项目进行逐个扫描以便进行比较。
• 当添加更多项时，一旦达到某个负载百分比，HashMap 就会调整大小。

因此，有时它将不得不比较一些项目，但一般来说，它更接近于 O (1)比 O (n)。
实际上，你只需要知道这些。

当然，散列表的性能将取决于给定对象的 hashCode ()函数的质量。然而，如果该函数的实现使得碰撞的可能性非常低，那么它将具有非常好的性能(在 每个可能的情况下这不是严格的 O (1) ，但在 大部分情况下是)。

例如，Oracle JRE 中的默认实现是使用一个随机数(存储在对象实例中，这样它就不会改变——但它也禁用了偏向锁定，但这是另一个讨论的话题) ，因此发生冲突的几率非常低。

这基本上适用于大多数编程语言中的大多数哈希表实现，因为算法本身并没有真正改变。

如果表中没有冲突，那么您只需要进行一次查找，因此运行时间为 O (1)。如果存在冲突，则必须执行多个查找，这将使性能降低到 O (n)。

请记住，o (1)并不意味着每次查找只检查一个项目——它意味着检查的平均项目数保持不变，即容器中的项目数。因此，如果平均需要4次比较才能找到一个包含100个条目的容器中的条目，那么也应该平均需要4次比较才能找到一个包含10000个条目的容器中的条目，以及任何其他数量的条目(总是会有一点差异，特别是在散列表重排的点周围，以及当有非常少数量的条目时)。

因此，只要每个 bucket 的平均键数保持在一个固定的范围内，冲突并不会阻止容器执行 o (1)操作。

您似乎将最坏情况下的行为与平均情况(预期)运行时混淆了。对于散列表来说，前者确实是 O (n)(即不使用完美散列) ，但这在实践中很少相关。

任何可靠的散列表实现，再加上一个不错的散列，在预期的情况下，在非常小的方差范围内，具有非常小的因子(实际上是2)的 O (1)的检索性能。

这取决于您选择的避免冲突的算法。如果您的实现使用单独的链接，那么最坏的情况发生在每个数据元素散列为相同值的情况下(例如，散列函数选择不当)。在这种情况下，数据查找与链表上的线性搜索(即 O (n))没有什么不同。然而，发生这种情况的可能性是可以忽略的，最佳查找和平均情况保持不变，即 O (1)。

HashMap 的一个特殊特性是，与平衡树不同，它的行为是随机的。在这些情况下，从最坏情况发生的可能性的角度来谈论复杂性通常是最有帮助的。对于散列映射来说，这当然是关于映射碰巧有多满的冲突的情况。碰撞是很容易估计的。

P_碰撞 = n/容量

因此，即使只有少量元素的散列映射也很有可能经历至少一次冲突。大 O 符号允许我们做一些更引人注目的事情。观察任意固定常数 k。

O (n) = O (k * n)

我们可以使用这个特性来提高散列映射的性能。我们可以考虑最多两次碰撞的概率。

P_{碰撞 X2} = (n/容量) ²

这个低多了。由于处理一个额外冲突的成本与 Big O 的性能无关，我们已经找到了一种在不改变算法的情况下提高性能的方法！我们可以把它推广到

P_{碰撞 x k} = (n/容量) ^K

现在我们可以忽略一些任意数量的碰撞，最终得到的碰撞的可能性微乎其微，超出了我们的计算范围。您可以通过选择正确的 k 将概率提高到任意微小的水平，而不需要改变算法的实际实现。

我们通过说散列映射具有 O (1)访问 非常有可能来讨论这个问题

我们已经确定，散列表查找的标准描述为 O (1)是指平均预期时间，而不是严格的最坏情况性能。对于解决链式冲突的散列表(如 Java 的散列映射) ，从技术上讲，这是 O (1 + α)和 一个很好的哈希函数，其中 α 是表的负载因子。只要存储的对象数量不超过比表大小大的常数因子，则仍然是常数。

还解释了严格来说，可以为任何确定性散列函数构造需要 O (N)查找的输入。但是考虑最坏情况下的 意料之中时间也很有趣，它不同于平均搜索时间。使用链表示 O (1 + 最长链的长度) ，例如当 α = 1时 Θ (log N/log N)。

如果您对实现常量时间预期最坏情况查找的理论方法感兴趣，那么您可以阅读有关 动态完全散列的内容，它用另一个散列表递归地解决冲突！

如果桶的数量(称为 b)保持不变(通常情况下) ，那么查找实际上是 O (n)。
当 n 变大时，每个 bucket 中的元素数平均为 n/b。如果冲突解决是通常的方式之一(例如链表) ，那么查找是 O (n/b) = O (n)。

O 符号是关于当 n 变得越来越大时会发生什么。当应用于某些算法时，它可能会产生误导，哈希表就是一个很好的例子。我们根据需要处理的元素数量来选择桶的数量。当 n 与 b 大小相同时，查找大致是常量时间，但我们不能称之为 O (1) ，因为 O 是根据 n →∞的极限定义的。

只有当散列函数非常好时，它才是 O (1)。Java 散列表实现不能防止错误的散列函数。

在添加项时是否需要增长表与问题无关，因为这与查找时间有关。

撇开学术不谈，从实际的角度来看，HashMaps 应该被认为对性能影响不大(除非您的分析器另有说法)

其中 k是桶的数量。

如果实现设置 k = n/alpha，那么它就是 O(1+alpha) = O(1)，因为 alpha是一个常量。

我知道这是一个老问题，但事实上有一个新的答案。

严格来说，散列映射并不是真正的 O(1)，这是正确的，因为随着元素的数量变得任意大，最终您将无法在常量时间内进行搜索(而 O 表示法是根据可以变得任意大的数来定义的)。

但这并不意味着实时复杂度就是 O(n)——因为没有规则说桶必须作为线性列表实现。

事实上，一旦桶超过一个阈值，Java8就将桶实现为 TreeMaps，这样实际的时间就是 O(log n)。

只有在理论上，当散列码总是不同的，而且每个散列码的 bucket 也不同时，O (1)才会存在。否则，它的顺序是恒定的，即在散列表的增量上，它的搜索顺序保持恒定。

HashMap 中的元素存储为一个链表(节点)数组，数组中的每个链表表示一个桶，用于存储一个或多个键的唯一散列值。
在 HashMap 中添加条目时，键的 hashcode 用于确定 bucket 在数组中的位置，类似于:

location = (arraylength - 1) & keyhashcode

这里的 & 表示按位 AND 运算符。

例如: 100 & "ABC".hashCode() = 64 (location of the bucket for the key "ABC")

在 get 操作期间，它使用相同的方法来确定密钥的 bucket 位置。在最好的情况下，每个键都有唯一的哈希代码，并且每个键都有一个唯一的 bucket，在这种情况下，get 方法只花时间确定 bucket 的位置并检索常量 O (1)的值。

在最坏的情况下，所有键都有相同的散列码并存储在相同的 bucket 中，这将导致遍历整个列表，从而导致 O (n)。

对于 java 8，如果大小增长到超过8，那么 Linked List bucket 将被 TreeMap 替换，这将最坏情况下的搜索效率降低到 O (log n)。