Java Internals: Jak działa ArrayList języku Java?

Czas czytania: 3 minut

Programując w języku Java, z pewnością wielokrotnie korzystałeś z różnego rodzaju list (ArrayList, LinkedList itd). Ale czy zastanawiałeś się kiedyś, jak wygląda ich wewnętrzna implementacja? Analizowałeś, jak wpływa ona na przykład na wydajność twojego programu oraz zajmowaną przezeń pamięć? W tym artykule zajmiemy się analizą wewnętrznej implementacji ArrayList, bazując na implementacji openjdk-11 [4].

Czym jest ArrayList?

ArrayList jest tablicą, której rozmiar można dynamicznie zmieniać. W przeciwieństwie do zwykłych tablic, które mają stały rozmiar, ArrayList rośnie dynamicznie w miarę jak dodajemy do niej nowe elementy.

Na początku przyjrzyjmy się definicji ArrayList.

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

ArrayList rozszerza klasę AbstractList<E>. Klasa ta jest „szkieletem” dla implementacji interfejsu List<E>. AbstractList<E> dostarcza implementacji „uniwersalnych” metod, jak „lastIndexOf”, „addAll” itd. których mechanizm działania nie zależy od konkretnej implementacji listy.

Interfejs znacznikowy RandomAccess [1] używany jest do oznaczenia klas, w których dostęp do poszczególnych elementów listy jest bardzo szybki. ArrayList spełnia ten warunek. Dostęp do dowolnego elementu listy uzyskamy w czasie O(1). (Nie ma znaczenia, czy jest to element pierwszy, drugi, setny czy milionowy).

Interfejs znacznikowy Cloneable zapewnia, że obiekt klasy można sklonować. Będzie to tzw. „deep copy” (głęboka kopia). Oznacza to, że po wywołaniu metody clone skopiowane do nowego obiektu zostaną nie referencje, a zawartość wszystkich elementów istniejących w obiekcie.

Interfejs znacznikowy Serializable mówi, że klasa jest serializowalna.

Prywatne statyczne elementy klasy ArrayList

Przyjrzyjmy się następującemu fragmentowi implementacji klasy ArrayList.

111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
  private static final int DEFAULT_CAPACITY = 10;

    /**
     * Shared empty array instance used for empty instances.
     */

    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
     * Shared empty array instance used for default sized empty instances. We
     * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
     * first element is added.
     */

    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * The array buffer into which the elements of the ArrayList are stored.
     * The capacity of the ArrayList is the length of this array buffer. Any
     * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
     * will be expanded to DEFAULT_CAPACITY when the first element is added.
     */

    transient Object[] elementData; // non-private to simplify nested class access

    /**
     * The size of the ArrayList (the number of elements it contains).
     *
     * @serial
     */

    private int size;

Już na podstawie tego fragmentu i deklaracji kilku prywatnych elementów klasy ArrayList możemy domyślić się, w jakiej strukturze elementy wewnątrz niej są przechowywane. Jest to oczywiście zwykła tablica obiektów Object[]. Jej deklarację widzimy w linijce 131 na powyższym listingu. Zastosowanie wyjaśnia zresztą komentarz umieszczony w kodzie źródłowym.

Domyślny rozmiar pustej ArrayListy sugeruje zmienna DEFAULT_CAPACITY znajdująca się w linijce 111. Wynosi ona 10 elementów. Ale czy faktycznie dla pustej ArrayListy wewnętrzna tablica obiektów ma rozmiar 10? Wątpliwości rozbudzają zmienne EMPTY_ELEMENTDATA i DEFAULTCAPACITY_EMPTY_ELEMENTDATA. Wielkość tych tablic wynosi 0. Aby rozwiać nasze wątpliwości, zerknijmy na kod źródłowy konstruktorów ArrayListy.

Konstruktory klasy ArrayList

