Secara singkat tentang hal utama - Java Collections Framework

Awal dari perjalanan

Hari ini saya ingin berbicara tentang topik menarik seperti “ Java Collections Framework ” atau, secara sederhana, tentang koleksi. Sebagian besar pekerjaan kode adalah memproses data dalam satu bentuk atau lainnya. Dapatkan daftar pengguna, dapatkan daftar alamat, dll. Entah bagaimana mengurutkannya, melakukan pencarian, membandingkannya. Inilah sebabnya mengapa pengetahuan tentang koleksi dianggap sebagai keterampilan inti. Itu sebabnya saya ingin membicarakannya. Selain itu, salah satu pertanyaan paling umum dalam wawancara pengembang Java adalah koleksi. Misalnya, "gambar hierarki koleksi". Kompiler online akan membantu kami dalam perjalanan. Misalnya, Anda dapat menggunakan " Tutorialspoint Online Java Compiler " atau Repl.it. Jalan untuk mengenal struktur data apa pun dimulai dengan variabel biasa (Variabel). Di situs Oracle, berbagai topik direpresentasikan sebagai "jalur" atau Jalur. Jadi, jalan untuk mengenal Java disebut dengan “ Jejak: Belajar Bahasa Java: Daftar Isi ”. Dan dasar-dasar bahasa (yaitu Dasar-Dasar Bahasa) dimulai dengan Variabel. Oleh karena itu, mari kita tulis kode sederhana:

public static void main(String[] args) {
	String user = "Max";
	System.out.println("Hello, " + user);
}

Itu bagus dalam segala hal, kecuali kami memahami bahwa kode ini bagus dan indah hanya untuk satu variabel. Apa yang harus dilakukan jika jumlahnya beberapa? Array diciptakan untuk menyimpan data dari satu jenis. Di Trail yang sama dari Oracle ada bagian terpisah yang didedikasikan untuk array. Bagian ini disebut: " Array ". Bekerja dengan array juga cukup sederhana:

import java.util.Arrays;
class Main {
  public static void main(String[] args) {
    String[] users = new String[2];
    users[0] = "Max";
    users[1] = "John";
    System.out.println("Hello, " + Arrays.toString(users));
  }
}

Array memecahkan masalah penyimpanan banyak nilai di satu tempat. Namun hal ini memberikan batasan: ukuran array adalah konstan. Jika seperti pada contoh kita mengatakan ukuran = 2, maka sama dengan dua. Itu saja. Jika kita menginginkan array yang lebih besar, kita perlu membuat instance baru. Selain itu, menemukan elemen juga merupakan hal yang rumit untuk sebuah array. Ada metodenya Arrays.binarySearch, tetapi pencarian ini hanya berfungsi pada array yang diurutkan (untuk array yang tidak disortir, hasilnya tidak ditentukan atau tidak dapat diprediksi). Artinya, pencarian akan mewajibkan kita untuk memilah setiap saat. Menghapus juga hanya menghapus nilainya. Oleh karena itu, kita masih belum mengetahui berapa banyak data sebenarnya yang ada di dalam array, kita hanya mengetahui berapa banyak sel yang ada di dalam array tersebut. Untuk menyegarkan pengetahuan Anda tentang array:

• " JavaRush: Array di Java "
• " Tutorial Java: Array "

Dan sebagai konsekuensi dari perkembangan bahasa Java, Java Collections Framework muncul di JDK 1.2, yang akan kita bicarakan hari ini.

Koleksi

