Итерация через HashMap (сложность)

Вы абсолютно правы. Итерация HashMap - это операция O(n + m), где n - это количество элементов, содержащихся в HashMap, а m - его емкость. Собственно, это четко указано в документы:

Iteration over collection views requires time proportional to the "capacity" of the HashMap instance (the number of buckets) plus its size (the number of key-value mappings).

Интуитивно (и концептуально) это происходит потому, что HashMap состоит из массива ведра, каждый элемент которого указывает либо ни на что (то есть на null), либо на список записей.

Итак, если массив сегментов имеет размер m, и если на карте всего есть записи n (я имею в виду, записи n разбросаны по всем спискам висит из некоторого сегмента), то итерация HashMap выполняется путем посещения каждого сегмента, а для сегментов со списком записей - посещение каждой записи в списке. Поскольку в целом есть корзины m и элементы n, итерация - это O(m + n).

Обратите внимание, что это не относится ко всем реализациям хеш-таблиц. Например, LinkedHashMap похож на HashMap, за исключением того, что он также имеет все свои записи, связанные в виде двусвязного списка (для сохранения порядка вставки или доступа). Если вы хотите повторить LinkedHashMap, нет необходимости посещать каждую корзину. Достаточно просто посетить самую первую запись, а затем перейти по ее ссылке к следующей записи, а затем перейти к следующей и т. д., И так до последней записи. Таким образом, итерация LinkedHashMap - это просто O(n), а n - это общее количество записей.

Итерация по представлениям коллекций требует времени, пропорционального «емкости» экземпляра HashMap (количеству сегментов) плюс его размеру (количеству сопоставлений "ключ-значение"). n = количество ведер m = количество сопоставлений "ключ-значение"

Сложность Hashmap составляет O (n + m), потому что в худшем случае один элемент массива содержит весь связанный список, что могло произойти из-за некорректной реализации функции хэш-кода, используемой в качестве ключа. Визуализируйте наихудший сценарий Чтобы повторить этот сценарий, сначала java необходимо выполнить итерацию по всему массиву O (n), а затем выполнить итерацию по связанному списку O (m), их объединение дает нам O (n + m).