145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
    /**
     * Constructs an empty list with the specified initial capacity.
     *
     * @param  initialCapacity  the initial capacity of the list
     * @throws IllegalArgumentException if the specified initial capacity
     *         is negative
     */

    public ArrayList(int initialCapacity) {
        if (initialCapacity>0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

Pierwszy z trzech konstruktorów pozwala na stworzenie ArrayListy o określonej początkowej pojemności. Taki konstruktor tworzy tablicę elementData o wielkości przekazanej w konstruktorze (jeśli ta wielkość jest większa od zera). Jeśli initialCapacity wynosi 0, rozmiar tablicy domyślnie wynosi 0. Przy dodawaniu kolejnych elementów będzie on zwiększany. A jak? Omówimy to sobie za chwilę.

163
164
165
166
167
168
  /**
     * Constructs an empty list with an initial capacity of ten.
     */

    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

W konstruktorze bezparametrowym nie ma wielkiej filozofii. Domyślny rozmiar wynosi 0, a ArrayLista jest pusta.

Zagadka: Czy polecenia new ArrayList<>(0) i new ArrayList<>() po dodaniu pierwszego elementu utworzą wewnętrznie tablicę o tym samym rozmiarze? Zastanów się nad tym zanim przejdziesz do dalszej części tekstu. Zwróć uwagę na to, że twórcy implementacji rozróżnili te dwie sytuacje za pomocą inicjacji ArrayListy dwoma różnymi obiektami: albo za pomocą DEFAULTCAPACITY_EMPTY_ELEMENTDATA albo EMPTY_ELEMENTDATA.

170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
    /**
     * Constructs a list containing the elements of the specified
     * collection, in the order they are returned by the collection's
     * iterator.
     *
     * @param c the collection whose elements are to be placed into this list
     * @throws NullPointerException if the specified collection is null
     */

    public ArrayList(Collection<? extends E> c) {
        Object[] a = c.toArray();
        if ((size = a.length) != 0) {
            if (c.getClass() == ArrayList.class) {
                elementData = a;
            } else {
                elementData = Arrays.copyOf(a, size, Object[].class);
            }
        } else {
            // replace with empty array.
            elementData = EMPTY_ELEMENTDATA;
        }
    }

Przyjrzyjmy się ostatniemu konstruktorowi. Tworzy on kopię ArrayListy na podstawie kolekcji zawartej w argumencie konstruktora.

Na początku kolekcja konwertowana jest do tablicy obiektów. Uzyskana tablica jest przypisywana do wewnętrznej ArrayListowej tablicy elementData. Jeśli źródłowa kolekcja jest pusta, konstruktor zachowa się tak samo jak wywołanie new ArrayList<>(0);

Dodawanie i usuwanie elementów ArrayList

Skoro wiemy, w jaki sposób obiekt ArrayList jest konstruowany, pora zastanowić się jak działa operacja dodawania i usuwania elementów. Zanim przejdziemy do analizy kodu zastanówmy się jak by to mogło działać – na logikę. Musimy posiadać wskaźnik, który mówi nam jaki jest aktualny rozmiar tablicy. Jeśli ten wskaźnik jest mniejszy od rozmiaru tablicy – sytuacja jest prosta. Zapisujemy wtedy dodawany element w kolejnej komórce tablicy. Jeśli tak nie jest – trzeba w jakiś sposób zwiększyć rozmiar tablicy. Jak to zrobili twórcy implementacji openjdk? Zobaczmy.

503
504
505
506
507
508
509
510
511
512
513
     /**
     * Appends the specified element to the end of this list.
     *
     * @param e element to be appended to this list
     * @return {@code true} (as specified by {@link Collection#add})
     */

    public boolean add(E e) {
        modCount++;
        add(e, elementData, size);
        return true;
    }

Publiczna metoda add nie jest długa. Zawiera tylko trzy linijki :). modCount jest polem zadeklarowanym w klasie AbstractList. Przekazuje ono informację o tym, ile razy lista była modyfikowana. Następna linijka to wywołanie prywatnej metody add. Przyjrzyjmy się jej implementacji.

479
480
481
482
483
484
485
486
487
488
489
        /**
     * This helper method split out from add(E) to keep method
     * bytecode size under 35 (the -XX:MaxInlineSize default value),
     * which helps when add(E) is called in a C1-compiled loop.
     */

    private void add(E e, Object[] elementData, int s) {
        if (s == elementData.length)
            elementData = grow();
        elementData[s] = e;
        size = s + 1;
    }

Zachowanie metody zgadza się z naszymi przewidywaniami. Argument s jest aktualnym rozmiarem tablicy (jeśli nie wiesz dlaczego – zwróć uwagę na poprzedni listing i wywołanie metody add). Jeśli aktualny rozmiar tablicy jest mniejszy od rozmiaru całkowitego – sytuacja jest prosta. Nowy element zapisujemy na kolejnej pozycji tablicy. Jeśli natomiast przekroczylibyśmy jej rozmiar – musimy powiększyć tablicę elementData.

240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
    private Object[] grow() {
        return grow(size + 1);
    }

    private Object[] grow(int minCapacity) {
        return elementData = Arrays.copyOf(elementData,
                                           newCapacity(minCapacity));
    }
    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);
    }

