Почему ArrayList растет со скоростью 1,5, но для Hashmap это 2?

В соответствии с реализацией Sun Java, во время расширения ArrayList растет до 3/2 начальной емкости, тогда как для HashMap коэффициент расширения удваивается. В чем причина этого?

В соответствии с реализацией, для HashMap, емкость всегда должна быть в силе двух. Это может быть причиной поведения HashMap. Но в этом случае возникает вопрос: для HashMap, почему способность всегда должна быть у власти двух?

Ответы

Ответ 1

Дорогая часть при увеличении емкости ArrayList копирует содержимое массива поддержки нового (большего).

Для HashMap он создает новый массив поддержки и помещает все записи в новый массив. И чем выше пропускная способность, тем меньше риск столкновения. Это дороже и объясняет, почему коэффициент расширения выше. Причина 1.5 против 2.0? Я считаю это "лучшей практикой" или "хорошим компромиссом".

Ответ 2

для HashMap, почему емкость всегда должна быть у власти двух?

Я могу думать о двух причинах.

  • Вы можете быстро определить ведро, к которому идет хэш-код. Вам нужно только побитовое И и не дорогое по модулю. int bucket = hashcode & (size-1);

  • Скажем, мы имеем коэффициент роста 1,7. Если мы начнем с размера 11, следующий размер будет 18, то 31. Нет проблем. Правильно? Но хэш-коды строк в Java вычисляются с простым коэффициентом 31. Ведро строки, в которое входит hashcode%31, определяется только последним символом String. Пока доведем O(1), если вы храните папки, все заканчивающиеся на /. Если вы используете размер, например, 3^n, , распределение не ухудшится, если вы увеличите n. Начиная с размера 3 до 9, каждый элемент в ковке 2 теперь переходит в ведро 2, 5 или 7, в зависимости от более высокой цифры. Это как разбить каждое ведро на три части. Таким образом, предпочтительным будет размер целочисленного коэффициента роста. (Конечно, все зависит от того, как вы вычисляете хэш-коды, но произвольный фактор роста не чувствует себя "стабильным".)

Ответ 3

Способ, которым HashMap разработан/реализован, его базовое количество ведер должно быть в 2 раза (даже если вы придаете ему разный размер, он имеет мощность 2), поэтому он увеличивается вдвое каждый раз, ArrayList может быть любого размера, и он может быть более консервативным в том, как он растет.

Ответ 4

Хеширование использует возможность равномерного распределения данных в ведрах. Алгоритм пытается предотвратить множественные записи в ведрах ( "хеш-коллизии" ), поскольку они снижают производительность.

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

Ответ 5

Я не могу дать вам причину, почему это так (вы должны спросить разработчиков Sun), но чтобы увидеть, как это происходит, посмотрите на источник:

  • HashMap: посмотрите, как изменяется размер HashMap до нового размера (source line 799)

         resize(2 * table.length);
    
  • ArrayList: источник, строка 183:

    int newCapacity = (oldCapacity * 3)/2 + 1;
    

Обновление: Я ошибочно связался с источниками Apache Harmony JDK - изменил его на Sun JDK.

Ответ 6

Общим правилом во избежание столкновений на Картах является сохранение коэффициента нагрузки max около 0,75 Чтобы уменьшить вероятность столкновений и избежать дорогостоящего процесса копирования, HashMap растет с большей скоростью.

Также, как говорит @Peter, он должен иметь мощность 2.