HashMap put() api time complex

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

ArrayListadd() апи с другой стороны ясно заявляет амортизированную O (N) т.е. добавить п элемент будет принимать п количество времени, почему бы не это относится к HashMap ставить тогда? хотя HashMap динамически создает большие ведра при достижении коэффициента нагрузки, а re применяет хэш к существующему, чтобы определить новое местоположение ковша.

всякая помощь по разъяснению выше будет высоко оценена, дайте мне знать, должны ли эти вопросы переместиться в какой-либо другой раздел, прежде чем его голосовать.

Спасибо.

источник

2017-01-03 Techfist

Возможный дубликат [HashMap vs. ArrayList, смещение производительности вставки] (http://stackoverflow.com/questions/30066806/hashmap-vs-arraylist-insertion-performance-confusion) – Borre

всякий раз, когда таблица становится слишком полной, выделяется новая таблица, которая больше по постоянному коэффициенту (например, в два раза больше), и все элементы перемещаются из старой таблицы в новую. Поэтому один конкретный вызов put() может иногда выполняться в Θ (n) времени, но (начиная с пустой таблицы) вся последовательность n вызовов put() всегда будет выполняться в ожидаемое время O (n), которое амортизируется ожидаемое время O (1) за операцию.

источник

2017-01-03 12:14:34

, так что это означает, что он не является постоянным O (1), и для более высоких нагрузок данных производительность HashMap put() будет затронута. – Techfist

Если вы ожидаете большой объем данных, вы можете явно установить емкость: HashMap h = new HashMap (3000), и в этом случае перестановки будут менее частыми или не произойдут. – cyanide

@Techfist, на самом деле это не так, как это работает. Если у вас есть операции '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' ', то они всегда будут принимать в общей В любой отдельной программе среднее время 'put' всегда будет O (1). –

ответ

Смежные вопросы