Mulailah menentukan biaya dari awal. Mengapa Koleksi? Istilah itu sendiri berasal dari hal-hal seperti "Teori Tipe" dan "Tipe Data Abstrak". Tetapi jika Anda tidak melihat hal-hal yang tinggi, maka ketika kita memiliki beberapa hal, kita dapat menyebutnya sebagai “kumpulan barang”. Mereka yang mengumpulkan barang. Secara umum kata mengumpulkan sendiri berasal dari bahasa Lat. collectiono "mengumpulkan, mengumpulkan." Artinya, koleksi adalah kumpulan sesuatu, wadah bagi beberapa unsur. Jadi kami memiliki kumpulan elemen. Apa yang mungkin ingin kami lakukan dengannya: Seperti yang Anda lihat, kita mungkin menginginkan hal-hal yang cukup logis. Kami juga memahami bahwa kami mungkin ingin melakukan sesuatu dengan banyak koleksi: Oleh karena itu, pengembang Java menulis antarmuka java.util.Collection untuk menggambarkan perilaku umum ini untuk semua koleksi . Antarmuka Koleksi adalah tempat semua koleksi berasal. Koleksi adalah sebuah ide, ini adalah ide tentang bagaimana semua koleksi harus berperilaku. Oleh karena itu, istilah "Koleksi" dinyatakan sebagai antarmuka. Tentu saja, sebuah antarmuka memerlukan implementasi. Antarmuka java.util.Collectionmemiliki kelas abstrak AbstractCollection, yaitu beberapa "kumpulan abstrak", yang mewakili kerangka untuk implementasi lain (seperti yang tertulis di JavaDoc di atas kelas java.util.AbstractCollection). Berbicara tentang koleksi, mari kita kembali dan ingat bahwa kita ingin mengulanginya. Artinya kita ingin mengulangi elemen satu per satu. Ini adalah konsep yang sangat penting. Oleh karena itu, antarmuka Collectiondiwarisi dari Iterable. Ini sangat penting karena... pertama, semua Iterable harus bisa mengembalikan Iterator berdasarkan isinya. Dan kedua, segala sesuatu yang Iterable dapat digunakan dalam loops for-each-loop. Dan dengan bantuan sebuah iterator AbstractCollectionmetode seperti contains, toArray, diimplementasikan remove. Dan jalur untuk memahami kumpulan dimulai dengan salah satu struktur data yang paling umum - daftar, yaitu. List.

Daftar

Jadi, daftar menempati tempat penting dalam hierarki koleksi: Seperti yang bisa kita lihat, daftar mengimplementasikan antarmuka java.util.List . Daftar mengungkapkan bahwa kita mempunyai kumpulan elemen yang disusun dalam beberapa urutan satu demi satu. Setiap elemen memiliki indeks (seperti dalam array). Biasanya, daftar memungkinkan Anda memiliki elemen dengan nilai yang sama. Seperti yang kami katakan di atas, Listia mengetahui tentang indeks elemen. Hal ini memungkinkan Anda untuk mendapatkan ( get) elemen berdasarkan indeks atau menetapkan nilai untuk indeks tertentu ( set). Metode pengumpulan add, addAll, removememungkinkan Anda menentukan indeks untuk mengeksekusinya. Selain itu, y Listmemiliki versi iteratornya sendiri yang disebut ListIterator. Iterator ini mengetahui tentang indeks elemen, sehingga dapat melakukan iterasi tidak hanya ke depan, tetapi juga ke belakang. Bahkan dapat dibuat dari tempat tertentu dalam koleksi. Di antara semua implementasi, ada dua yang paling umum digunakan: ArrayListdan LinkedList. Pertama, ArrayListini adalah daftar ( List) berdasarkan array ( Array). Hal ini memungkinkan Anda untuk mencapai "Akses Acak" ke elemen. Akses acak adalah kemampuan untuk segera mengambil elemen berdasarkan indeks, daripada mengulangi semua elemen hingga kita menemukan elemen dengan indeks yang diinginkan. Ini adalah susunan sebagai dasar yang memungkinkan hal ini dicapai. Sebaliknya, LinkedListini adalah Daftar Tertaut. Setiap entri dalam daftar tertaut direpresentasikan dalam bentuk Entry, yang menyimpan data itu sendiri, serta tautan ke berikutnya (berikutnya) dan sebelumnya (sebelumnya) Entry. Dengan demikian LinkedListmengimplementasikan "Akses Berurutan " . Jelas bahwa untuk menemukan elemen ke-5 kita harus beralih dari elemen pertama ke elemen terakhir, karena kami tidak memiliki akses langsung ke elemen kelima. Kami hanya dapat mengaksesnya dari elemen ke-4. Perbedaan konsep mereka diberikan di bawah ini: Dalam pekerjaan, seperti yang Anda pahami, ada juga perbedaan. Misalnya menambahkan elemen. Elemen - LinkedListelemen tersebut terhubung secara sederhana seperti mata rantai dalam sebuah rantai. Tapi ArrayListitu menyimpan elemen dalam array. Dan sebuah array, seperti yang kita ketahui, tidak dapat mengubah ukurannya. Lalu bagaimana cara kerjanya ArrayList? Dan cara kerjanya sangat sederhana. Ketika ruang dalam array habis, itu bertambah 1,5 kali lipat. Berikut ini kode zoomnya: int newCapacity = oldCapacity + (oldCapacity >> 1); Perbedaan lain dalam pengoperasiannya adalah offset elemen. Misalnya saat menambah atau menghapus elemen di tengah. Untuk menghapus dari LinkedListsuatu elemen, cukup hapus referensi ke elemen ini. Dalam kasus , ArrayListkita terpaksa menggeser elemen setiap kali menggunakan System.arraycopy. Jadi, semakin banyak elemen, semakin banyak tindakan yang harus dilakukan. Penjelasan lebih rinci dapat ditemukan di artikel berikut:

