Artikel ini menganalisis kode sumber ArrayList. Izinkan saya berbicara tentang array sebelum menganalisisnya. Array mungkin merupakan salah satu struktur data pertama yang kami hubungi. Mereka membagi ruang alamat yang berkelanjutan dalam memori untuk menyimpan elemen. Karena secara langsung mengoperasikan memori, kinerja array lebih baik daripada kelas koleksi, yang merupakan keuntungan utama menggunakan array. Tetapi kita tahu bahwa array memiliki cacat fatal, yaitu, ukuran array harus ditentukan selama inisialisasi, dan ukuran array tidak dapat diubah dalam operasi berikutnya. Dalam situasi yang sebenarnya, kami menemukan lebih banyak hal yang kami tidak tahu berapa banyak elemen yang akan disimpan di awal, tetapi sebaliknya berharap bahwa wadah dapat secara otomatis memperluas kapasitasnya sendiri sehingga dapat menyimpan lebih banyak elemen. ArrayList dapat memenuhi kebutuhan seperti itu dengan sangat baik, dan secara otomatis dapat memperluas ukuran untuk beradaptasi dengan peningkatan elemen penyimpanan yang berkelanjutan. Lapisan yang mendasarinya diimplementasikan berdasarkan array, sehingga memiliki beberapa fitur array, seperti menemukan modifikasi cepat dan penyisipan dan penghapusan lambat. Dalam artikel ini, kita akan masuk jauh ke dalam kode sumber untuk melihat bagaimana merangkum array. Pertama -tama lihat variabel anggotanya dan tiga konstruktor utama.
// Kapasitas Inisialisasi Default Private Static Final Int Default_Capacity = 10; // Objek Kosong Objek Statis Privat Statis Objek akhir [] kosong_elementData = {}; // Objek Array Private Transient Obyek [] ElementData; // Jumlah elemen pengumpulan ukuran int pribadi; // Metode Konstruktor untuk Melewati Kapasitas Awal Kapasitas Publik Arraylist (Int InitialCapacity) (Metode Initial) {) {Metode Initial () {Initial) {{/{Metode Initial () {Initial) {inter elemen () {{{{{{{) {inter elements; if (initialcapacity <0) {lempar baru ilegalArgumentException ("kapasitas ilegal:"+ initialcapacity); } // Buat array tipe objek baru dari kapasitas yang ditentukan this.elementData = objek baru [initialcapacity];} // konstruktor tanpa parameter arraylist publik () {super (); // Lewati contoh array kosong ke elementData this.elementData = empleme_elementdata;} // metode konstruktor untuk masuk ke dalam koleksi eksternal arraylist publik (koleksi <? Memperluas e> c) {// tahan elemen referensi dari array internal yang diteruskan ke koleksi elementData = c.toArray (); // Perbarui jumlah elemen ukuran koleksi = elementData.length; // menilai jenis array referensi dan mengonversi referensi ke referensi array objek if (elementData.getClass ()! = Objek []. Class) {elementData = arrays.copyof (elementData, size, objek []. Class); }}Anda dapat melihat bahwa struktur penyimpanan internal ArrayList adalah berbagai jenis objek, sehingga dapat menyimpan elemen jenis apa pun. Saat membangun daftar array, jika ukuran awal dilewati, itu akan membuat array objek baru dari kapasitas yang ditentukan. Jika ukuran awal tidak diatur, itu tidak akan mengalokasikan ruang memori tetapi menggunakan array objek kosong, dan kemudian mengalokasikan memori ketika elemen sebenarnya ditempatkan. Mari kita lihat metode penambahan, menghapus, memodifikasi, dan mencari.
// Tingkatkan (Tambah) Boolean Publik Tambah (E E) {// Periksa apakah array perlu diperluas sebelum ditambahkan, panjang array minimum adalah ukuran + 1 Ensurecapacityinternal (ukuran + 1); // tambahkan elemen ke ujung elemen array [ukuran ++] = e; return true;} // Tingkatkan (masukkan) public void add (indeks int, elemen e) {// masukkan rentang posisi periksa rangeCheckForAdd (index); // Periksa apakah kapasitas perlu diperluas Ensurecapacityinternal (ukuran + 1); // Pindahkan elemen di belakang System Posisi Penyisipan.ArrayCopy (ElementData, Indeks, ElementData, Indeks + 1, Ukuran - Indeks); // Tetapkan nilai baru elementData [index] = elemen; SIZE ++;} // Hapus Publik E Remove (INT INDEX) {// INDEX tidak boleh lebih besar dari ukuran RangeCheck (indeks); modcount ++; E oldValue = elementData (indeks); int nummoved = ukuran - indeks - 1; if (nummoved> 0) {// Pindahkan elemen di belakang indeks ke depan oleh satu system.arraycopy (elementData, index+1, elementData, index, nummoved); } // Referensi kosong elementData [-size] = null; return oldValue;} // Ubah Set Publik E (indeks int, elemen E) {// indeks tidak dapat lebih besar dari ukuran rangecheck (indeks); E oldValue = elementData (indeks); // ganti dengan elemen elemen baru [indeks] = elemen; return oldValue;} // periksa publik e get (index) {// index tidak boleh lebih besar dari ukuran rangecheck (index); // kembalikan elemen elemen elemen yang ditentukan elementData (indeks);} Setiap kali elemen ditambahkan ke koleksi, pertama -tama akan memeriksa apakah kapasitasnya cukup, jika tidak kapasitas akan diperluas. Rincian ekspansi kapasitas akan dibahas di bawah ini. Pertama -tama mari kita lihat poin -poin spesifik yang harus diperhatikan saat menambahkan, menghapus, memodifikasi, dan memeriksa.
Tambahkan (Tambah): Cukup tambahkan elemen ini ke akhir. Operasi cepat.
Tambah (Sisipkan): Operasi lebih lambat karena elemen di belakang posisi penyisipan perlu dipindahkan dan penyalinan array terlibat.
Hapus: Karena elemen -elemen di balik posisi penghapusan perlu dipindahkan ke depan, salinan array juga akan dirancang, sehingga operasinya lambat.
Ubah: Langsung memodifikasi elemen di lokasi yang ditentukan, tanpa melibatkan gerakan elemen atau menyalin array, dan operasinya cepat.
Periksa: Langsung kembalikan elemen array dari subskrip yang ditentukan, dan operasinya cepat.
Dari kode sumber, dapat dilihat bahwa karena pencarian dan modifikasi diposisikan langsung ke subskrip array, itu tidak melibatkan gerakan elemen dan menyalin array, sehingga lebih cepat. Namun, karena elemen perlu dipindahkan, itu melibatkan penyalinan array, sehingga operasinya lebih lambat. Selain itu, setiap operasi penambahan juga dapat melakukan ekspansi array, yang juga akan mempengaruhi kinerja. Mari kita lihat bagaimana ArrayList secara dinamis memperluas kapasitasnya.
Private void EnsureCapacityInternal (int MinCapacity) {// Jika array masih kosong pada saat ini jika (elementData == kosong_elementData) {// Bandingkan dengan kapasitas default, ambil nilai yang lebih besar MinCapacity = Math.max (default_capacity, mincapacity); } // Jika array telah diinisialisasi, lakukan langkah ini EnsureExplicitCapacity (MinCapacity);} private void ensureeexplicitCapacity (int MinCapacity) {modcount ++; // Jika kapasitas minimum lebih besar dari panjang array, amplifikasi array if (MinCapacity - elementData.length> 0) {grow (MinCapacity); }} // Kapasitas maksimum dari koleksi private static final int max_array_size = integer.max_value - 8; // Tingkatkan panjang array batal pribadi tumbuh (int mincapacity) {// Dapatkan kapasitas asli array int oldcapacity = elementData.length; // Kapasitas array baru, tambahkan setengah pada basis asli int newcapacity = oldcapacity + (oldcapacity >> 1); // Periksa apakah kapasitas baru kurang dari kapasitas minimum IF (newcapacity - mintcapacity <0) {newCapacity = mincapacity; } // Periksa apakah kapasitas baru melebihi kapasitas array maksimum IF (newCapacity - max_array_size> 0) {newCapacity = hugeCapacity (MinCapacity); } // Salin array asli ke array baru elementData = arrays.copyof (elementData, newcapacity);} Sebelum menambahkan elemen, EnsureCapacityinternal akan dipanggil untuk pemeriksaan kapasitas pengumpulan. Di dalam metode ini, ia akan memeriksa apakah array internal koleksi saat ini masih merupakan array kosong. Jika ya, buat array objek baru dengan ukuran default 10. Jika tidak, itu membuktikan bahwa koleksi saat ini telah diinisialisasi. Kemudian hubungi metode EnsureExplicitCapacity untuk memeriksa apakah kapasitas array saat ini memenuhi kapasitas minimum yang diperlukan. Jika tidak puas, hubungi metode tumbuh untuk berkembang. Dalam metode Grow, Anda dapat melihat bahwa setiap ekspansi adalah untuk meningkatkan setengah dari panjang array asli. Ekspansi sebenarnya untuk membuat array baru dengan kapasitas lebih besar, salin semua elemen array asli ke array baru, dan kemudian buang array asli dan gunakan array baru. Sejauh ini, kami telah menganalisis metode yang lebih umum digunakan dalam daftar array, dan beberapa poin penting yang perlu diperhatikan:
1. Implementasi ArrayList yang mendasari didasarkan pada array, sehingga pencarian dan modifikasi subskrip yang ditentukan lebih cepat, tetapi operasi penghapusan dan penyisipan lebih lambat.
2. Saat membangun daftar array, cobalah untuk menentukan kapasitas sebanyak mungkin untuk mengurangi operasi salinan array yang disebabkan oleh ekspansi. Jika Anda tidak tahu ukurannya, Anda dapat menetapkan kapasitas default ke 10.
3. Sebelum menambahkan elemen, periksa apakah perlu ekspansi kapasitas. Setiap ekspansi kapasitas adalah setengah dari kapasitas asli.
4. Setiap kali operasi subskrip dioperasikan, pemeriksaan keamanan akan dilakukan. Jika array di luar batas, pengecualian akan segera dilemparkan.
5. Semua metode arraylist tidak disinkronkan, jadi tidak aman.
6. Analisis di atas didasarkan pada JDK1.7, dan versi lain akan memiliki beberapa perbedaan, sehingga tidak dapat digeneralisasi.
Di atas adalah semua konten artikel ini. Saya berharap ini akan membantu untuk pembelajaran semua orang dan saya harap semua orang akan lebih mendukung wulin.com.