HashMap 获取/放入复杂性

我们习惯于说 HashMap get/put运算是 O (1)。但是它取决于散列实现。默认对象散列实际上是 JVM 堆中的内部地址。我们是否确定它足够好，声称 get/put是 O (1) ？

可用内存是另一个问题。正如我从 javadocs 中了解到的那样，HashMap的加载因子应该是0.75。如果我们在 JVM 中没有足够的内存，并且负载因子超出了限制，那么该怎么办？

所以，看起来 O (1)是不能保证的。这是有意义的还是我遗漏了什么？

221214 次浏览
小开
最佳答案

这取决于很多事情。它是 通常 O (1) ，有一个像样的散列，它本身是一个常量... 但是你可以有一个散列，需要很长的时间来计算，还有如果有多个项目在散列映射返回相同的散列代码，get将不得不在他们中的每一个上调用 equals迭代，以找到匹配。

在最坏的情况下，由于遍历同一散列桶中的所有条目(例如，如果它们都具有相同的散列代码) ，HashMap具有 O (n)查找。幸运的是，根据我的经验，这种最坏的情况在现实生活中并不常见。所以不，O (1)当然不能保证-但它通常是您在考虑使用哪种算法和数据结构时应该假设的。

在 JDK 8中，对 HashMap进行了调整，以便如果可以比较键以进行排序，那么任何密集填充的 bucket 都将作为树实现，因此即使有大量条目使用相同的哈希代码，复杂度也是 O (log n)。当然，如果键类型的相等性和顺序不同，这可能会导致问题。

是的，如果您没有足够的内存来使用散列映射，那么您将会遇到麻烦... ... 但是无论您使用什么数据结构，情况都是如此。

小开

我不确定默认的 hashcode 是否是地址-我前段时间读过 OpenJDK 的 hashcode 生成源代码，我记得它有点复杂。也许，这仍然不能保证一个良好的发行。然而，这在某种程度上是没有意义的，因为在散列表中用作键的类很少使用默认的散列码——它们提供自己的实现，这应该是好的。

最重要的是，你可能不知道(再次声明，这是基于阅读源代码——这并不能保证) HashMap 在使用它之前搅拌散列，将整个单词的熵混合到底部位，这是除了最大的散列映射之外所有人都需要的地方。这有助于处理散列，特别是不这样做本身，虽然我不能想到任何常见的情况下，你会看到这一点。

最后，当表被重载时，它会退化成一组并行链表——性能变成 O (n)。具体来说，通过的链接数量平均将是负载因子的一半。

小开

前面已经提到过，如果 n是条目的数量，而 m是大小，那么散列表的平均值就是 O(n/m)。还有人提到，原则上，整个事情可以崩溃成一个单链表与 O(n)查询时间。(这一切都假设计算散列是常量时间)。

然而，不常提到的是，至少在 1-1/n的概率下(所以对于1000件物品，有99.9% 的概率) ，最大的桶不会比 O(logn)多！因此匹配二叉搜索树的平均复杂度。(常数是好的，更紧的界是 (log n)*(m/n) + O(1))。

这个理论界限所需要的就是使用一个相当好的 hash 函数(参见 Wikipedia: 全域哈希)。它可以像 a*x>>m一样简单)。当然，给出哈希值的人并不知道您是如何选择随机常量的。

DR: 在非常高的概率下，散列映射最坏的获取/放入复杂度是 O(logn)。

小开

HashMap 操作是 hashCode 实现的依赖因素。对于理想的场景，假设好的哈希实现为每个对象提供唯一的哈希代码(没有哈希冲突) ，那么最好的、最坏的和平均的场景将是 O (1)。 让我们考虑这样一个场景，即 hashCode 的错误实现总是返回1或类似的具有 hash 冲突的 hash。在这种情况下，时间复杂度为 O (n)。

现在进入关于内存的问题的第二部分，那么是的，内存约束将由 JVM 来处理。

小开