• " Struktur data dalam gambar. ArrayList "
• " Struktur data dalam gambar. LinkedList "
• " Apa yang ada di balik terpal LinkedList? "

Setelah memeriksa ArrayList, kita pasti ingat “pendahulunya”, kelas java.util.Vector . Berbeda Vectordengan ArrayListmetode untuk bekerja dengan koleksi (menambah, menghapus, dll.) yang disinkronkan. Artinya, jika salah satu thread ( Thread) menambahkan elemen, maka thread lainnya akan menunggu hingga thread pertama menyelesaikan pekerjaannya. Karena keamanan thread seringkali tidak diperlukan, disarankan untuk menggunakan kelas dalam kasus seperti itu ArrayList, seperti yang dinyatakan secara eksplisit dalam JavaDoc untuk kelas tersebut Vector. Selain itu, Vectorukurannya bertambah bukan 1,5 kali lipat, ArrayListtetapi 2 kali lipat. Jika tidak, perilakunya sama - Vectorpenyimpanan elemen dalam bentuk array disembunyikan dan penambahan/penghapusan elemen memiliki konsekuensi yang sama seperti pada ArrayList. Faktanya, Vectorkami mengingat ini karena suatu alasan. Jika kita melihat di Javadoc, kita akan melihat di "Subkelas Langsung yang Diketahui" struktur seperti java.util.Stack . Tumpukan adalah struktur menarik yang merupakan last-in-first-outstruktur LIFO (masuk terakhir, keluar pertama). Stack yang diterjemahkan dari bahasa Inggris adalah stack (seperti tumpukan buku misalnya). Tumpukan mengimplementasikan metode tambahan: peek(lihat, lihat), pop(dorong), push(dorong). Metode ini peekditerjemahkan sebagai melihat (misalnya, mengintip ke dalam tas diterjemahkan sebagai “ melihat ke dalam tas ”, dan mengintip melalui lubang kunci diterjemahkan sebagai “ mengintip melalui lubang kunci ”). Metode ini memungkinkan Anda untuk melihat "bagian atas" tumpukan, mis. dapatkan elemen terakhir tanpa menghapus (yaitu tanpa menghapus) dari tumpukan. Metode ini pushmendorong (menambahkan) elemen baru ke dalam tumpukan dan mengembalikannya, dan metode elemen popmendorong (menghapus) dan mengembalikan elemen yang dihapus. Dalam ketiga kasus (yaitu mengintip, pop dan push), kami hanya bekerja dengan elemen terakhir (yaitu “bagian atas tumpukan”). Ini adalah fitur utama dari struktur tumpukan. Omong-omong, ada tugas menarik untuk memahami tumpukan, yang dijelaskan dalam buku "Karir Seorang Programmer" (Cracking Coding Interview). Ada tugas menarik di mana, dengan menggunakan struktur "tumpukan" (LIFO), Anda perlu mengimplementasikan "antrian" ” struktur (FIFO). Seharusnya terlihat seperti ini: Analisis tugas ini dapat ditemukan di sini: " Implementasi Antrean Menggunakan Tumpukan - ADT Antrean ("Implementasikan Antrean Menggunakan Tumpukan" pada LeetCode) ". Jadi kami dengan lancar beralih ke struktur data baru - antrian.

