Tabel linier, daftar tertaut, dan tabel hash biasanya digunakan struktur data. Saat mengembangkan Java, JDK telah memberi kami serangkaian kelas yang sesuai untuk mengimplementasikan struktur data dasar. Kelas -kelas ini semuanya ada dalam paket java.util. Artikel ini mencoba menjelaskan kepada pembaca peran setiap kelas dan cara menggunakannya dengan benar melalui deskripsi sederhana.
Koleksi ├List │✜LinkedList │✜ArrayList │└Vector │└Stack └Set Map ├Hashtable ├HashMap └WeakHashMap
Antarmuka koleksi
Koleksi adalah antarmuka koleksi paling dasar. Koleksi mewakili satu set objek, yaitu elemen koleksi (elemen). Beberapa koleksi memungkinkan elemen yang sama sementara yang lain tidak. Beberapa bisa menyortir tetapi yang lain tidak bisa. Java SDK tidak menyediakan kelas yang secara langsung diwarisi dari koleksi. Kelas -kelas yang disediakan oleh Java SDK adalah semua "subinterfaces" yang diwarisi dari koleksi seperti daftar dan set.
Semua kelas yang mengimplementasikan antarmuka koleksi harus menyediakan dua konstruktor standar: konstruktor tanpa parameter digunakan untuk membuat koleksi kosong, dan konstruktor parameter koleksi digunakan untuk membuat koleksi baru, yang memiliki elemen yang sama dengan koleksi yang masuk. Konstruktor terakhir memungkinkan pengguna untuk menyalin koleksi.
Bagaimana cara mengulangi setiap elemen dalam koleksi? Terlepas dari jenis koleksi yang sebenarnya, ia mendukung metode iterator (), yang mengembalikan iterator, dan menggunakan iterator ini untuk mengakses setiap elemen dalam koleksi satu per satu.
Penggunaan tipikal adalah sebagai berikut:
Iterator it = collection.iterator (); // Dapatkan iterator while (it.hasnext ()) {objek obj = it.next (); // Dapatkan elemen berikutnya} Dua antarmuka yang berasal dari antarmuka koleksi adalah daftar dan diatur.
Daftar antarmuka
Daftar adalah koleksi yang dipesan, dan menggunakan antarmuka ini memungkinkan Anda untuk secara akurat mengontrol posisi setiap penyisipan elemen. Pengguna dapat menggunakan indeks (posisi elemen dalam daftar, mirip dengan subskrip array) untuk mengakses elemen dalam daftar, yang mirip dengan array Java.
Berbeda dengan set yang disebutkan di bawah ini, daftar memungkinkan elemen yang sama.
Selain metode iterator () yang memiliki metode Iterator () yang diperlukan, Daftar juga menyediakan metode ListIterator (), yang mengembalikan antarmuka ListIterator. Dibandingkan dengan antarmuka iterator standar, ListIterator memiliki lebih banyak metode seperti add (), memungkinkan penambahan, menghapus, mengatur elemen, dan melintasi ke depan atau ke belakang.
Kelas umum yang mengimplementasikan antarmuka daftar termasuk LinkedList, ArrayList, Vector dan Stack.
Kelas LinkedList
LinkedList mengimplementasikan antarmuka daftar, yang memungkinkan elemen nol. Selain itu, LinkedList memberikan Get, Lepas, Sisipkan metode tambahan di header atau ekor LinkedList. Operasi ini memungkinkan LinkedList untuk digunakan sebagai tumpukan, antrian, atau antrian dua arah.
Perhatikan bahwa LinkedList tidak memiliki metode sinkron. Jika beberapa utas mengakses daftar pada saat yang sama, Anda harus menerapkan sinkronisasi akses sendiri. Salah satu solusi adalah membuat daftar sinkron saat membuatnya:
Daftar daftar = collections.synchronizedList (LinkedList baru (...));
Kelas ArrayList
ArrayList mengimplementasikan array berukuran variabel. Ini memungkinkan semua elemen, termasuk nol. ArrayList tidak disinkronkan.
Metode pengoperasian ukuran, isply, get, set adalah konstan. Namun, overhead dari metode ADD adalah konstanta diamortisasi, dan dibutuhkan waktu untuk menambahkan elemen N. Metode lain memiliki waktu lari linier.
Setiap contoh arraylist memiliki kapasitas, yang merupakan ukuran array yang digunakan untuk menyimpan elemen. Kapasitas ini dapat meningkat secara otomatis karena elemen baru terus ditambahkan, tetapi algoritma pertumbuhan tidak didefinisikan. Ketika sejumlah besar elemen perlu dimasukkan, metode perasaan dapat dipanggil sebelum dimasukkan untuk meningkatkan kapasitas arraylist untuk meningkatkan efisiensi penyisipan.
Seperti LinkedList, ArrayList juga tidak disinkronkan.
Kelas Vektor
Vektor sangat mirip dengan ArrayList, tetapi vektor sinkron. Meskipun iterator yang dibuat oleh vektor adalah antarmuka yang sama dengan iterator yang dibuat oleh ArrayList, karena vektor disinkronkan, ketika satu iterator dibuat dan sedang digunakan, utas lain mengubah status vektor (misalnya, menambahkan atau menghapus beberapa elemen), concurrentModification Exception akan dilemparkan ketika Metode ITERATOR, SOLET, SOLET, SOLED, SOECTED.
Kelas tumpukan
Stack mewarisi dari vektor, menerapkan tumpukan keluar pertama yang terakhir. Stack menyediakan 5 metode tambahan untuk memungkinkan vektor digunakan sebagai tumpukan. Metode dorongan dan pop dasar, dan metode Peek mendapatkan elemen di bagian atas tumpukan, metode kosong menguji apakah tumpukan kosong, dan metode pencarian mendeteksi posisi elemen dalam tumpukan. Stack baru saja dibuat dan merupakan tumpukan kosong.
Atur antarmuka
Set adalah koleksi yang tidak mengandung elemen duplikat, yaitu, dua elemen E1 dan E2 memiliki E1.Equals (E2) = false, dan set memiliki paling banyak satu elemen nol.
Jelas, konstruktor SET memiliki kendala, dan parameter pengumpulan yang diteruskan tidak dapat berisi elemen duplikat.
Harap dicatat: Objek yang dapat berubah harus dioperasikan dengan hati -hati. Jika elemen yang dapat berubah dalam suatu set mengubah keadaannya sendiri, itu menyebabkan objek.
Antarmuka peta
Harap dicatat bahwa peta tidak mewarisi antarmuka koleksi, dan peta menyediakan pemetaan dari kunci ke nilai. Peta tidak dapat berisi kunci yang sama, dan setiap kunci hanya dapat memetakan satu nilai. Antarmuka peta menyediakan tiga jenis tampilan koleksi. Konten peta dapat dianggap sebagai satu set koleksi kunci, satu set koleksi nilai, atau satu set pemetaan nilai kunci.
Kelas hashtable
Hashtable mengimplementasikan antarmuka peta untuk mengimplementasikan tabel hash dengan pemetaan nilai kunci. Objek non-nol dapat digunakan sebagai kunci atau nilai.
Gunakan put (tombol, nilai) untuk menambahkan data, gunakan GET (Key) untuk mengambil data. Waktu overhead dari dua operasi dasar ini adalah konstan.
Hashtable menyesuaikan kinerja melalui parameter kapasitas dan faktor beban awal. Biasanya, faktor beban default 0,75 dapat mencapai keseimbangan waktu dan ruang. Meningkatkan faktor beban dapat menghemat ruang tetapi waktu pencarian yang sesuai akan meningkat, yang akan mempengaruhi operasi seperti Get and Put.
Contoh sederhana menggunakan hashtable adalah sebagai berikut: put 1, 2, dan 3 ke dalam hashtable, dan kunci mereka adalah "satu", "dua", "tiga" masing -masing:
Hashtable number = hashtable baru ();
number.put ("satu", bilangan bulat baru (1));
number.put ("dua", bilangan bulat baru (2));
number.put ("tiga", integer baru (3));
Untuk mengeluarkan angka, seperti 2, gunakan kunci yang sesuai:
Integer n = (integer) numbers.get ("dua");
System.out.println ("dua =" + n);
Karena suatu objek sebagai kunci akan menentukan posisi nilai yang sesuai dengan menghitung fungsi hashnya, objek apa pun sebagai kunci harus mengimplementasikan kode hash dan sama dengan metode. Kode hashcode dan sama dengan metode yang diwariskan dari objek kelas root. Jika Anda menggunakan kelas khusus sebagai kunci, berhati -hatilah. Menurut definisi fungsi hash, jika kedua objek tersebut sama, yaitu, Obj1.Equals (OBJ2) = Benar, kode hash mereka harus sama, tetapi jika kedua objek tersebut berbeda, kode hash mereka mungkin tidak berbeda. Jika kode hash dari dua objek yang berbeda adalah sama, fenomena ini disebut konflik. Konflik akan meningkatkan waktu overhead pengoperasian tabel hash. Oleh karena itu, cobalah untuk mendefinisikan metode hashcode () untuk mempercepat pengoperasian tabel hash.
Jika objek yang sama memiliki kode hash yang berbeda, operasi pada tabel hash akan memiliki hasil yang tidak terduga (metode get yang diharapkan mengembalikan nol). Untuk menghindari masalah ini, Anda hanya perlu mengingat satu hal: Anda harus menulis ulang metode Equals dan HashCode pada saat yang sama, daripada hanya menulis salah satunya.
Hashtable disinkronkan.
Kelas hashmap
HashMap mirip dengan hashtable, perbedaannya adalah hashmap asinkron dan memungkinkan nol, yaitu nilai nol dan kunci nol. , tetapi ketika hashmap dianggap sebagai koleksi (metode nilai () dapat mengembalikan koleksi), overhead waktu sub -operasi berulang sebanding dengan kapasitas hashmap. Oleh karena itu, jika kinerja operasi iterasi sangat penting, jangan atur kapasitas inisialisasi hashmap menjadi terlalu tinggi atau faktor beban terlalu rendah.
Kelas WeakHashMap
Lemari Hashmap adalah hashmap yang lebih baik yang mengimplementasikan "referensi lemah" ke kunci. Jika kunci tidak lagi dirujuk secara eksternal, kunci dapat didaur ulang oleh GC.
Meringkaskan
Jika tumpukan, antrian dan operasi lainnya terlibat, Anda harus mempertimbangkan untuk menggunakan daftar. Untuk elemen yang perlu dimasukkan dan dihapus dengan cepat, Anda harus menggunakan LinkedList. Jika elemen perlu diakses dengan cepat, Anda harus menggunakan ArrayList.
Java.util.Collections Paket Kelas
Kelas java.util.collections berisi banyak metode berguna yang dapat membuat pekerjaan pemrogram lebih mudah, tetapi metode ini biasanya tidak sepenuhnya digunakan. Javadoc memberikan deskripsi paling lengkap tentang kelas koleksi: "Kelas ini berisi kelas statis khusus yang dapat mengoperasikan atau mengembalikan koleksi.
”1.2 Metode Termasuk
Iterator, Daftar Array, Elemen, Buffer, Peta, Koleksi
Liezi:
impor java.util.arraylist; impor java.util.collection; impor java.util.collections; impor java.util.comparator; impor java.util.list; Public Class CollectionsSort {public collectionssort () {} public static void main (string [] args) {ganda array [] = {111, 111, 23, 456, 231}; Daftar Daftar = ArrayList baru (); Daftar li = arraylist baru (); untuk (int i = 0; i <array.length; i ++) {list.add (double baru (array [i])); //list.add(""+Arrayhti]); } ARR ganda [] = {111}; untuk (int j = 0; j <arr.length; j ++) {li.add (double baru (arr [j])); }}2. Operasi spesifik
1) urutkan (urutkan)
Gunakan metode sortir untuk mengurutkan daftar yang ditentukan dalam urutan naik sesuai dengan urutan alami elemen. Semua elemen dalam daftar harus mengimplementasikan antarmuka yang sebanding. Semua elemen dalam daftar ini harus dibandingkan satu sama lain menggunakan pembanding yang ditentukan
array ganda [] = {112, 111, 23, 456, 231}; untuk (int i = 0; i <array.length; i ++) {list.add (double baru (array [i])); } Collections.sort (daftar); untuk (int i = 0; i <array.length; i ++) {System.out.println (li.get (i)); } // Hasil: 112.111,23.456.2312) Mengocok
Algoritma pengaturan hibrida melakukan kebalikan dari jenis: Ini mengganggu permutasi apa pun yang dapat ditemukan dalam daftar. Artinya, daftar ini disusun ulang berdasarkan input sumber acak, pengaturan seperti itu memiliki kemungkinan yang sama (dengan asumsi bahwa sumber acak adil). Algoritma ini sangat berguna dalam mengimplementasikan permainan keberuntungan. Misalnya, ini dapat digunakan untuk mencampur daftar objek kartu yang mewakili setumpuk kartu. Selain itu, ini juga sangat berguna saat menghasilkan kasus uji.
Collections.shuffling (daftar) array ganda [] = {112, 111, 23, 456, 231}; untuk (int i = 0; i <array.length; i ++) {list.add (double baru (array [i])); } Collections.shuffle (daftar); untuk (int i = 0; i <array.length; i ++) {System.out.println (li.get (i)); } // Hasil: 112.111,23.456.2313) terbalik
Gunakan metode terbalik untuk mengurutkan daftar yang ditentukan dalam urutan menurun sesuai dengan urutan alami elemen.
Collections.reverse (daftar) array ganda [] = {112, 111, 23, 456, 231}; untuk (int i = 0; i <array.length; i ++) {list.add (double baru (array [i])); } Koleksi. terbalik (daftar); untuk (int i = 0; i <array.length; i ++) {System.out.println (li.get (i)); } // Hasil: 231.456,23,111,112 4) Ganti semua elemen dalam daftar yang ditentukan dengan elemen yang ditentukan. String str [] = {"dd", "aa", "bb", "cc", "ee"}; untuk (int j = 0; j <str.length; j ++) {li.add (string baru (str [j])); } Collections.fill (li, "aaa"); untuk (int i = 0; i <li.size (); i ++) {System.out.println ("Daftar [" + i + "] =" + li.get (i)); } // Hasil: AAA, AAA, AAA, AAA5) Salin (salin)
Gunakan dua parameter, daftar target dan daftar sumber, untuk menyalin elemen sumber ke target dan menimpa isinya. Daftar target setidaknya selama sumbernya. Jika lebih lama, elemen yang tersisa dalam daftar target tidak terpengaruh.
Collections.Copy (Daftar, Li): Parameter terakhir adalah daftar target, yang sebelumnya adalah daftar sumber
array ganda [] = {112, 111, 23, 456, 231}; Daftar Daftar = ArrayList baru (); Daftar li = arraylist baru (); untuk (int i = 0; i <array.length; i ++) {list.add (double baru (array [i])); } ARR ganda [] = {1131,333}; String str [] = {"dd", "aa", "bb", "cc", "ee"}; untuk (int j = 0; j <arr.length; j ++) {li.add (double baru (arr [j])); } Collections.copy (daftar, li); untuk (int i = 0; i <list.size (); i ++) {System.out.println ("Daftar [" + i + "] =" + list.get (i)); } // Hasil: 1131.333,23,456.2316) Mengembalikan elemen terkecil dalam koleksi (min)
Mengembalikan elemen terkecil dari koleksi yang diberikan sesuai dengan urutan di mana pembanding yang ditentukan dihasilkan. Semua elemen dalam koleksi harus dibandingkan satu sama lain melalui pembanding yang ditentukan
Collections.min (daftar) array ganda [] = {112, 111, 23, 456, 231}; Daftar Daftar = ArrayList baru (); untuk (int i = 0; i <array.length; i ++) {list.add (double baru (array [i])); } Collections.min (daftar); untuk (int i = 0; i <list.size (); i ++) {System.out.println ("Daftar [" + i + "] =" + list.get (i)); } // Hasil: 237) Mengembalikan elemen terkecil (maks) dalam koleksi
Mengembalikan elemen maksimum dari koleksi yang diberikan sesuai dengan urutan di mana pembanding yang ditentukan dihasilkan. Semua elemen dalam koleksi harus dibandingkan satu sama lain melalui pembanding yang ditentukan
Collections.max (daftar) array ganda [] = {112, 111, 23, 456, 231}; Daftar Daftar = ArrayList baru (); untuk (int i = 0; i <array.length; i ++) {list.add (double baru (array [i])); } Collections.max (daftar); untuk (int i = 0; i <list.size (); i ++) {System.out.println ("Daftar [" + i + "] =" + list.get (i)); } // Hasil: 4568) LastIndexOfSublist
Mengembalikan posisi awal dari daftar target yang ditentukan yang terakhir muncul dalam daftar sumber yang ditentukan
int count = collections.lastIndexOfsublist (daftar, li); array ganda [] = {112, 111, 23, 456, 231}; Daftar Daftar = ArrayList baru (); Daftar li = arraylist baru (); untuk (int i = 0; i <array.length; i ++) {list.add (double baru (array [i])); } ARR ganda [] = {111}; String str [] = {"dd", "aa", "bb", "cc", "ee"}; untuk (int j = 0; j <arr.length; j ++) {li.add (double baru (arr [j])); } Lokasi int = Koleksi. lastIndexOfSublist (Daftar, Li); System.out.println ("==="+ Lokasi); // Hasil 39) IndexOfSublist
Mengembalikan posisi awal pertama kali daftar target yang ditentukan muncul dalam daftar sumber yang ditentukan
int count = collections.IndexOfSublist (Daftar, Li); array ganda [] = {112, 111, 23, 456, 231}; Daftar Daftar = ArrayList baru (); Daftar li = arraylist baru (); untuk (int i = 0; i <array.length; i ++) {list.add (double baru (array [i])); } ARR ganda [] = {111}; String str [] = {"dd", "aa", "bb", "cc", "ee"}; untuk (int j = 0; j <arr.length; j ++) {li.add (double baru (arr [j])); } Int locations = collections.indexOfsublist (daftar, li); System.out.println ("==="+ Lokasi); // Hasil 110) Putar
Elemen Pindahkan Siklik Dalam daftar yang ditentukan berdasarkan jarak yang ditentukan
Collections.rotate (daftar, -1);
Jika itu adalah angka negatif, ia bergerak positif, dan jika bergerak positif, ia bergerak positif.
array ganda [] = {112, 111, 23, 456, 231}; Daftar Daftar = ArrayList baru (); untuk (int i = 0; i <array.length; i ++) {list.add (double baru (array [i])); } Collections.rotate (daftar, -1); untuk (int i = 0; i <list.size (); i ++) {System.out.println ("Daftar [" + i + "] =" + list.get (i)); } // Hasil: 111.23.456.231.112Artikel di atas secara singkat membahas koleksi kelas implementasi dan peta struktur data yang umum digunakan di Java. Ini semua konten yang telah saya bagikan dengan Anda. Saya harap Anda dapat memberi Anda referensi dan saya harap Anda dapat mendukung wulin.com lebih lanjut.