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

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.

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.

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

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ę.

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.

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.

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.

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.

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.

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!

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.

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.

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