Antre

Antrian adalah struktur yang kita kenal dari kehidupan. Antrian ke toko, ke dokter. Siapapun yang datang lebih dulu (First In) akan menjadi orang pertama yang keluar dari antrian (First Out). Di Java, antrian diwakili oleh antarmuka java.util.Queue . Menurut Javadoc antrian, antrian menambahkan metode berikut: Seperti yang Anda lihat, ada metode pemesanan (kegagalan menjalankannya penuh dengan pengecualian) dan ada metode permintaan (ketidakmampuan untuk menjalankannya tidak menyebabkan kesalahan). Dimungkinkan juga untuk mendapatkan elemen tanpa menghapusnya (mengintip atau elemen). Antarmuka antrian juga memiliki penerus yang berguna - Deque . Inilah yang disebut "antrian dua arah". Artinya, antrian seperti itu memungkinkan Anda untuk menggunakan struktur ini baik dari awal maupun dari akhir. Dokumentasi mengatakan bahwa "Deques juga dapat digunakan sebagai tumpukan LIFO (Last-In-First-Out). Antarmuka ini harus digunakan sebagai preferensi terhadap kelas Stack lama.", yaitu, disarankan untuk menggunakan implementasi Deque daripada menggunakan Tumpukan. Javadoc menunjukkan metode apa yang dijelaskan oleh antarmuka Deque: Mari kita lihat implementasi apa saja yang ada. Dan kita akan melihat fakta menarik - LinkedList telah masuk ke dalam kamp antrian) Artinya, LinkedList mengimplementasikan keduanya List, dan Deque. Namun ada juga yang “antrian saja”, misalnya PriorityQueue. Dia tidak sering diingat, tapi sia-sia. Pertama, Anda tidak dapat menggunakan "objek yang tidak dapat dibandingkan" dalam antrian ini, mis. baik Pembanding harus ditentukan atau semua objek harus sebanding. Kedua, "implementasi ini menyediakan waktu O(log(n)) untuk metode enqueuing dan dequeuing". Kompleksitas logaritma ada karena suatu alasan. Menerapkan PriorityQueue berdasarkan heap. Javadoc mengatakan: "Antrian prioritas direpresentasikan sebagai tumpukan biner yang seimbang". Penyimpanannya sendiri untuk ini adalah array biasa. Yang tumbuh bila diperlukan. Jika tumpukannya kecil, maka akan bertambah 2 kali lipat. Dan kemudian sebesar 50%. Komentar dari kode: "Ukuran ganda jika kecil; jika tidak, tumbuh sebesar 50%". Antrean prioritas dan Binary Heap adalah topik terpisah. Jadi untuk informasi lebih lanjut:

• Artikel super tentang Habré: " Struktur data. Panduan informal "
• Penjelasan yang jelas tentang "heap": " Foxford: Ilmu Komputer. Struktur data: Heap "
• Artikel dari Habr tentang Binary Heap: " Struktur data: heap biner "
• " Pengantar Tumpukan Biner (MaxHeaps) "

