{"id":2573,"date":"2021-04-22T16:20:22","date_gmt":"2021-04-22T14:20:22","guid":{"rendered":"https:\/\/www.kompikownia.pl\/?p=2573"},"modified":"2021-04-22T16:27:55","modified_gmt":"2021-04-22T14:27:55","slug":"java-internals-jak-dziala-arraylist-jezyku-java","status":"publish","type":"post","link":"https:\/\/www.kompikownia.pl\/index.php\/2021\/04\/22\/java-internals-jak-dziala-arraylist-jezyku-java\/","title":{"rendered":"Java Internals: Jak dzia\u0142a ArrayList j\u0119zyku Java?"},"content":{"rendered":"Czas czytania:<\/span> 3<\/span> minut<\/span><\/span>\n

Programuj\u0105c w j\u0119zyku Java, z pewno\u015bci\u0105 wielokrotnie korzysta\u0142e\u015b z r\u00f3\u017cnego rodzaju list (ArrayList, LinkedList itd). Ale czy zastanawia\u0142e\u015b si\u0119 kiedy\u015b, jak wygl\u0105da ich wewn\u0119trzna implementacja? Analizowa\u0142e\u015b, jak wp\u0142ywa ona na przyk\u0142ad na wydajno\u015b\u0107 twojego programu oraz zajmowan\u0105 przeze\u0144 pami\u0119\u0107? W tym artykule zajmiemy si\u0119 analiz\u0105 wewn\u0119trznej implementacji ArrayList, bazuj\u0105c na implementacji openjdk-11 [4]<\/a>.<\/p>\n\n\n\n

Czym jest ArrayList?<\/h2>\n\n\n\n

ArrayList jest tablic\u0105, kt\u00f3rej rozmiar mo\u017cna dynamicznie zmienia\u0107. W przeciwie\u0144stwie do zwyk\u0142ych tablic, kt\u00f3re maj\u0105 sta\u0142y rozmiar, ArrayList ro\u015bnie dynamicznie w miar\u0119 jak dodajemy do niej nowe elementy.<\/p>\n\n\n\n

Na pocz\u0105tku przyjrzyjmy si\u0119 definicji ArrayList. <\/p>\n\n\n

public<\/span> class<\/span> ArrayList<<\/span>E><\/span> extends<\/span> AbstractList<<\/span>E><\/span>
\n        implements<\/span> List<<\/span>E><\/span>, RandomAccess, Cloneable<\/span><\/a>, java.io<\/span>.Serializable<\/span><\/a><\/div><\/div>\n\n\n\n

ArrayList rozszerza klas\u0119 AbstractList<E><\/em>. Klasa ta jest „szkieletem” dla implementacji interfejsu List<E>. AbstractList<E> dostarcza implementacji „uniwersalnych” metod, jak „lastIndexOf”, „addAll” itd. kt\u00f3rych mechanizm dzia\u0142ania nie zale\u017cy od konkretnej implementacji listy. <\/p>\n\n\n\n

Interfejs znacznikowy RandomAccess<\/em> [1]<\/a> u\u017cywany jest do oznaczenia klas, w kt\u00f3rych dost\u0119p do poszczeg\u00f3lnych element\u00f3w listy jest bardzo szybki. ArrayList spe\u0142nia ten warunek. Dost\u0119p do dowolnego elementu listy uzyskamy w czasie O(1). (Nie ma znaczenia, czy jest to element pierwszy, drugi, setny czy milionowy). <\/p>\n\n\n\n

Interfejs znacznikowy Cloneable <\/em>zapewnia, \u017ce obiekt klasy mo\u017cna sklonowa\u0107. B\u0119dzie to tzw. „deep copy” <\/strong>(g\u0142\u0119boka kopia). Oznacza to, \u017ce po wywo\u0142aniu metody clone <\/em>skopiowane do nowego obiektu zostan\u0105 nie referencje, a zawarto\u015b\u0107 wszystkich element\u00f3w istniej\u0105cych w obiekcie. <\/p>\n\n\n\n

Interfejs znacznikowy Serializable <\/em>m\u00f3wi, \u017ce klasa jest serializowalna. <\/p>\n\n\n\n

Prywatne statyczne elementy klasy ArrayList<\/h2>\n\n\n\n

Przyjrzyjmy si\u0119 nast\u0119puj\u0105cemu fragmentowi implementacji klasy ArrayList.<\/p>\n\n\n

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
<\/div><\/td>
  private<\/span> static<\/span> final<\/span> int<\/span> DEFAULT_CAPACITY =<\/span> 10<\/span>;<\/span>
\n
\n    \/**
\n     * Shared empty array instance used for empty instances.
\n     *\/<\/span>
\n    private<\/span> static<\/span> final<\/span> Object<\/span><\/a>[<\/span>]<\/span> EMPTY_ELEMENTDATA =<\/span> {<\/span>}<\/span>;<\/span>
\n
\n    \/**
\n     * Shared empty array instance used for default sized empty instances. We
\n     * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
\n     * first element is added.
\n     *\/<\/span>
\n    private<\/span> static<\/span> final<\/span> Object<\/span><\/a>[<\/span>]<\/span> DEFAULTCAPACITY_EMPTY_ELEMENTDATA =<\/span> {<\/span>}<\/span>;<\/span>
\n
\n    \/**
\n     * The array buffer into which the elements of the ArrayList are stored.
\n     * The capacity of the ArrayList is the length of this array buffer. Any
\n     * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
\n     * will be expanded to DEFAULT_CAPACITY when the first element is added.
\n     *\/<\/span>
\n    transient<\/span> Object<\/span><\/a>[<\/span>]<\/span> elementData;<\/span> \/\/ non-private to simplify nested class access<\/span>
\n
\n    \/**
\n     * The size of the ArrayList (the number of elements it contains).
\n     *
\n     * @serial
\n     *\/<\/span>
\n    private<\/span> int<\/span> size;<\/span><\/div><\/td><\/tr><\/tbody><\/table><\/div>\n\n\n\n

Ju\u017c na podstawie tego fragmentu i deklaracji kilku prywatnych element\u00f3w klasy ArrayList mo\u017cemy domy\u015bli\u0107 si\u0119, w jakiej strukturze elementy wewn\u0105trz niej s\u0105 przechowywane. Jest to oczywi\u015bcie zwyk\u0142a tablica obiekt\u00f3w Object[]<\/strong>. Jej deklaracj\u0119 widzimy w linijce 131 na powy\u017cszym listingu. Zastosowanie wyja\u015bnia zreszt\u0105 komentarz umieszczony w kodzie \u017ar\u00f3d\u0142owym. <\/p>\n\n\n\n

Domy\u015blny rozmiar pustej ArrayListy sugeruje zmienna DEFAULT_CAPACITY<\/em> znajduj\u0105ca si\u0119 w linijce 111. Wynosi ona 10 element\u00f3w. Ale czy faktycznie dla pustej ArrayListy wewn\u0119trzna tablica obiekt\u00f3w ma rozmiar 10? W\u0105tpliwo\u015bci rozbudzaj\u0105 zmienne EMPTY_ELEMENTDATA<\/em> i DEFAULTCAPACITY_EMPTY_ELEMENTDATA<\/em>. Wielko\u015b\u0107 tych tablic wynosi 0. Aby rozwia\u0107 nasze w\u0105tpliwo\u015bci, zerknijmy na kod \u017ar\u00f3d\u0142owy konstruktor\u00f3w ArrayListy.<\/p>\n\n\n\n

Konstruktory klasy ArrayList<\/h2>\n\n\n
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
<\/div><\/td>
    \/**
\n     * Constructs an empty list with the specified initial capacity.
\n     *
\n     * @param  initialCapacity  the initial capacity of the list
\n     * @throws IllegalArgumentException if the specified initial capacity
\n     *         is negative
\n     *\/<\/span>
\n    public<\/span> ArrayList<\/span><\/a>(<\/span>int<\/span> initialCapacity)<\/span> {<\/span>
\n        if<\/span> (<\/span>initialCapacity><\/span>0<\/span>)<\/span> {<\/span>
\n            this<\/span>.elementData<\/span> =<\/span> new<\/span> Object<\/span><\/a>[<\/span>initialCapacity]<\/span>;<\/span>
\n        }<\/span> else<\/span> if<\/span> (<\/span>initialCapacity ==<\/span> 0<\/span>)<\/span> {<\/span>
\n            this<\/span>.elementData<\/span> =<\/span> EMPTY_ELEMENTDATA;<\/span>
\n        }<\/span> else<\/span> {<\/span>
\n            throw<\/span> new<\/span> IllegalArgumentException<\/span><\/a>(<\/span>"Illegal Capacity: "<\/span>+<\/span>
\n                                               initialCapacity)<\/span>;<\/span>
\n        }<\/span>
\n    }<\/span><\/div><\/td><\/tr><\/tbody><\/table><\/div>\n\n\n\n

Pierwszy z trzech konstruktor\u00f3w pozwala na stworzenie ArrayListy o okre\u015blonej pocz\u0105tkowej pojemno\u015bci. Taki konstruktor tworzy tablic\u0119 elementData o wielko\u015bci przekazanej w konstruktorze (je\u015bli ta wielko\u015b\u0107 jest wi\u0119ksza od zera). Je\u015bli initialCapacity<\/em> wynosi 0, rozmiar tablicy domy\u015blnie wynosi 0. Przy dodawaniu kolejnych element\u00f3w b\u0119dzie on zwi\u0119kszany. A jak? Om\u00f3wimy to sobie za chwil\u0119. <\/p>\n\n\n

163
164
165
166
167
168
<\/div><\/td>
  \/**
\n     * Constructs an empty list with an initial capacity of ten.
\n     *\/<\/span>
\n    public<\/span> ArrayList<\/span><\/a>(<\/span>)<\/span> {<\/span>
\n        this<\/span>.elementData<\/span> =<\/span> DEFAULTCAPACITY_EMPTY_ELEMENTDATA;<\/span>
\n    }<\/span><\/div><\/td><\/tr><\/tbody><\/table><\/div>\n\n\n\n

W konstruktorze bezparametrowym nie ma wielkiej filozofii. Domy\u015blny rozmiar wynosi 0, a ArrayLista jest pusta. <\/p>\n\n\n\n

Zagadka: <\/strong>Czy polecenia new ArrayList<>(0)<\/em> i new ArrayList<>()<\/em> po dodaniu pierwszego elementu utworz\u0105 wewn\u0119trznie tablic\u0119 o tym samym rozmiarze? Zastan\u00f3w si\u0119 nad tym zanim przejdziesz do dalszej cz\u0119\u015bci tekstu. Zwr\u00f3\u0107 uwag\u0119 na to, \u017ce tw\u00f3rcy implementacji rozr\u00f3\u017cnili te dwie sytuacje za pomoc\u0105 inicjacji ArrayListy dwoma r\u00f3\u017cnymi obiektami: albo za pomoc\u0105 DEFAULTCAPACITY_EMPTY_ELEMENTDATA<\/em> albo EMPTY_ELEMENTDATA<\/em>.<\/p>\n\n\n\n\n

170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
<\/div><\/td>
    \/**
\n     * Constructs a list containing the elements of the specified
\n     * collection, in the order they are returned by the collection's
\n     * iterator.
\n     *
\n     * @param c the collection whose elements are to be placed into this list
\n     * @throws NullPointerException if the specified collection is null
\n     *\/<\/span>
\n    public<\/span> ArrayList<\/span><\/a>(<\/span>Collection<?<\/span> extends<\/span> E><\/span> c)<\/span> {<\/span>
\n        Object<\/span><\/a>[<\/span>]<\/span> a =<\/span> c.toArray<\/span>(<\/span>)<\/span>;<\/span>
\n        if<\/span> (<\/span>(<\/span>size =<\/span> a.length<\/span>)<\/span> !=<\/span> 0<\/span>)<\/span> {<\/span>
\n            if<\/span> (<\/span>c.getClass<\/span>(<\/span>)<\/span> ==<\/span> ArrayList<\/span><\/a>.class<\/span>)<\/span> {<\/span>
\n                elementData =<\/span> a;<\/span>
\n            }<\/span> else<\/span> {<\/span>
\n                elementData =<\/span> Arrays<\/span><\/a>.copyOf<\/span>(<\/span>a, size, Object<\/span><\/a>[<\/span>]<\/span>.class<\/span>)<\/span>;<\/span>
\n            }<\/span>
\n        }<\/span> else<\/span> {<\/span>
\n            \/\/ replace with empty array.<\/span>
\n            elementData =<\/span> EMPTY_ELEMENTDATA;<\/span>
\n        }<\/span>
\n    }<\/span><\/div><\/td><\/tr><\/tbody><\/table><\/div>\n\n\n\n\n

Przyjrzyjmy si\u0119 ostatniemu konstruktorowi. Tworzy on kopi\u0119 ArrayListy na podstawie kolekcji zawartej w argumencie konstruktora. <\/p>\n\n\n\n

Na pocz\u0105tku kolekcja konwertowana jest do tablicy obiekt\u00f3w. Uzyskana tablica jest przypisywana do wewn\u0119trznej ArrayListowej tablicy elementData. Je\u015bli \u017ar\u00f3d\u0142owa kolekcja jest pusta, konstruktor zachowa si\u0119 tak samo jak wywo\u0142anie new ArrayList<>(0); <\/p>\n\n\n\n

Dodawanie i usuwanie element\u00f3w ArrayList<\/h2>\n\n\n\n

Skoro wiemy, w jaki spos\u00f3b obiekt ArrayList jest konstruowany, pora zastanowi\u0107 si\u0119 jak dzia\u0142a operacja dodawania i usuwania element\u00f3w. Zanim przejdziemy do analizy kodu zastan\u00f3wmy si\u0119 jak by to mog\u0142o dzia\u0142a\u0107 – na logik\u0119. Musimy posiada\u0107 wska\u017anik, kt\u00f3ry m\u00f3wi nam jaki jest aktualny rozmiar tablicy. Je\u015bli ten wska\u017anik jest mniejszy od rozmiaru tablicy – sytuacja jest prosta. Zapisujemy wtedy dodawany element w kolejnej kom\u00f3rce tablicy. Je\u015bli tak nie jest – trzeba w jaki\u015b spos\u00f3b zwi\u0119kszy\u0107 rozmiar tablicy. Jak to zrobili tw\u00f3rcy implementacji openjdk? Zobaczmy. <\/p>\n\n\n

503
504
505
506
507
508
509
510
511
512
513
<\/div><\/td>
     \/**
\n     * Appends the specified element to the end of this list.
\n     *
\n     * @param e element to be appended to this list
\n     * @return {@code true} (as specified by {@link Collection#add})
\n     *\/<\/span>
\n    public<\/span> boolean<\/span> add(<\/span>E e)<\/span> {<\/span>
\n        modCount++;<\/span>
\n        add(<\/span>e, elementData, size)<\/span>;<\/span>
\n        return<\/span> true<\/span>;<\/span>
\n    }<\/span><\/div><\/td><\/tr><\/tbody><\/table><\/div>\n\n\n\n

Publiczna metoda add<\/em> nie jest d\u0142uga. Zawiera tylko trzy linijki :). modCount<\/em> jest polem zadeklarowanym w klasie AbstractList.<\/em> Przekazuje ono informacj\u0119 o tym, ile razy lista by\u0142a modyfikowana. Nast\u0119pna linijka to wywo\u0142anie prywatnej metody add<\/em>. Przyjrzyjmy si\u0119 jej implementacji.<\/p>\n\n\n

479
480
481
482
483
484
485
486
487
488
489
<\/div><\/td>
        \/**
\n     * This helper method split out from add(E) to keep method
\n     * bytecode size under 35 (the -XX:MaxInlineSize default value),
\n     * which helps when add(E) is called in a C1-compiled loop.
\n     *\/<\/span>
\n    private<\/span> void<\/span> add(<\/span>E e, Object<\/span><\/a>[<\/span>]<\/span> elementData, int<\/span> s)<\/span> {<\/span>
\n        if<\/span> (<\/span>s ==<\/span> elementData.length<\/span>)<\/span>
\n            elementData =<\/span> grow(<\/span>)<\/span>;<\/span>
\n        elementData[<\/span>s]<\/span> =<\/span> e;<\/span>
\n        size =<\/span> s +<\/span> 1<\/span>;<\/span>
\n    }<\/span><\/div><\/td><\/tr><\/tbody><\/table><\/div>\n\n\n\n

Zachowanie metody zgadza si\u0119 z naszymi przewidywaniami. Argument s<\/em> jest aktualnym rozmiarem tablicy (je\u015bli nie wiesz dlaczego – zwr\u00f3\u0107 uwag\u0119 na poprzedni listing i wywo\u0142anie metody add<\/em>). Je\u015bli aktualny rozmiar tablicy jest mniejszy od rozmiaru ca\u0142kowitego – sytuacja jest prosta. Nowy element zapisujemy na kolejnej pozycji tablicy. Je\u015bli natomiast przekroczyliby\u015bmy jej rozmiar – musimy powi\u0119kszy\u0107 tablic\u0119 elementData.<\/em><\/p>\n\n\n

240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
<\/div><\/td>
    private<\/span> Object<\/span><\/a>[<\/span>]<\/span> grow(<\/span>)<\/span> {<\/span>
\n        return<\/span> grow(<\/span>size +<\/span> 1<\/span>)<\/span>;<\/span>
\n    }<\/span>
\n
\n    private<\/span> Object<\/span><\/a>[<\/span>]<\/span> grow(<\/span>int<\/span> minCapacity)<\/span> {<\/span>
\n        return<\/span> elementData =<\/span> Arrays<\/span><\/a>.copyOf<\/span>(<\/span>elementData,
\n                                           newCapacity(<\/span>minCapacity)<\/span>)<\/span>;<\/span>
\n    }<\/span>
\n    private<\/span> int<\/span> newCapacity(<\/span>int<\/span> minCapacity)<\/span> {<\/span>
\n        \/\/ overflow-conscious code<\/span>
\n        int<\/span> oldCapacity =<\/span> elementData.length<\/span>;<\/span>
\n        int<\/span> newCapacity =<\/span> oldCapacity +<\/span> (<\/span>oldCapacity >><\/span> 1<\/span>)<\/span>;<\/span>
\n        if<\/span> (<\/span>newCapacity -<\/span> minCapacity <=<\/span> 0<\/span>)<\/span> {<\/span>
\n            if<\/span> (<\/span>elementData ==<\/span> DEFAULTCAPACITY_EMPTY_ELEMENTDATA)<\/span>
\n                return<\/span> Math<\/span><\/a>.max<\/span>(<\/span>DEFAULT_CAPACITY, minCapacity)<\/span>;<\/span>
\n            if<\/span> (<\/span>minCapacity <<\/span> 0<\/span>)<\/span> \/\/ overflow<\/span>
\n                throw<\/span> new<\/span> OutOfMemoryError<\/span><\/a>(<\/span>)<\/span>;<\/span>
\n            return<\/span> minCapacity;<\/span>
\n        }<\/span>
\n        return<\/span> (<\/span>newCapacity -<\/span> MAX_ARRAY_SIZE <=<\/span> 0<\/span>)<\/span>
\n            ?<\/span> newCapacity
\n            :<\/span> hugeCapacity(<\/span>minCapacity)<\/span>;<\/span>
\n    }<\/span><\/div><\/td><\/tr><\/tbody><\/table><\/div>\n\n\n\n

Powi\u0119kszenie wewn\u0119trznej tablicy ArrayList, jak widzimy na powy\u017cszym listingu, zasadniczo sk\u0142ada si\u0119 z dw\u00f3ch etap\u00f3w. Pierwszym z nich jest obliczenie nowego rozmiaru tablicy. Odpowiada za to metoda newCapacity. <\/em><\/p>\n\n\n\n

W jaki spos\u00f3b wyliczany jest rozmiar nowej tablicy? Clue logiki znajduje si\u0119 w linijce 251. Operator >>, jak dobrze wiemy, jest operatorem przesuni\u0119cia bitowego w prawo. Co si\u0119 stanie, jak wykonamy przesuni\u0119cie bitowe o 1 w prawo? Jest to odpowiednik mno\u017cenia przez liczb\u0119 2. Po\u0142owa tablicy jest ju\u017c zaj\u0119ta, wi\u0119c rozmiar tablicy zostanie zwi\u0119kszony o 50%. <\/p>\n\n\n\n

Zwr\u00f3\u0107 uwag\u0119 na wykorzystanie zmiennej DEFAULT_CAPACITY<\/em> i DEFAULTCAPACITY_EMPTY_ELEMENTDATA. <\/em>Je\u015bli u\u017cyli\u015bmy konstruktora bezargumentowego ArrayList(), <\/em>dodanie pierwszego elementu spowoduje, \u017ce tablica zostanie rozszerzona do wielko\u015bci wskazanej przez zmienn\u0105 DEFAULT_CAPACITY <\/em>(10 element\u00f3w). W przeciwnym wypadku u\u017cywane s\u0105 domy\u015blne regu\u0142y. <\/p>\n\n\n\n

W momencie, gdy posiadamy ju\u017c nowy rozmiar tablicy, kopiujemy zawarto\u015b\u0107 starej tablicy do nowej. W tym momencie mo\u017cemy ju\u017c doda\u0107 nowy element. <\/p>\n\n\n\n

Nr powi\u0119kszenia<\/td>new ArrayList<>()<\/td>new ArrayList<>(0)<\/td><\/tr>
1<\/td>1 element<\/td>1 element<\/td><\/tr>
2<\/td>10 element<\/td>2 element<\/td><\/tr>
3<\/td>15 element<\/td>3 element<\/td><\/tr>
4<\/td>22 element<\/td>4 element<\/td><\/tr>
5<\/td>34 element<\/td>5 element<\/td><\/tr>
6<\/td>50 element<\/td>7 element<\/td><\/tr>
12<\/td>550 element<\/td>64 element<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

Sp\u00f3jrz na powy\u017csz\u0105 tabel\u0119. Pokazuje ona moment wywo\u0142ania metody grow <\/em>dla dw\u00f3ch metod stworzenia ArrayListy. Widzisz, dlaczego domy\u015blny rozmiar ArrayList zosta\u0142 ustawiony na 10? Przy dodawaniu 50 element\u00f3w tablica jest powi\u0119kszana tylko 6 razy. Je\u015bli wst\u0119pny rozmiar tablicy wynosi 0, podobny rozmiar uzyskamy dopiero po 12 wywo\u0142aniach metody grow. <\/em><\/p>\n\n\n\n

Jaki mo\u017cemy wyci\u0105gn\u0105\u0107 wniosek? Je\u015bli wiemy, \u017ce:<\/p>\n\n\n\n