ArrayList

@hsad · Регистрация: 24.05.2015

Студворк — интернет-сервис помощи студентам

Произвожу знакомство с коллекциями и читаю про ArrayList, а конкретно про увеличение размера при его заполнении. Нашел довольно старую статью (2011 года), где есть формула для расчета нового размера массива: (oldCapacity * 3) / 2 + 1. Т.е. увеличивается в 1,5 раза.

У меня в IDEA стоит JDK 11, и я решил залезть в доки на ArrayList. А там уже такой метод:

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
private int newCapacity(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity <= 0) {
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
                return Math.max(DEFAULT_CAPACITY, minCapacity);
            if (minCapacity < 0) // overflow
                throw new OutOfMemoryError();
            return minCapacity;
        }
        return (newCapacity - MAX_ARRAY_SIZE <= 0)
            ? newCapacity
            : hugeCapacity(minCapacity);
    }

Получается, он уже увеличивается в два раза? И как здесь работает операция сдвига? (Ох как я не люблю двоичные разряды и возню с ними).

@xoraxax · 05.12.2019, 21:15

>>1 - деление на 2, <<1 умножение на два
Вообще непонятно в чем вопрос, есть код, есть иде, вставь и посмотри, как работает

@Mirohaaa · 06.12.2019, 13:44

xoraxax, Полагаю, что ТС новичок в программировании, в принципе как и я (учу язык третий месяц).
Сам залез в документацию (использовал JDK 12) и немного почитал. Для себя выявил следующее:

Добавление элементов в списочный массив осуществляется с помощью перегруженных вариантов метода add().

1) public boolean add(E элемент).
Внутри данного метода происходит вызов перегруженного варианта метода add(), помеченный как private, который в свою очередь на вход принимает три параметра: добавляемый элемент, внутренний массив и его размер (size). В закрытом методе происходит проверка: если переданный параметр размера равен длине внутреннего массива, то массиву присваивается результат выполнения метода grow(). В методе grow() возвращается результат работы его перегруженного варианта grow(int minCapacity): return grow(mincapacity: size + 1), в котором внутреннему массиву присваивается ссылка на новый массив, полученный в результате копирования: Arrays.copyOf(elementData, newCapacity(minCapacity)).

Размер нового массива непосредственно вычисляется в закрытом методе newCapacity по формуле:
int newCapacity = oldCapacity + (oldCapacity >> 1)
Для массива с размером по умолчанию будет справедливо:
>> 1 – побитовый сдвиг вправо на единицу (оператор, который уменьшает число до его половины). По сути, означает деление на 2 в степени 1. Получается, что мы делим 10 на 2 и прибавляем 10. Итого, новая емкость массива равна 15, но так как мы добавляем 11 элемент, то 15+1 = 16.

Поправьте, если не прав.

Новые блоги и статьи Все статьи Все блоги /
Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. На мобильном - сканируйте QR-код. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .	Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .
Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .	SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .	SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .

@xoraxax 3639 / 2971 / 918 Регистрация: 05.07.2013 Сообщений: 14,220
	05.12.2019, 21:15
	>>1 - деление на 2, <<1 умножение на два Вообще непонятно в чем вопрос, есть код, есть иде, вставь и посмотри, как работает 1

@Mirohaaa 1 / 1 / 0 Регистрация: 15.10.2019 Сообщений: 13
	06.12.2019, 13:44
	xoraxax, Полагаю, что ТС новичок в программировании, в принципе как и я (учу язык третий месяц). Сам залез в документацию (использовал JDK 12) и немного почитал. Для себя выявил следующее: Добавление элементов в списочный массив осуществляется с помощью перегруженных вариантов метода add(). 1) public boolean add(E элемент). Внутри данного метода происходит вызов перегруженного варианта метода add(), помеченный как private, который в свою очередь на вход принимает три параметра: добавляемый элемент, внутренний массив и его размер (size). В закрытом методе происходит проверка: если переданный параметр размера равен длине внутреннего массива, то массиву присваивается результат выполнения метода grow(). В методе grow() возвращается результат работы его перегруженного варианта grow(int minCapacity): return grow(mincapacity: size + 1), в котором внутреннему массиву присваивается ссылка на новый массив, полученный в результате копирования: Arrays.copyOf(elementData, newCapacity(minCapacity)). Размер нового массива непосредственно вычисляется в закрытом методе newCapacity по формуле: int newCapacity = oldCapacity + (oldCapacity >> 1) Для массива с размером по умолчанию будет справедливо: >> 1 – побитовый сдвиг вправо на единицу (оператор, который уменьшает число до его половины). По сути, означает деление на 2 в степени 1. Получается, что мы делим 10 на 2 и прибавляем 10. Итого, новая емкость массива равна 15, но так как мы добавляем 11 элемент, то 15+1 = 16. Поправьте, если не прав. 0