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)，请参阅 这里。