JavaRush/Помощь по Java задачам/Объясните пожалуйста динамическое увеличение размера Arra...

15 уровень

02.06.2020
2105просмотров
6комментариев

Объясните пожалуйста динамическое увеличение размера ArrayList?

Решен

читал на просторах интернета об основных характеристиках ArrayList. И встретил такой текст: " При записи в позицию capacity +1 происходит динамическое увеличение размера, а именно создается новый массив кол-во элементов в котором равно (capacity * 3) / 2 + 1 (capacity - вместимость) и в него перемещаются все элементы из старого + плюс добавляется новый элемент. В связи с этим свойством вставка в конец происходит в среднем за постоянное время. В среднем т.к периодически происходят операции расширения, которые занимают больше времени, чем вставка в пустую ячейку." Я не понял описание этой характеристики "Динамическое увеличивает размер по формуле (capacity * 3) / 2 + 1" подскажите пожалуйста как можно подробнее узнать об этой характеристике, что бы понять эту характеристику списка, и в каких практических случаях учитывать ее?

Комментарии (6)

популярные
новые
старые

Для того, чтобы оставить комментарий Вы должны авторизоваться

Ksenia Volkova Java Developer в DXC

Master

2 июня 2020, 08:09

полезный

Практически это можно учитывать вот как. У ArrayList начальная вместимость по умолчанию - 10 (в классе ArrayList есть константа DEFAULT_CAPACITY, равная 10). То есть если ты создаешь список без указания capacity в конструкторе, то массив в нем будет создан именно на 10 ячеек. Затем, если ты будешь добавлять элементы и их станет 10, то будет создан новый массив на 10 * 1.5 +1 = 16 ячеек, и данные из старого массива будут скопированы в новый. Потом при увеличении списка снова будет создаваться массив (на 25, 38, 58...), и данные в него будут копироваться из старого. Так вот, если ты заранее знаешь, что тебе надо будет добавить в список много элементов, то может иметь смысл сразу указать нужное значение capacity при создании списка. Тогда не нужно будет многократно создавать новые массивы и копировать в них даные. (При этом все равно имеет смысл ориентироваться именно на минимально необходимое значение, чтобы не резервировать лишнюю память. ArrayList все равно потом увеличит размер, если в этом будет необходимость).

Justinian Judge в Mega City One

Master

2 июня 2020, 07:21

полезный

грубо говоря, представь ArrayList вот так:

class ArrayList {
    private int capacity = 10;
    private Integer[] array = new Integer[capacity];
    private int currentIndex = 0;
    private int size = 0;

    public void add(Integer element) {
        if (currentIndex >= array.length) {
            makeArrayGreatAgain();
        }
        array[currentIndex++] = element;
        size++;
    }

    public int size() {
        return size();
    }

    private void makeArrayGreatAgain() {
        int newCapacity = capacity * 3 / 2 + 1;
        Integer[] newExpandedArray = new Integer[newCapacity];

        System.arraycopy(array, 0, newExpandedArray, 0, capacity);
        array = newExpandedArray;
        capacity = newCapacity;
    }

    @Override
    public String toString() {
        String elements = "";
        for (int i = 0; i < size; i++) {
            elements = elements + array[i] + ", ";
        }
        return "ArrayList{" +
                elements.substring(0, elements.length() - 2) +
                '}';
    }
}

Сама суть понятна? Есть у нас класс, под капотом у него массив. Массив как мы знаем, не может расширяться или сужаться, если он уже создан с определенным размером, то таким и умрет. Это неудобно. Поэтому придумали такую конструкцию - авторасширение. То есть создается с определенным запасом массив. И мы туда бросаем элементы. Когда место заканчивается (по разному бывает, может стоять и 75% загрузка), создается НОВЫЙ массив, с размерностью:

старыйРазмер * 1.5 + 1;

