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.
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ększenia | new ArrayList<>() | new ArrayList<>(0) |
1 | 1 element | 1 element |
2 | 10 element | 2 element |
3 | 15 element | 3 element |
4 | 22 element | 4 element |
5 | 34 element | 5 element |
6 | 50 element | 7 element |
12 | 550 element | 64 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.
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