Асимптотика добавления значения по ключу в hash-таблицу
Почему не O(n), ведь для добавления, сначала проверяются все ключи в hash-таблице, и если ключа нет, то он и добавляется
Ответы (1 шт):
Автор решения: Nick Zimakov
→ Ссылка
Не совсем так, проверять нам все ключи смысла нет, т.к в случае если мы кладем пару, у которой ключ уже лежит в хешмапе, то предыдущее значение просто перезапишется.
Вот выдержка из JavaDoc метода put класса HashMap:
Associates the specified value with the specified key in this map. If the map previously contained a mapping for the key, the old value is replaced.
Returns: the previous value associated with key, or null if there was no mapping for key. (A null return can also indicate that the map previously associated null with key.)