Powiększenie wewnętrznej tablicy ArrayList, jak widzimy na powyższym listingu, zasadniczo składa się z dwóch etapów. Pierwszym z nich jest obliczenie nowego rozmiaru tablicy. Odpowiada za to metoda newCapacity.

W jaki sposób wyliczany jest rozmiar nowej tablicy? Clue logiki znajduje się w linijce 251. Operator >>, jak dobrze wiemy, jest operatorem przesunięcia bitowego w prawo. Co się stanie, jak wykonamy przesunięcie bitowe o 1 w prawo? Jest to odpowiednik mnożenia przez liczbę 2. Połowa tablicy jest już zajęta, więc rozmiar tablicy zostanie zwiększony o 50%.

Zwróć uwagę na wykorzystanie zmiennej DEFAULT_CAPACITY i DEFAULTCAPACITY_EMPTY_ELEMENTDATA. Jeśli użyliśmy konstruktora bezargumentowego ArrayList(), dodanie pierwszego elementu spowoduje, że tablica zostanie rozszerzona do wielkości wskazanej przez zmienną DEFAULT_CAPACITY (10 elementów). W przeciwnym wypadku używane są domyślne reguły.

W momencie, gdy posiadamy już nowy rozmiar tablicy, kopiujemy zawartość starej tablicy do nowej. W tym momencie możemy już dodać nowy element.

Nr powiększenianew ArrayList<>()new ArrayList<>(0)
11 element1 element
210 element2 element
315 element3 element
422 element4 element
534 element5 element
650 element7 element
12550 element64 element

Spójrz na powyższą tabelę. Pokazuje ona moment wywołania metody grow dla dwóch metod stworzenia ArrayListy. Widzisz, dlaczego domyślny rozmiar ArrayList został ustawiony na 10? Przy dodawaniu 50 elementów tablica jest powiększana tylko 6 razy. Jeśli wstępny rozmiar tablicy wynosi 0, podobny rozmiar uzyskamy dopiero po 12 wywołaniach metody grow.

Jaki możemy wyciągnąć wniosek? Jeśli wiemy, że:

  • będziemy przechowywali bardzo dużą ilość elementów
  • kopiowanie przechowywanych elementów jest kosztowne

to powinniśmy utworzyć ArrayList<> wstępnie deklarując ilość elementów, jakie będziemy przechowywali. Dzięki temu unikniemy kosztownego kopiowania elementów przy każdym powiększeniu przestrzeni.

Usuwanie elementów z ArrayList

Jak działa usuwanie elementów z ArrayList? Skoro dodawanie zwiększa rozmiar wewnętrznej tablicy, to czy usuwanie będzie ją zmniejszało? Zobaczmy!

669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
    public E remove(int index) {
        Objects.checkIndex(index, size);
        final Object[] es = elementData;

        @SuppressWarnings("unchecked") E oldValue = (E) es[index];
        fastRemove(es, index);

        return oldValue;
    }


private void fastRemove(Object[] es, int i) {
        modCount++;
        final int newSize;
        if ((newSize = size - 1) > i)
            System.arraycopy(es, i + 1, es, i, newSize - i);
        es[size = newSize] = null;
    }

W linijce 673 wykonywane jest „brzydkie” rzutowanie. Dzięki temu możemy zapisać wartość usuwanego elementu aby potem móc go zwrócić.

Najważniejsza jest implementacja metody fastRemove. Spójrz na linijkę 684. Jeśli usuwamy element ze „środka” tablicy, wszystkie elementy znajdujące się na lewo od niego przesuwamy o jedną pozycję. Jeśli kasujemy element znajdujący się na końcu listy – po prostu go nullujemy. Na końcu zmniejszamy rozmiar tablicy (nie fizycznie – jedynie ten „widoczny dla użytkownika” czyli wartość zmiennej size).

Serializacja/deserializacja

Na koniec zajmijmy się pewną ciekawostką. Wróćmy do fragmentu pierwszego listingu.

transient Object[] elementData;

Zwróć uwagę na to, że elementData oznaczony jest słowem kluczowym transient. Oznacza to, że elementData nie zostanie poddany serializacji. Ale listy ArrayList można przecież serializować! Jak to jest możliwe? ArrayList korzysta z własnego mechanizmu serializacji [3]. Jej fragment został przytoczony na poniższym listingu.

