Untuk waktu yang lama, daftar data yang lebih sering digunakan dalam kode ini terutama adalah daftar, dan mereka semua adalah daftar array. Rasanya hal ini sudah cukup. ArrayList adalah kelas alat pembungkus yang digunakan untuk mengimplementasikan array dinamis, sehingga ketika menulis kode, Anda dapat menarik masuk dan keluar, mengulangi dan melintasi, yang cukup nyaman.
Saya tidak tahu kapan saya mulai perlahan memulai kelas alat seperti hashmap dan hashset sering muncul dalam kode. Harus dikatakan bahwa hashmap lebih umum, dan itu juga merupakan pertanyaan wawancara klasik, jadi saya akan membacanya lebih banyak dalam kehidupan sehari -hari. Ketika saya pertama kali mulai menggunakannya, saya hanya memahaminya sebagai tabel yang sesuai dengan nilai kunci, dan lebih nyaman untuk menggunakan kunci untuk menemukan data. Setelah penyelidikan lebih lanjut, saya mengetahuinya
Benda ini memiliki beberapa rahasia, terutama setelah versi baru JDK mengubah hashmap ke pohon, kodenya agak rumit.
Saya mulai menggunakan set lebih sedikit, tetapi saya secara tidak sengaja menemukan sebuah pohon dalam kode. Saya menemukan bahwa kelas ini bisa datang dengan kehalusan. Rasanya cukup menarik. Saya secara bertahap menemukan bahwa ini juga merupakan alat yang baik.
Jika Anda menulis terlalu banyak kode, Anda akan merasakan pentingnya dasar -dasarnya, jadi di sini saya menulis artikel pendek untuk mengatur secara singkat beberapa pengetahuan tentang koleksi tersebut.
Oke, mari kita selesaikan secara singkat:
• Daftar: yaitu, daftar, yang mendukung fungsi array dan daftar tertaut, dan umumnya linier.
• Peta: Ini adalah tabel pemetaan, yang menyimpan hubungan yang sesuai antara kunci dan nilai.
• Set: Berarti set, terutama digunakan untuk mengurutkan data dan mengurutkan
Mari kita lihat daftar dulu
Daftar adalah jendela untuk menyimpan data linier, seperti: ArrayList untuk array dan LinkedList untuk daftar tertaut.
Daftar Array
Ini adalah daftar array, tetapi menyediakan fungsi ekspansi otomatis untuk mewujudkan antarmuka daftar. Operasi eksternal diakses melalui metode Deklarasi Antarmuka, yang aman dan nyaman.
Kunci untuk ArrayList adalah ekspansi kapasitas otomatis. Kapasitas awal dapat diatur ketika objek diinisialisasi atau kapasitas default dapat diukur. Jika ukuran array tidak terlalu jelas, ukuran awal tidak dapat ditentukan. Jika jelas, suatu ukuran dapat ditentukan, yang mengurangi jeda yang disebabkan oleh ekspansi dinamis. Berbicara tentang ini, kita perlu berbicara tentang bagaimana ekspansi diterapkan. Lihat kode berikut:
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); }Grow adalah metode yang memicu daftar array saat menambahkan elemen atau beberapa pemeriksaan mudah. Proses utama:
1. Dapatkan panjang array dan pindahkan ke kanan, yang setara dengan Oldcapacity/2, dan dapatkan panjang baru
2. Jika panjang ini kurang dari kapasitas minimum, mudah digunakan secara langsung.
3. Jika lebih besar dari maksimum, ambil nilai maksimum. Metode HugeCapacity akan disebut di sini, terutama untuk membandingkan cincang dengan max_array_size. Jika cincangcity lebih besar dari max_array_size, ambil integer.max_value, jika tidak ambil max_array_size. Menariknya, max_array_size mengambil integer.max_value - 8; Saya tidak tahu apa artinya melakukan ini
4. Akhirnya, hubungi metode salin untuk menyalin nomor yang ada ke array baru.
Karena proses penyalinan ini, jika array relatif besar, maka ekspansi pasti akan menyebabkan lag. Jadi, jika Anda mengetahui nilai maksimum dari awal dan mudah untuk tumbuh ke nilai ini, maka menentukan ukuran ketika memulai inisialisasi akan memiliki efek tertentu.
LinkedList
Ini adalah kelas alat untuk daftar tertaut. Keuntungan dari daftar yang ditautkan adalah bahwa mereka menambah dan menghapus hal -hal lebih cepat, tetapi mereka akan menemukannya lebih lambat.
Adapun kode, tampaknya tidak ada yang istimewa adalah bahwa itu dihubungkan bersama oleh serangkaian petunjuk. Tentu saja, Java menggunakan objek sebagai gantinya untuk membuat objek node. Node itu sendiri menunjuk ke simpul sebelumnya dan simpul berikutnya. Ini adalah struktur daftar yang ditautkan:
node kelas statis privat <e> {e item; Node <E> Berikutnya; Node <e> Sebelumnya; Node (node <E> prev, elemen e, node <E> selanjutnya) {this.item = elemen; this.next = next; this.prev = prev; }}Kemudian gunakan dua node untuk menunjuk ke kepala dan ekor dan selesai. Kode berikut:
/*** Pointer ke Node Pertama. * Invarian: (pertama == null && last == null) || * (first.prev == null && first.item! = null) */ node transien <E> pertama; /*** Pointer ke Node Terakhir. * Invarian: (pertama == null && last == null) || * (last.next == null && last.item! = null) */ node transien <E> terakhir;
Lihat Operasi Tambah:
/*** tautan E sebagai elemen terakhir. */ 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 ++; }Masa lalu adalah:
1. Dapatkan simpul terakhir dan letakkan di l
2. Buat node baru dan ambil data ke dalam node ini. Proses pembuatan akan mengarahkan prev dari simpul baru ke L, sehingga akan terhubung ke rantai.
3. Lalu point terakhir ke simpul baru ini
4. Kemudian tentukan apakah L adalah nol. Jika null null, itu berarti itu adalah daftar tertaut kosong. Node baru adalah elemen pertama. Dengan cara ini, yang pertama juga harus menunjuk ke newnode
5. Jika tidak kosong, arahkan Next of L ke Newnode
6. Penghitung Akumulasi
Operasi penghapusan juga merupakan simpul depan dan belakang yang menunjuk ke pengoperasian node ini.
Mari kita lihat peta
Peta adalah aplikasi tabel pemetaan untuk kunci dan nilai. Kelas Implementasi Utama: HashMap, Hashtable, TreeMap
Hashmap dan hashtable
HashMap adalah yang menggunakan algoritma hash untuk pemetaan nilai kunci. Hashtable adalah kelas yang aman dari utas dengan sinkronisasi. Ini adalah perbedaan utama di antara mereka. Prinsipnya serupa, dan semuanya dicapai melalui kombinasi rantai ember +. Bucket digunakan untuk menyimpan kunci, dan nilainya perlu disimpan dalam daftar tertaut karena tabrakan hash.
• Signifikansi ember terletak pada efisiensi, dan dapat diposisikan dalam satu langkah melalui perhitungan hash.
• Arti dari daftar tertaut adalah untuk mengakses data hash berulang
Prinsip spesifik saya menulis "Catatan Studi: Hashtable dan Hashmap" sebelumnya
Tetapi saya hanya melihat bahwa hashmap JDK1.8 telah mengubah struktur penyimpanannya dan mengadopsi struktur pohon merah dan hitam. Ini dapat menyelesaikan efisiensi pencarian daftar yang ditautkan? Tidak ada studi terperinci yang dilakukan.
TreeMap
Setelah membaca Kode TreeMap, saya menemukan bahwa saya masih menggunakan struktur pohon, pohon merah dan hitam. Karena pohon merah dan hitam dipesan, mereka secara alami memiliki fungsi penyortiran. Tentu saja, Anda juga dapat menentukan metode perbandingan melalui pembanding untuk mencapai penyortiran tertentu.
Karena struktur pohon digunakan untuk menyimpan, akan lebih merepotkan untuk menambah dan menghapus data. Mari kita lihat kode put:
public v put (key k, nilai v) {entri <k, v> t = root; if (t == null) {bandingkan (key, key); // type (dan kemungkinan null) periksa root = entri baru <> (tombol, nilai, null); ukuran = 1; modcount ++; kembali nol; } int cmp; Entri <k, v> orang tua; // pembanding split dan pembanding jalur yang sebanding <? super k> cpr = pembanding; if (cpr! = null) {do {parent = t; cmp = cpr.compare (key, t.key); if (cmp <0) t = t.left; lain jika (cmp> 0) t = t.right; lain return t.setValue (nilai); } while (t! = null); } else {if (key == null) lempar nullpointerException baru (); @SuppressWarnings ("Uncecked") sebanding <? super k> k = (sebanding <? super k>) kunci; lakukan {parent = t; CMP = K.COMPARETO (T.Key); if (cmp <0) t = t.left; lain jika (cmp> 0) t = t.right; lain return t.setValue (nilai); } while (t! = null); } Entri <k, v> e = entri baru <> (tombol, nilai, induk); if (cmp <0) parent.left = e; lain Parent.right = e; fixafterinsersion (e); ukuran ++; modcount ++; kembali nol; }1. Pertama periksa apakah ada simpul root. Jika tidak ada, itu berarti bahwa itu adalah bagian pertama dari data dan secara langsung digunakan sebagai akar pohon.
2. Tentukan apakah ada pembanding. Jika ada, gunakan pembanding untuk menemukan lokasi penyimpanan data. Jika hasil pengembalian pembanding kurang dari 0, ambil kiri, dan ambil ke kanan, jika tidak ganti nilai node saat ini secara langsung.
3. Jika tidak ada pembanding, kunci secara langsung dibandingkan dengan kunci node. Perbandingannya sama dengan metode sebelumnya.
4. Langkah selanjutnya adalah membuat simpul anak pada orang tua yang ditemukan dan meletakkannya di node anak kiri atau kanan.
5. FIXAFTERINSERTION adalah node mewarnai
6. Pemrosesan Akumulator
Ini juga akan sedikit merepotkan saat menghapus data. Selain menghapus data, Anda juga perlu menyeimbangkan kembali pohon merah dan hitam.
Selain itu, TreeMap mengimplementasikan antarmuka NavigableMap <K, V>, sehingga juga menyediakan beberapa operasi pengembalian pada set data.
Akhirnya, lihat set
Ditetapkan terutama memiliki dua jenis aplikasi: hashset dan treeset.
Hashset
Arti literalnya sangat jelas, menggunakan koleksi hash. Karakteristik dari koleksi ini adalah untuk menggunakan algoritma hash untuk menyimpan data, sehingga data tidak diduplikasi dan aksesnya relatif cepat. Bagaimana itu bisa dilakukan?
public boolean add (e e) {return map.put (e, present) == null; }Ternyata ada objek peta. Mari kita lihat apa peta itu?
Hashmap transien pribadi <e, objek> peta;
Itu adalah hashmap. Mereka yang tahu hashmap akan memahami bahwa data seperti itu tidak akan diulang. Karena objek itu sendiri disimpan sebagai kunci saat disimpan, hanya satu salinan yang akan ada di hashmap.
Setelah memahami hal ini dan hal -hal lain, Anda akan sangat mengerti.
Treeset
Set ini digunakan untuk mengurutkan set, yang berarti bahwa selain kemampuan untuk menyortir berat, ia juga dapat memiliki fungsi penyortirannya sendiri. Tetapi setelah melihat Kode Treeset, saya menemukan bahwa itu diimplementasikan dalam dasar -dasar TreeMap. Lebih tepatnya, itu harus menjadi kelas turunan navigablemap. Treeset didasarkan pada TreeMap tanpa menentukan peta secara default.
Treeset publik () {this (treemap baru <e, objek> ()); }Jadi, apa yang mungkin kita perhatikan di sini adalah bagaimana TreeSet adalah tugas berat? Mari kita lihat metode ADD:
public boolean add (e e) {return m.put (e, present) == null; }Ini agak mirip dengan hashset, yang keduanya didasarkan pada fitur peta untuk mencapai pemuatan berat. Ini sangat sederhana dan efektif.
Di atas adalah penjelasan terperinci dari set, daftar, dan peta di Java yang dibawa editor kepada Anda. Saya harap Anda dapat mendukung wulin.com lebih banyak ~