在 for 循环中插入和检索 HashMap 的时间复杂度是多少？

Question

我已经为一个应用程序编写了这段代码，但我很难确定它是否比遗留代码更好（遗留代码在每个值中使用一个带有 List 的哈希图）。据我了解，由于 Java 8 从 Hashmap 插入和检索是 O(log n)，而 for 循环在我的例子中是 O(n)。我假设这里的时间复杂度是 O(n log n) 是否正确？

//complexity => O(n)
  for (int i = 0; i < len; i++) {
        String s = someList.get(i);
        int someValue = someArray[i];
        if (someCondition < 0) {
            // complexity => O(log n)
            if (hashmap1.containsKey(s)) {
                //complexity => O(log n) + O(log n) = O(log n)
                hashmap1.put(s, hashmap1.get(s) + someValue);
                //complexity => O(log n) + O(log n) = O(log n)
                hashmap2.put(s, hashmap2.get(s) + 1);
            } else {
                //complexity => O(log n)
                hashmap1.put(s, someValue);
                //complexity => O(log n)
                hashmap2.put(s, 1);
            }
        }
    }

Answer 1

遍历元素的for循环是O(n)，HashMap的遍历是O(1)，最终答案是O(n)，详见here。

在 for 循环中插入和检索 HashMap 的时间复杂度是多少？

What is the time complexity of HashMap insertion and retrieval inside of a for loop?

java

big-o

hashmap

time-complexity