886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
    private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException {
        // Write out element count, and any hidden stuff
        int expectedModCount = modCount;
        s.defaultWriteObject();

        // Write out size as capacity for behavioral compatibility with clone()
        s.writeInt(size);

        // Write out all elements in the proper order.
        for (int i=0; i<size; i++) {
            s.writeObject(elementData[i]);
        }

        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }

Dlaczego zostało wybrane takie rozwiązanie? Zwróć uwagę na to, iż wewnętrzna tablica praktycznie zawsze będzie miała rozmiar większy niż ilość faktycznie zapisanych elementów. W przypadku korzystania z domyślnego mechanizmu, puste pola także zostałyby zserializowane. Zaimplementowany przez twórców implementacji mechanizm zapobiega temu (linijki 896-898).

Jak prawidłowo korzystać z ArrayList?

Skoro wiemy już, jak działa ArrayList, spróbujmy wyciągnąć kilka wniosków. Najważniejszym wnioskiem jest potrzeba dobrania odpowiedniego rozmiaru startowego w wypadku, gdy kopiowanie przechowywanych elementów jest kosztowne obliczeniowo. Pamiętajmy też, że nie każda operacja w ArrayList posiada taką samą wydajność.

  • add(): Dodawanie pojedynczego elementu na końcu listy jest najszybsze i zawsze wykonuje się tyle samo czasu. Złożoność obliczeniowa: O(1).
  • remove(): Posiada liniową złożoność obliczeniową O(n). Po pierwsze, trzeba znaleźć element, który chcemy usunąć. Po drugie natomiast – „wypełnić lukę” przesuwając wszystkie elementy o 1 w lewo.
  • add(index, element): Dodanie elementu w środku tablicy będzie mniej więcej tak samo szybkie jak usuwanie elementów. Operacja ta posiada złożoność O(n). Dlaczego? Ponieważ, podobnie jak przy usuwaniu, musimy przesunąć wszystkie elementy listy aby zrobić element na nowododawany.
  • get() – Zawsze trwa tyle samo czasu. Złożoność O(1).
  • indexOf() – Czas trwania liniowo zależy od rozmiaru tablicy O(n). W najgorszym wypadku musimy przejrzeć wszystkie elementy tablicy, aby znaleźć indeks szukanego.
  • contains(): Implementacja wykorzystuje wewnętrznie metodę indexOf(). Złożoność obliczeniowa będzie więc taka sama: O(n).
  • size, isEmpty, iterator, listIterator – te operacje potrzebuja stałego czasu O(1).

Co warto zapamiętać?

Wynotujmy najważniejsze rzeczy, które warto mieć z tyłu głowy (m.in. ze względu na to, że pytania o takie szczegóły czasami pojawiają się na rozmowach kwalifikacyjnych):

  • ArrayList jest implementacją tablicy o zmiennym rozmiarze. (to każdy wie)
  • Implementacja ArrayList opiera się na zwykłej tablicy obiektów.
  • Jeden z konstruktorów ArrayList pozwala na zdefiniowanie początkowego rozmiaru. Wewnętrzna tablica osiągnie taki rozmiar po dodaniu pierwszego elementu.
  • Domyślnie tablica znajdująca się wewnątrz ArrayList jest 10-elementowa.
  • Kiedy dodajemy nowy element, najpierw sprawdzamy czy się on zmieści. Jeśli nie – musimy zwiększyć tablicę o 50% jest aktualnej wielkości.

Zapisz się do newslettera i polub mój Fanpage

Podobał ci się ten artykuł? Kliknij dzwoneczek (w lewej dolnej części ekranu) i zapisz się na powiadomienia. Dzięki temu, kiedy opublikuję nowy artykuł, dostaniesz o tym natychmiastową informację i jednocześnie zainspirujesz mnie do dalszej pracy :). Polajkuj fanpage.

Zapisz się do newslettera!

Jeśli zauważyłeś jakiś błąd, nie zrozumiałeś czegoś lub chcesz się podzielić niewspomnianymi w tym artykule wnioskami – śmiało – napisz komentarz. Będę niezmiernie wdzięczny 🙂

Dzięki za lekturę i Powodzenia!

Źródła

[1] https://docs.oracle.com/javase/7/docs/api/java/util/RandomAccess.html
[2] https://www.geeksforgeeks.org/internal-working-of-arraylist-in-java/
[3] https://stackoverflow.com/questions/9848129/why-does-arraylist-use-transient-storage
[4] https://github.com/AdoptOpenJDK/openjdk-jdk11/blob/master/src/java.base/share/classes/java/util/ArrayList.java

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Wymagane pola są oznaczone *