(в твоей формуле 1.5 это 3 / 2) в него перекопируется старый массив и теперь у нас увеличенный в полтора раза массив. Таким образом мы можем писать просто: list.add(2); и не переживать, а заполнен там массив или нет. Под капотом ArrayList, когда нужно будет автоматически происходит увеличение массива.

Justinian Judge в Mega City One

Master

2 июня 2020, 07:41

полезный

Тебе на данный момент нужно знать две вещи: 1. Как внутри устроен ArrayList, что это структура данных, которая имеет в своей основе обычный массив. 2. Что при достижении определенных крайних значений заполненности, будет происходить автоматическое расширение массива, чтобы можно было добавлять следующие элементы.

ArrayList list = new ArrayList();
list.add(5);
list.add(1);
list.add(3);
list.add(9);
System.out.println(list);

И вывод на экран:

ArrayList{5, 1, 3, 9}

можешь поверить на слово, а можешь (так лучше) скопировать код себе, и попробуй позапускать, добавить 1 элемент, или 20, можешь отдебажить или сделать геттер для массива внутреннего и проверить его размер. Хорошая статья на тему: Структуры данных в картинках. ArrayList

Sergei Kirianov

Уровень 27

12 октября 2022, 18:37

Не мог бы ты объяснить что происходит в toString, который переписан.

Justinian Judge в Mega City One

Master

27 октября 2022, 15:11

Привет, каждый объект в джаве это набор аттрибутов, их значений, единичек и ноликов. Но часто есть потребность, визуально работать с объектом, поэтому в классе Object есть метод toString() , этот метод есть во всех классах в джаве (поскольку классы наследуются от Object и имеют его методы) Метод toString возвращает представление объекта в текстовом виде. Программисты сами определяют как это выглядит, переопределяя этот метод ПРИ НЕОБХОДИМОСТИ. Посмотри материалы ниже: - https://comaqa.gitbook.io/java-automation/oop-v-java/metod-tostring - https://www.internet-technologies.ru/articles/ispolzovanie-metoda-tostring-v-java.html - https://www.youtube.com/watch?v=KEQ043yT3F4 После того почитаешь, вернемся к примеру выше:

@Override
public String toString() {

здесь мы переопределяем метод туСтринг, сигнатура метода должна быть именно такой, тогда.

String elements = "";

инициализируем пустую строку, к которой будем добавлять

Justinian Judge в Mega City One

Master

27 октября 2022, 15:11

for (int i = 0; i < size; i++) {
    elements = elements + array[i] + ", ";
}

итерируемся по массиву и делаем конкатенацию строк результирующая строка = результирующая строка + текущий элемент массива + , например для массива {1, 2, 3} У нас на первой итерации elements = "" - пустая строка elements = "" + 1 + "," то есть мы добавили в вывод первый элемент и запятую

1,

после первой итерации

1,2,

после второй (elements = "1," + 2 + ",") и

1,2,3,

после третьей итерации. То есть мы просто складываем в строку все элементы массива через запятую. А потом идет еще одна склейка: return "ArrayList{" + elements.substring(0, elements.length() - 2) + '}' elements у нас равно 1,2,3, elements.substring(0, elements.length() - 2) - сабстринг минус два -2, мы делаем чтобы убрать последнюю запятую. Почему именно -2 а не -1, поскольку мы указываем индекс последнего элемента по сути, а это длина - 1, поскольку индексы с нуля. Поскольку нам нужно еще убрать один символ, то мы добавляем -1, и получается -2, если здесь есть вопросы погугли java susbtring в итоге у нас получится

1,2,3

и у нас идет последняя склейка:

"ArrayList{" + "1,2,3" + "}"

Эта логика может быть любой, какой программист ее задаст, такой и будет, главное чтобы был объект типа Строка. Можно прописать вот так: "ArrayList{one, two, three"}" можно так: "ArrayList!!one pig+two pig+three pig!!" это как пропишешь. Обычно это из условий задачи явно следует как нужно прописывать, если не указано прямо, значит на твое усмотрение