Sebagai implementasinya, java.util.DequeAnda dapat menggunakan kelas java.util.ArrayDeque . Artinya, daftar dapat diimplementasikan menggunakan daftar tertaut dan array, dan antrian juga dapat diimplementasikan menggunakan array atau menggunakan daftar tertaut. Antarmuka Queueand Dequememiliki turunan yang mewakili "antrian pemblokiran": BlockingQueuedan BlockingDeque. Berikut perubahan antarmuka dibandingkan antrian biasa: Mari kita lihat beberapa contoh pemblokiran antrian. Tapi mereka menarik. Misalnya, BlockingQueue diimplementasikan oleh: PriorityBlockingQueue , SynchronousQueue , ArrayBlockingQueue, DelayQueue , LinkedBlockingQueue . Namun BlockingDequemereka mengimplementasikan semuanya mulai dari Collection Frameworks standar LinkedBlockingDeque. Setiap antrian adalah topik tinjauan terpisah. Dan dalam kerangka ulasan ini, kami akan menggambarkan hierarki kelas tidak hanya dengan List, tetapi juga dengan Queue: Seperti yang dapat kita lihat dari diagram, antarmuka dan kelas Java Collections Framework sangat saling terkait. Mari tambahkan cabang hierarki lainnya - Set.

Mengatur

Set— diterjemahkan sebagai “set.” Ini berbeda dari antrian dan daftar Setdalam abstraksinya yang lebih besar terhadap penyimpanan elemen. Set- seperti sekantong benda, yang tidak diketahui bagaimana letak benda tersebut dan bagaimana letaknya. Di Java, himpunan seperti itu diwakili oleh antarmuka java.util.Set . Seperti yang tertulis dalam dokumentasi, Setini adalah "koleksi yang tidak mengandung elemen duplikat". Menariknya, antarmuka itu sendiri Settidak menambahkan metode baru ke antarmuka Collection, tetapi hanya memperjelas persyaratan (tentang apa yang tidak boleh mengandung duplikat). Selain itu, dari uraian sebelumnya dapat disimpulkan bahwa Anda tidak bisa Setmendapatkan elemen begitu saja darinya. Iterator digunakan untuk mendapatkan elemen. Setmemiliki beberapa antarmuka lagi yang terkait dengannya. Yang pertama adalah SortedSet. Seperti namanya, SortedSetini menunjukkan bahwa kumpulan tersebut diurutkan, dan oleh karena itu elemen-elemennya mengimplementasikan antarmuka Comparableatau ditentukan Comparator. Selain itu, SortedSetia menawarkan beberapa metode menarik: Selain itu, ada metode first(elemen terkecil berdasarkan nilai) dan last(elemen terbesar berdasarkan nilai). Ada SortedSetahli waris - NavigableSet. Tujuan antarmuka ini adalah untuk menjelaskan metode navigasi yang diperlukan agar lebih akurat mengidentifikasi elemen yang sesuai. Hal yang menarik adalah NavigableSetia menambahkan iterator biasa (yang dimulai dari terkecil ke terbesar) sebuah iterator untuk urutan terbalik - descendingIterator. Selain itu, NavigableSetini memungkinkan Anda menggunakan metode descendingSetuntuk mendapatkan tampilan diri Anda (View), di mana elemen-elemennya berada dalam urutan terbalik. Disebut demikian Viewkarena melalui elemen yang dihasilkan Anda dapat mengubah elemen aslinya Set. Artinya, pada hakikatnya merupakan representasi data asli dengan cara yang berbeda, dan bukan salinannya. Menariknya, NavigableSet, seperti Queue, dapat menangani elemen pollFirst(minimal) dan pollLast(maksimal). Artinya, ia mendapatkan elemen ini dan menghapusnya dari himpunan. Implementasi seperti apa yang ada? Pertama, implementasi paling terkenal didasarkan pada kode hash - HashSet . Implementasi lain yang sama terkenalnya didasarkan pada pohon merah-hitam - TreeSet . Mari lengkapi diagram kita: Dalam koleksinya, masih memilah hierarki - para pertapa. Yang pada pandangan pertama berdiri di samping - java.util.Map.