实际上，它是 O (1) ，但这实际上是一个可怕的、在数学上毫无意义的简化。O ()符号表示当问题的大小趋于无穷大时算法的行为。Hashmap get/put 的工作原理类似于 O (1)算法，只适用于有限的大小。从计算机内存和寻址的角度来看，这个限制相当大，但远不是无穷大。

当我们说散列表 get/put 是 O (1)的时候，我们应该说，get/put 所需要的时间或多或少是常量，而不是取决于散列表中元素的数量，只要散列表能够在实际的计算系统中显示出来。如果问题超出了这个范围，我们需要更大的散列映射，那么过一段时间后，当我们用尽了可描述的不同元素时，描述一个元素的位数肯定也会增加。例如，如果我们使用一个散列映射来存储32位数，然后我们增加问题的大小，以便在散列映射中有超过2 ^ 32位的元素，那么单个元素将被描述为超过32位。

描述单个元素所需的位数是 log (N) ，其中 N 是元素的最大数目，因此 get 和 put 实际上是 O (log N)。

如果你把它和一个树集合比较，它是 O (log n) ，那么散列集合是 O (long (max (n)) ，我们只是觉得这是 O (1) ，因为在某个特定的实现上 max (n)是固定的，不会改变(我们存储的对象的大小是以比特计量的) ，计算散列码的算法是快速的。

最后，如果在任何数据结构中找到一个元素是 O (1) ，我们将凭空创建信息。有了 n 个元素的数据结构，我就可以用 n 种不同的方式选择一个元素。这样，我就可以对日志(n)位信息进行编码。如果我可以把它编码为零位(这就是 O (1)的意思) ，那么我就创建了一个无限压缩的 ZIP 算法。

小开

我同意:

  • O (1)的一般分摊复杂度
  • 糟糕的 hashCode()实现可能导致多次冲突，这意味着在最糟糕的情况下，每个对象都会进入同一个 bucket，因此，如果每个 bucket 都由 List支持，则 O (N)。
  • 自 Java 8以来，HashMap动态地用 TreeNodes (当列表大于8个元素时为红黑树)替换每个桶中使用的 Nodes (链表) ，导致 O (LogN)的性能最差。

但是，如果我们想要100% 精确，这是 没有的全部真相。hashCode()的实现和键 Object的类型(不可变/缓存或作为 Collection)也可能严格地影响实时复杂性。

让我们假设以下三种情况:

  1. HashMap<Integer, V>
  2. HashMap<String, V>
  3. HashMap<List<E>, V>

它们具有相同的复杂性吗？那么，第一个的摊销复杂度，正如预期的那样，O (1)。但是，对于其余部分，我们还需要计算查找元素的 hashCode()，这意味着我们可能必须遍历算法中的数组和列表。

让我们假设上面所有数组/列表的大小都是 K。 然后，HashMap<String, V>和 HashMap<List<E>, V>将有 O (k)分摊复杂性，类似地，在 Java8中最坏的情况是 O (K + logN)。

* 注意，使用 String键是一个更复杂的情况，因为它是不可变的，而且 Java 将 hashCode()的结果缓存在一个私有变量 hash中，所以它只计算一次。

/** Cache the hash code for the string */
private int hash; // Default to 0

但是，上述情况也有它自己的最坏情况，因为 Java 的 String.hashCode()实现在计算 hashCode之前正在检查 hash == 0。但是，有一些输出 hashcode为零的非空字符串，如“ f5a5a608”，请参阅 给你，在这种情况下，制表可能没有帮助。

小开

简单地说，如果每个桶只包含一个节点，那么时间复杂度将是 O (1)。如果 bucket 包含多个节点，那么它们的时间复杂度将是 O (linkedList 大小)。它总是比 O (n)有效。

因此我们可以说，对于 put (K，V)函数的平均情况下的时间复杂度:

节点(n)/桶(N) = λ (lambda)

例子: 16/16 = 1

时间复杂度为 O (1)


提交答案