HashMap put/get 里面的时间复杂度为？

Question

假设我有以下代码片段：

for(int i=0; i < n.length(); i++) {
    int aux = n[i];
    if(map.containsKey(aux)) {
        map.put(aux, map.get(aux)+1);
    } else {
        map.put(aux, 1);
    }
}

我的地图是一个HashMap。 我知道 for 将是 O(n) 然后映射操作具有 O(1)，但是我在那里有三个映射操作（containsKey、put 和 get）所以那将是 O(3n) 还是 O(n)？为什么？

Answer 1

O(3N) 和 O(N) 将被视为 O(N)。

---

我想，如果我没记错的话，getOrDefault() 可能是一个选项：

for (int i = 0; i < n.length(); i++) {
    int aux = n[i];

    map.put(aux, map.getOrDefault(aux, 0) + 1);
}

你的时间和内存复杂度都是 O(N)。

---

我认为另一个更具可读性的版本是：

for (int i = 0; i < n.length(); i++) {
    int aux = n[i];

    map.put(aux, -~map.getOrDefault(aux, 0));
}

-~x只是x + 1（-~x = x + 1）的按位运算。但是，您可以使用任何您觉得舒服的方式。

---

感谢ciamej的评论！