big o通过Java 8中的实代码详细说明Hashmap put（）方法的big

Question

我是算法新手。我读到并意识到Hashmap中put（K键，V值）的big-O是O（1）。 当我进入HashMap类的核心时

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        //...
    if ((p = tab[i = (n - 1) & hash]) == null)
        //...
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            // ...
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // ...
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
           // ...
        }
    }
    ...
    return null;
}

如您所见，当向hashmap添加新的项时，它将用上面的“For Loop”迭代max n（hashmap中的所有项）：

 for (int binCount = 0; ; ++binCount) {

现在，For循环的大O是O（n）——>；为什么HashMap中put（K键，V值）的big-O可以是O（1）？ 我哪里理解错了

非常感谢

Answer 1

Big-O表示法与函数的性能有关，与所操作的元素数有关。仅仅拥有一个for循环并不会突然使Hashmap查找的性能在Hashmap内的每个元素上都有固定的增长

大O符号中有一些模式。整个元素集合中的循环是O(n)，但循环通常并不意味着查找是O(n)。为了举例说明，我将使用下面的（愚蠢的）例子

具有O(1)性能的函数

  public void add_o_one(int x, int y) {
     return x + y;
  }

具有O(1)性能的函数，添加了循环

  public void add_still_o_one(int x, int y) {
     int[2] numbers;
     numbers[0] = x; 
     numbers[1] = y;
     int result = 0;
     for (int index = 0; index < numbers.length; index++) {
        result += numbers[index];
     }
     return result;
  }

虽然我预计后一种方法的效率会稍低一些，但无法通过选择不同（或更多）的数字来改变其运行时速度。因此，它仍然是O(1)

在Hashmap中，循环存储桶列表确实会改变相对于输入的速度；但是，对于每个元素，它并不会以恒定的量改变它。此外，大多数hashmap实现都会随着映射的填充而增大其存储桶大小。这意味着你看到的不是常见的情况，而且很可能很少被调用（除非你实现了一个非常糟糕的哈希代码）

虽然您可能会认为“大于^ {CD5>}的东西”很难使代码功能以与{{CD5>}不一致的方式出现，除非您明确地破坏算法（通过提供所有散列到相同值的对象，例如）。p>

Answer 2

HashMap实际上是一个桶的集合（由数组支持），这些桶由一棵红黑树支持（从Java8开始）。如果你有一个非常糟糕的散列函数，将所有元素放在同一个容器中，那么性能会下降到O(log(n))

从Baeldung

HashMap has O(1) complexity, or constant-time complexity, of putting and getting the elements. Of course, lots of collisions could degrade the performance to O(log(n)) time complexity in the worst case, when all elements land in a single bucket. This is usually solved by providing a good hash function with a uniform distribution.

从docs

This implementation provides constant-time performance for the basic operations (get and put), assuming the hash function disperses the elements properly among the buckets.

Answer 3

其思想是，哈希表中的单个bin具有预期的常量元素数。因此，您提到的循环将在O（1）个预期时间内运行（假设您的键的hashCode()并不糟糕）

具体来说，对于HashMap实现，有一个默认值为0.75的负载因子。这意味着HashMap的每个bin平均应该有<；=0.75个元素（一旦HashMap中有超过负载系数*的存储单元条目，存储单元的数量就会加倍，以保持不变）。因此，所提到的循环平均应该有一次迭代