Какова временная сложность итерации хеш-карты в среднем случае? Я думаю, что его O(n)
O(n)
Какова временная сложность map.get(key); Я думаю, что O(1)
map.get(key);
O(1)
Из документации , которая должна быть вашим первым портом вызова:
Эта реализация обеспечивает постоянную производительность для основных операций (получение и сдача), предполагая, чтоХэш-функция правильно распределяет элементы по сегментам.Итерации по представлениям коллекции требуют времени, пропорционального «емкости» экземпляра HashMap (количество сегментов) плюс его размер (количество отображений ключ-значение).Таким образом, очень важно не устанавливать слишком высокую начальную емкость (или слишком низкий коэффициент загрузки), если важна производительность итерации.
O(1), которая в нормальном случае постоянна, , если они не сталкиваются
См. Также
Документ HashMap API
Структура данных HashTable
Из API:
Эта реализация обеспечивает постоянную производительность для основных операций (получение и сдача), предполагая, что хеш-функция правильно распределяет элементы между сегментами. Итерации по представлениям коллекции требуют времени, пропорционального «емкости» экземпляра HashMap (количество сегментов) плюс его размер (количество отображений ключ-значение). Таким образом, очень важно не устанавливать слишком высокую начальную емкость (или слишком низкий коэффициент загрузки), если важна производительность итерации.