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

Question

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

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

Answer 1

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

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

Answer 2

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

Я могу вспомнить две причины.

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

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

Answer 3

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

Answer 4

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

Также, как говорит @Peter, это должно быть степень 2.

Answer 5

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

1. HashMap: посмотрите, как HashMap изменяет размеры до нового размера ( источник строка 799)

        resize(2 * table.length);
   

2. ArrayList: источник , строка 183:

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

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

Answer 6

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

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