Peta

Peta adalah struktur data di mana data disimpan berdasarkan kunci. Misalnya, kuncinya bisa berupa tanda pengenal atau kode kota. Dan dengan kunci inilah data akan dicari. Menariknya, kartu-kartu tersebut ditampilkan secara terpisah. Menurut pengembang (lihat " FAQ Desain API Koleksi Java "), pemetaan nilai kunci bukanlah sebuah koleksi. Dan peta dapat lebih cepat dianggap sebagai kumpulan kunci, kumpulan nilai, kumpulan pasangan nilai kunci. Ini adalah binatang yang sangat menarik. Metode apa yang disediakan kartu? Mari kita lihat antarmuka Java API java.util.Map . Karena Karena peta bukan koleksi (tidak mewarisi Koleksi), peta tidak berisi file contains. Dan ini logis. Peta terdiri dari kunci dan nilai. Manakah dari metode berikut yang harus diperiksa containsdan bagaimana agar tidak bingung? Oleh karena itu, antarmuka Mapmemiliki dua versi berbeda: containsKey(berisi kunci) dan containsValue(berisi nilai). Menggunakannya keySetmemungkinkan Anda mendapatkan satu set kunci (yang sama Set). Dan dengan menggunakan metode tersebut valueskita bisa mendapatkan kumpulan nilai di peta. Kunci dalam peta bersifat unik, yang ditekankan oleh struktur datanya Set. Nilai dapat diulang, yang ditekankan oleh struktur data Koleksi. Selain itu, dengan menggunakan metode ini entrySetkita dapat memperoleh sekumpulan pasangan nilai kunci. Anda dapat membaca lebih lanjut tentang implementasi kartu apa saja yang ada dalam analisis paling mendetail:

• " Struktur data dalam gambar. HashMap "
• " Struktur data dalam gambar. LinkedHashMap "
• " Cara kerja HashMap di Java (pembaruan untuk Java 8) "

Saya juga ingin melihat apa yang HashMapsangat mirip dengan HashSet, TreeMapdan TreeSet. Mereka bahkan memiliki antarmuka yang serupa: NavigableSetdan NavigableMap, SortedSetdan SortedMap. Jadi peta akhir kita akan terlihat seperti ini: Kita dapat mengakhiri dengan fakta menarik bahwa koleksi tersebut Setmenggunakan secara internal Map, di mana nilai tambah adalah kunci, dan nilainya sama di semua tempat. Hal ini menarik karena Mapbukan collection and return Setyang merupakan koleksi tetapi sebenarnya diimplementasikan sebagai Map. Agak tidak nyata, tapi itulah yang terjadi)

Kesimpulan

Kabar baiknya adalah ini mengakhiri ulasan ini. Kabar buruknya adalah ini adalah artikel yang sangat review. Setiap implementasi dari setiap koleksi memerlukan artikel terpisah, dan juga untuk setiap algoritma yang tersembunyi dari pandangan kita. Namun tujuan dari tinjauan ini adalah untuk mengingat apa itu dan apa hubungan antar antarmuka. Saya berharap setelah membaca dengan seksama Anda akan dapat menggambar diagram koleksi dari ingatan. Seperti biasa, beberapa link:

• " Jejak Oracle: Koleksi "
• " Tutorial IBM: Koleksi Java "
• " Yuri Tkach: Java Tingkat Lanjut - Koleksi "
• " Koleksi Java: Kekuatan yang Bangkit oleh Raoul-Gabriel Urma dan Richard Warburton "
• " Timur Batyrshinov: 22 - Dasar-dasar java. Koleksi (dan video berikut dari PlayList) "
• " Lima Hal yang Tidak Anda Ketahui Tentang... Java Collections API "

#Viacheslav