1. Analisis Kode Sumber ArrayList (JDK7)
ArrayList mempertahankan array objek dinamis secara internal. Penambahan dan penghapusan arraylist yang dinamis adalah penambahan dan penghapusan yang dinamis dari pasangan kelompok ini.
1. Konstruksi dan inisialisasi ArrayList
ArrayList instance variable//ArrayList default capacity private static final int DEFAULT_CAPACITY = 10;//Default empty Object array, used to define empty ArrayListprivate static final Object[] EMPTY_ELEMENTDATA = {};//ArrayList stores the Object array private transient Object[] elementData;//The number of elements in ArrayList private int size;Konstruktor ArrayList:
No Parameter Constructor: yaitu, buat objek kosong []
arraylist publik () {super (); this.elementData = empleme_elementdata;} Tentukan konstruk ukuran kapasitas:
arraylist publik (int initialcapacity) {super (); if (InitialCapacity <0) melempar IllegalArgumentException baru ("Kapasitas Ilegal:"+ InitialCapacity); this.elementData = objek baru [initialcapacity];} Tentukan struktur koleksi yang mengimplementasikan antarmuka koleksi:
Public ArrayList (Collection <? Extends e> c) {elementData = c.toArray (); size = elementData.length; // c.toarray mungkin (salah) tidak mengembalikan objek [] (lihat 6260652) if (elementData.getClass ()! = objek []. Class) elementData = arrays.copyof (elementData, ukuran, objek []. Kelas);}Ini juga menjelaskan peran koleksi, dan alasan mengapa java-collection-framwork merancang antarmuka koleksi alih-alih secara langsung menggunakan daftar, set, dan antarmuka lainnya.
2. Mekanisme Alokasi Kapasitas ArrayList
Kapasitas Kapasitas untuk ArrayList: Kapasitas ArrayList adalah batas atas, dan teori memungkinkan alokasi integer.max_value - kapasitas ukuran 8. Namun, berapa banyak yang dapat dialokasikan tergantung pada pengaturan tumpukan, dan parameter VM perlu diatur
private static final int max_array_size = integer.max_value - 8;
Perpanjang volume saat memanggil metode Tambah
public boolean add (e e) {ensurecapacityinternal (ukuran + 1); // Menambah ModCount !! elementData [size ++] = e; Kembali Benar; }Metode EnsureCapacity Internal (INT) sebenarnya menentukan ukuran ekspansi minimum.
private void ensureCapacityInternal (int minCapacity) {if (elementData == kosong_elementData) {Minsapacity = math.max (default_capacity, MinCapacity); } ensureExplicitCapacity (MinCapacity); } private void ensureExplicitCapacity (int minCapacity) {modcount ++; // overflow -consent code if (MinCapacity - elementData.length> 0) Grow (MinCapacity); } Tentang ModCount: ModCount didefinisikan dalam Daftar Abstrak Kelas Abstrak. Komentar kode sumber pada dasarnya menjelaskan penggunaannya: Saat menggunakan Iterator untuk melintasi, digunakan untuk memeriksa apakah elemen dalam daftar memiliki perubahan struktural (jumlah dari jumlah elemen daftar telah berubah). Ini terutama digunakan dalam lingkungan multi-threaded untuk mencegah satu utas dari iterasi dan utas lain yang memodifikasi struktur daftar ini.
Metode pertumbuhan adalah metode ekspansi nyata
private void grow (int mincapacity) {// overflow-conscious code int oldcapacity = elementData.length; int newcapacity = oldcapacity + (oldcapacity >> 1); if (newcapacity - mincapacity <0) newcapacity = mincapacity; if (newcapacity - max_array_size> 0) newcapacity = hugeCapacity (mintcapacity); // MinCapacity biasanya mendekati ukuran, jadi ini adalah win: elementData = arrays.copyof (elementData, newcapacity); }Ada juga metode hugeCapacity untuk berapa banyak kapasitas yang diperluas
private static int hugeCapacity (int mincapacity) {if (Minsapacity <0) // overflow lempar outofmemoryError baru (); return (Mincapacity> max_array_size)? Integer.max_value: max_array_size; } Meringkaskan:
Setiap ekspansi disertai dengan salinan array, jadi memberikan kapasitas yang tepat pada suatu waktu akan sedikit meningkatkan kinerja.
Angka berikut adalah seluruh proses ekspansi yang saya ringkas:
3.arraylist iterator
Ada dua iterator utama ArrayList dan Listitr, tetapi ArrayListSpliterator juga ditambahkan dalam JDK1.8. Mari kita pelajari analisis kode sumber ITR dan Listitr masing -masing.
(1) ITR: hanya bisa mundur
kelas pribadi ITR mengimplementasikan iterator <E> {int kursor; // indeks elemen berikutnya untuk mengembalikan int lastret = -1; // indeks elemen terakhir dikembalikan; -1 Jika tidak ada // yang diharapkan MODCount adalah salinan ModCount Int diharapkan Modcount = ModCount; public boolean hasnext () {return kursor! = size; } @Suppresswarnings ("Uncecked") public e next () {checkForComodification (); // Catat posisi saat ini int i = kursor; if (i> = size) melempar nosuchelementException baru (); Objek [] elementData = arraylist.this.elementData; if (i> = elementData.length) melempar concurrentmodificationException baru (); // posisi kursor elemen berikutnya = i + 1; return (e) elementData [lastret = i]; } // Gunakan metode hapus iterator public void remove () {if (lastret <0) Lempar IllegalStateException baru (); checkForComodification (); Coba {// Perhatikan bagaimana kelas dalam memanggil arraylist kelas luar.this.remove (lastret); // Setelah menghapus, Anda harus menyesuaikan kembali posisi setiap kursor pointer = lastret; lastret = -1; diharapkan modcount = modcount; } catch (IndexOutOfBoundSException ex) {Throw New ConcurrentModificationException (); }} final void checkForComodification () {if (modcount! = diharapkan modcount) lempar concurrentModificationException baru (); }} Dari kode sumber, dapat dilihat bahwa ITR iterator adalah iterator maju, yang menyediakan metode berikutnya untuk mendapatkan elemen di daftar array.
CheckForComodifikasi adalah mekanisme deteksi kesalahan gagal dalam java-collection-framwork. Operasi pada set yang sama dalam lingkungan multi-utas dapat memicu mekanisme gagal-cepat dan melemparkan pengecualian Exception ConcurrentModification.
ITR iterator mendefinisikan salinan Record ModCount yang diharapkan. Ketika ArrayList melakukan operasi untuk mengubah struktur, seperti menambahkan, menghapus, dan menghapus metode, nilai MODCount akan berubah.
Melalui kode sumber ITR, dapat dilihat bahwa memanggil metode berikutnya dan menghapus akan memicu pemeriksaan gagal-cepat. Pada saat ini, jika pengecualian terjadi ketika utas lain melakukan operasi yang mengubah struktur set saat melintasi set.
(2) Listitr: mendukung traversal maju dan mundur. Mari kita lihat kode sumber Listitr:
Private Class ListItr memperluas ITR mengimplementasikan listiterator <E> {listitr (int index) {super (); kursor = indeks; } public boolean hasprevious () {return cursor! = 0; } public int nextIndex () {return kursor; } public int priorIndex () {return kursor - 1; } @SuppressWarnings ("Uncecked") public e sebelumnya () {checkForComodification (); // Posisi elemen sebelumnya dari arraylist int i = kursor - 1; if (i <0) melempar nosuchelementException baru (); Objek [] elementData = arraylist.this.elementData; if (i> = elementData.length) melempar concurrentmodificationException baru (); kursor = i; return (e) elementData [lastret = i]; } // Metode set ditambahkan ke Iterator Public Void Set ini (E E) {if (LASTRET <0) Lempar IllegalStateException baru (); checkForComodification (); coba {arraylist.this.set (lastret, e); } catch (IndexOutOfBoundSException ex) {Throw New ConcurrentModificationException (); }} // iterator ini menambahkan metode tambah public void add (e e) {checkForComodification (); coba {int i = kursor; Arraylist.this.add (i, e); // Komentar kursor posisi pointer = i + 1; lastret = -1; diharapkan modcount = modcount; } catch (IndexOutOfBoundSException ex) {Throw New ConcurrentModificationException (); }}}Implementasi Listitr pada dasarnya sama dengan ITR, menambahkan metode yang dapat dilintasi sebelumnya, serta menambahkan dan mengatur metode.
(3) Gunakan CopyonWriteArrayList di java.util.concurrent untuk menyelesaikan masalah cepat gagal
CopyOnWriteArrayList adalah utas-aman. Untuk detailnya, mari kita lihat kode Sumber Tambah Metodenya:
public boolean add (e e) {final reentrantlock lock = this.lock; lock.lock (); coba {objek [] elemen = getArray (); int len = elemen.length; Objek [] newElements = arrays.copyof (elemen, len + 1); NewElements [len] = e; setArray (NewElements); Kembali Benar; } akhirnya {lock.unlock (); }} CopyOnWriteArrayList adalah daftar array yang disalin. Saat memulai pengoperasian data penulisan, array. Copyof adalah array baru, yang tidak akan mempengaruhi operasi baca.
Biaya ini adalah kehilangan ingatan dan menyebabkan masalah kinerja. Ketika CopyOnWriteArrayList ditulis, objek salinan dihasilkan dalam memori, dan objek asli masih ada.
CopyOnWriteArrayList tidak dapat menjamin konsistensi data secara real time, ia hanya dapat menjamin konsistensi hasil. Cocok untuk skenario seperti cache saat membaca lebih banyak dan menulis lebih banyak dan menulis lebih sedikit dalam situasi bersamaan.
(4) Metode lain Sumber Kode ArrayList:
Batchremove metode pribadi (koleksi <?> C, komplemen boolean), yaitu operasi penghapusan batch
Private Boolean Batchremove (Collection <?> C, Boolean Complement) {// Alasan untuk menggunakan final disebutkan di bawah objek akhir [] elementData = this.elementData; int r = 0, w = 0; boolean dimodifikasi = false; coba {// ketenangan melalui elemen dalam daftar dan verifikasi untuk (; r <size; r ++) if (c.contains (elementData [r]) == komplemen) elementData [w ++] = elementData [r]; } akhirnya {// Jika pengecualian terjadi di coba, pastikan konsistensi data dan lakukan operasi salinan berikut jika (r! = size) {System.ArrayCopy (ElementData, R, ElementData, W, Size - R); w += ukuran - r; } // Bersihkan elemen yang tidak digunakan dan beri tahu GC untuk mendaur ulang jika (w! = Size) {// Bersihkan untuk membiarkan GC melakukan pekerjaannya untuk (int i = w; i <size; i ++) elementData [i] = null; modcount += size - w; ukuran = w; dimodifikasi = true; }} return dimodifikasi; } Variabel yang dimodifikasi oleh final mengacu pada referensi yang sama untuk mempertahankan konsistensi data nanti.
Dalam metode ini, ketika Anda ingin mempertahankan elemen dalam koleksi C, nilai komplemennya benar; Ketika Anda ingin menghapus elemen di C, nilai komplemen salah. Ini masing -masing menjadi metode retainall dan hapus.
Pertukaran: Pertukaran Dua Posisi di Daftar Array
2. Analisis Kode Sumber LinkedList (JDK7)
LinkedList adalah daftar tertaut. Dibandingkan dengan tabel pesanan, daftar tertaut tidak perlu menggunakan unit memori kontinu untuk menyimpan data. Mengurangi masalah elemen bergerak yang disebabkan oleh memodifikasi struktur wadah, dan akses berurutan relatif efisien.
1. Definisi Node
LinkedList di JDK adalah daftar ditautkan dua arah, masing -masing simpul menyimpan informasi tentang simpul sebelumnya dan masing -masing simpul berikutnya. Definisi ini adalah sebagai berikut:
node kelas statis privat <e> {e item; Node <E> Berikutnya; Node <e> Sebelumnya; Node <E> (node <E> prev, elemen e, node <E> NEXT) {this.item = elemen; this.next = next; this.prev = prev; }}2. Konstruksi dan inisialisasi Daftar Linked
Anggota: 3 variabel anggota dipertahankan di LinkedList untuk merekam jumlah node dalam daftar tertaut, pendahulu dan penerus node
ukuran int transien = 0; simpul transien <e> pertama; node transien <e> terakhir;
Konstruktor: Konstruktor default adalah membangun daftar tautan kosong
linkedlist publik () {}Atau konstruksi berdasarkan wadah lain, dan kemudian kami akan menulis konstruktor untuk membentuk daftar tautan yang dipesan.
Public LinkedList (Collection <? Extends e> c) {this (); addall (c);}Ini sedikit ekstra. Untuk perbedaan antara pengubah generik? Super T dan memperluas T, lihat artikel ini tentang perbedaan antara Super T dan memperluas T dalam generik.
3. Operasi Struktural LinkedList
Metode penyisipan header: yaitu, masukkan elemen di header daftar tertaut
private void linkFirst (e e) {node akhir <e> f = pertama; node akhir <E> newNode = node baru <> (null, e, f); pertama = newnode; // menilai apakah itu daftar tertaut kosong jika (f == null) terakhir = newnode; lain f.prev = newNode; ukuran ++; modcount ++; } Metode penyisipan ekor: yaitu, masukkan elemen di ujung daftar yang ditautkan
void linkLast (e e) {node akhir <E> l = terakhir; node akhir <e> newNode = node baru <> (l, e, null); terakhir = newnode; if (l == null) first = newNode; lain l.next = newNode; ukuran ++; modcount ++; } Sebelum memasukkan ke dalam simpul saat ini: Temukan drive depan dari node saat ini
void linkBefore (e e, node <e> succ) {// Tentukan apakah simpul tidak kosong tentu saja node akhir <e> pred = succ.prev; node akhir <E> newNode = node baru <> (pred, e, succ); succ.prev = newNode; // Tentukan apakah simpul saat ini adalah simpul pertama IF (pred == null) pertama = newNode; lain pred.next = newNode; ukuran ++; modcount ++; } Metode Penghapusan Header: Hapus simpul pertama dari daftar tertaut
private e UNLINKFIRST (node <E> f) {// Assert f == pertama && f! = null; elemen E akhir = f.item; Node akhir <E> NEXT = F.NEXT; f.item = null; f.next = null; // BANTUAN GC First = Next; if (next == null) terakhir = null; lain next.prev = null; ukuran--; modcount ++; elemen kembali; } Metode Penghapusan Ekor: Hapus simpul terakhir dari daftar tertaut
private e unlinkLast (node <E> l) {// Pastikan l == Last dan L! = Null Final E Element = L.Item; Node akhir <E> prev = l.prev; l.item = null; l.prev = null; // BANTUAN GC LAST = PREV; if (prev == null) pertama = null; lain prev.next = null; ukuran--; modcount ++; elemen kembali; }4. Pertahankan konsistensi antara antarmuka daftar dan deque
Antarmuka daftar memungkinkan penggunaan subskrip untuk mengimplementasikan akses acak ke wadah, dan mudah untuk menerapkan akses acak ke array seperti ini. Untuk daftar tertaut, JDK juga secara logis menggunakan jumlah node dalam daftar tertaut untuk memberikan implementasi akses acak
Node <E> node (indeks int) {// Pastikan kebenaran indeks if (index <(size >> 1)) {node <E> x = pertama; untuk (int i = 0; i <index; i ++) x = x.next; mengembalikan x; } else {node <E> x = terakhir; untuk (int i = ukuran-1; i> index; i--) x = x.prev; mengembalikan x; }} Indeks adalah penghitungan babak pertama, cari dari awal. Indeks milik penghitungan babak kedua, dan mencari dari akhir. Manfaatkan sepenuhnya karakteristik daftar tertaut dua arah.
Oleh karena itu, tambahkan (indeks int, tt), get (int), set (int) dan metode lain dapat dengan mudah diimplementasikan.
LinkedList mengimplementasikan antarmuka deque, yaitu, LinkedList mengimplementasikan metode wadah antrian ganda. Berikut adalah beberapa ringkasan API.
5. LinkedList Traversal
Karena LinkedList adalah daftar tertaut dua arah, Anda secara alami dapat melintasi bolak-balik. Seperti ArrayList, LinkedList juga memiliki masalah gagal-cepat ketika datang ke operasi wadah multi-threading.
Masalah gagal-cepat telah dijelaskan dalam artikel sebelumnya, jadi saya tidak akan membicarakannya di sini.
Mengenai iterator, LinkedList memiliki daftar arah dua arah daftarterator, dan descendingiterator terbalik iterator. Semuanya sangat sederhana. Kode sumber tidak dianalisis
Jika Anda melintasi elemen, biaya akses acak relatif tinggi.
3. LinkedList, ArrayList, Ringkasan Vektor
1. LinkedList dan ArrayList
ArrayList mengimplementasikan struktur data berdasarkan array dinamis, dan LinkedList didasarkan pada struktur data berdasarkan daftar tertaut.
Untuk akses acak untuk mendapatkan dan mengatur, ArrayList terasa lebih baik daripada LinkedList karena LinkedList menggerakkan pointer.
Untuk operasi baru dan hapus, tambahkan dan hapus, LinedList memiliki keuntungan yang lebih baik karena ArrayList perlu memindahkan data. Ini tergantung pada situasi sebenarnya. Jika hanya satu bagian data yang dimasukkan atau dihapus, kecepatan arraylist lebih baik daripada yang ada di LinkedList. Namun, jika data dimasukkan secara acak dalam batch, kecepatan LinkedList jauh lebih baik daripada arraylist. Karena setiap kali arraylist menyisipkan data, perlu untuk memindahkan titik penyisipan dan semua data sesudahnya.
2. ArrayList dan Vector
Vektor adalah utas-sinkron, jadi juga aman, sedangkan arraylist adalah thread-asyn, yang tidak aman. Jika faktor keamanan utas tidak diperhitungkan, ArrayList umumnya lebih efisien.
Jika jumlah elemen dalam set lebih besar dari panjang array set saat ini, laju pertumbuhan vektor adalah 100% dari panjang array saat ini, dan laju pertumbuhan arraylist adalah 50% dari panjang array saat ini. Jika menggunakan data dengan jumlah data yang relatif besar dalam set, menggunakan vektor memiliki keunggulan tertentu.
Jika Anda mencari data di lokasi yang ditentukan, waktu yang digunakan oleh Vector dan ArrayList adalah sama, keduanya 0 (1), dan Anda dapat menggunakan vektor dan arraylist saat ini. Jika waktu yang dihabiskan untuk memindahkan data di lokasi yang ditentukan adalah 0 (Ni) N, yang merupakan panjang total, Anda harus mempertimbangkan untuk menggunakan LinkList, karena dibutuhkan 0 (1) untuk memindahkan data di lokasi yang ditentukan, dan waktu yang dihabiskan untuk meminta data di lokasi yang ditentukan adalah 0 (i).
ArrayList dan vektor menggunakan array untuk menyimpan data. Jumlah elemen dalam array ini lebih besar dari data tersimpan yang sebenarnya untuk menambah dan memasukkan elemen. Keduanya memungkinkan elemen indeks nomor seri langsung. Namun, memasukkan data harus dirancang untuk memindahkan elemen array dan operasi memori lainnya, sehingga data indeks cepat dan lambat untuk memasukkan data. Vektor menggunakan metode sinkronisasi (utas aman), sehingga kinerja lebih buruk daripada arraylist. LinkedList menggunakan daftar ditautkan dua arah untuk menyimpan data. Pengindeksan data sesuai dengan nomor seri memerlukan traversal maju atau mundur, tetapi ketika memasukkan data, hanya item depan dan belakang item ini yang direkam, sehingga memasukkan beberapa derajat lebih cepat!