Сложность времени для HashMap положить / попасть внутрь?

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 в комментарии!