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