Saya sering menemukan pertanyaan seperti itu selama wawancara di masa lalu. Sayangnya, saya malu, fondasinya terlalu buruk, tidak ada cara, saya merasa dirugikan
Sekarang kita harus berbicara tentang perbedaan dan koneksi antara ketiganya: Ketiganya menerapkan antarmuka daftar, semua memiliki metode yang didefinisikan dalam antarmuka daftar, dan juga memiliki metode antarmuka koleksi;
ArrayList: Menggunakan metode array untuk menyimpan data, kueri dan kecepatan modifikasi cepat, tetapi kecepatan penambahan dan penghapusannya lambat;
LinkedList: Menggunakan metode daftar tertaut untuk menyimpan data, kecepatan kueri dan modifikasi lambat, tetapi kecepatan penambahan dan penghapusan cepat.
Vektor juga menggunakan array untuk penyimpanan. Iterator, Pencacahan, Get (INT INDEX), dan INDEXOF (INT INDEX), tetapi ArrayList tidak memiliki enumerasi
ArrayList dan Vector menggunakan array untuk menyimpan data. Operasi, data indeks dengan cepat dimasukkan. Atau traversal mundur, tetapi hanya item ini yang diperlukan saat memasukkan data.
Tabel linier, daftar tertaut, dan tabel hash biasanya digunakan struktur data. 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 │ └ vektor │ └Stack └SetMap ├Hashtable ├HashMap └WeakHashMap
Antarmuka koleksi
Koleksi adalah antarmuka koleksi paling dasar. 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.
Semua kelas yang mengimplementasikan antarmuka koleksi harus menyediakan dua konstruktor standar: konstruktor tanpa parameter digunakan untuk membuat koleksi kosong, dan ada konstruktor parameter koleksi digunakan untuk membuat koleksi baru, koleksi dan lulus baru ini. elemen yang sama. 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 itu = collection.iterator ();
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 antarmuka koleksi yang diperlukan, Daftar juga menyediakan metode ListIterator (), yang mengembalikan antarmuka ListIterator. Hapus, atur elemen, dan juga dapat 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 tambahan, lepas, masukkan metode 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. Iterator yang dibuat oleh vektor, meskipun iterator yang dibuat oleh ArrayList, 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) pada saat ini, ConcurrentModificationException akan dilemparkan ketika metode iterator dipanggil, sehingga pengecualian harus ditangkap.
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, 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.
Kelas hashtable
Hashtable mewarisi antarmuka peta dan mengimplementasikan tabel hash dengan pemetaan nilai kunci. Objek non-nol dapat digunakan sebagai kunci atau nilai.
Gunakan put (kunci, nilai) untuk menambahkan data, gunakan GET (kunci) untuk mengambil data.
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. HashCode dan Equals Metode mewarisi dari objek kelas root. ) = Kode hash mereka harus sama, tetapi jika kedua objeknya berbeda, kode hash mereka mungkin tidak berbeda. Operasi 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). saat yang sama.
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
Lemarihashmap adalah hashmap yang ditingkatkan yang mengimplementasikan "referensi lemah" ke kunci.
Meringkaskan
Jika tumpukan, antrian dan operasi lain terlibat, Anda harus mempertimbangkan untuk menggunakan daftar.
Jika program ini berada di lingkungan satu utamanya, atau akses hanya ada di satu utas, mempertimbangkan kelas asinkron, itu lebih efisien.
Berikan perhatian khusus pada pengoperasian tabel hash.
Cobalah untuk mengembalikan antarmuka alih -alih jenis yang sebenarnya, seperti mengembalikan daftar alih -alih daftar array. Ini untuk pemrograman abstrak.
Sinkronisasi
Vektor sinkron. Beberapa metode di kelas ini memastikan bahwa objek di vektor aman-aman. ArrayList tidak sinkron, sehingga objek di ArrayList tidak aman-aman. Karena persyaratan sinkronisasi akan memengaruhi efisiensi eksekusi, menggunakan ArrayList adalah pilihan yang baik jika Anda tidak memerlukan koleksi yang aman, yang dapat menghindari overhead kinerja yang tidak perlu karena sinkronisasi.
Pertumbuhan data
Dari mekanisme implementasi internal, arraylist dan vektor keduanya menggunakan array (array) untuk mengontrol objek dalam koleksi. Ketika Anda menambahkan elemen pada kedua jenis ini, jika jumlah elemen melebihi panjang array internal saat ini, mereka perlu memperluas panjang array internal Asli 50% dari itu, jadi terakhir kali Anda mendapatkan koleksi ini akan selalu mengambil lebih banyak ruang daripada yang sebenarnya Anda butuhkan. Jadi, jika Anda ingin menyimpan banyak data dalam koleksi maka ada beberapa keuntungan menggunakan vektor, karena Anda dapat menghindari overhead sumber daya yang tidak perlu dengan mengatur ukuran inisialisasi koleksi.
Mode Penggunaan
Di ArrayList dan Vector, dibutuhkan waktu yang sama untuk menemukan data dari lokasi yang ditentukan (melalui indeks) atau untuk menambah dan menghapus elemen di akhir set. Namun, jika elemen ditambahkan atau dihapus di tempat lain dalam set, waktu yang dihabiskan akan tumbuh secara linear: o (ni), di mana n mewakili jumlah elemen dalam set, dan saya mewakili posisi indeks di mana elemen meningkatkan atau menghapus elemen. Mengapa ini terjadi? Diperkirakan bahwa ketika melakukan operasi di atas, semua elemen setelah elemen i-th dan i-th dalam set harus melakukan operasi perpindahan. Apa artinya semua ini?
Ini berarti bahwa Anda hanya mencari elemen dalam posisi tertentu atau hanya menambah dan menghapus elemen di akhir koleksi, kemudian menggunakan vektor atau daftar array tidak apa -apa. Jika ini adalah operasi lain, Anda sebaiknya memilih kelas operasi pengumpulan lainnya. Misalnya, waktu yang dibutuhkan untuk kelas pengumpulan LinkList untuk menambah atau menghapus elemen pada posisi apa pun dalam koleksi adalah sama? adalah lokasi indeks. LinkList juga akan membuat objek untuk setiap elemen yang dimasukkan, dan semua yang perlu Anda pahami juga akan membawa overhead tambahan.
Akhirnya, dalam buku Java Praktis, Peter Haggar menyarankan menggunakan array sederhana (array) alih -alih vektor atau arraylist. Ini terutama berlaku untuk program dengan efisiensi eksekusi tinggi. Karena menggunakan array (array) menghindari sinkronisasi, panggilan metode tambahan dan realokasi operasi ruang yang tidak perlu.