Secara ringkas tentang perkara utama - Rangka Kerja Koleksi Java

Permulaan jalan

Hari ini saya ingin bercakap tentang topik yang menarik seperti " Rangka Kerja Koleksi Java " atau, secara ringkas, mengenai koleksi. Kebanyakan kerja kod memproses data dalam satu bentuk atau yang lain. Dapatkan senarai pengguna, dapatkan senarai alamat, dsb. Entah bagaimana menyusunnya, melakukan carian, membandingkannya. Itulah sebabnya pengetahuan tentang koleksi dianggap sebagai kemahiran teras. Itulah sebabnya saya ingin bercakap mengenainya. Di samping itu, salah satu soalan yang paling biasa dalam temu bual pembangun Java ialah koleksi. Contohnya, "lukiskan hierarki koleksi." Penyusun dalam talian akan membantu kami dalam perjalanan. Sebagai contoh, anda boleh menggunakan " Tutorialspoint Online Java Compiler " atau Repl.it. Laluan untuk mengenali mana-mana struktur data bermula dengan pembolehubah biasa (Pembolehubah). Di laman web Oracle, pelbagai topik diwakili sebagai "laluan" atau Jejak. Jadi, laluan untuk mengenali Java dipanggil " Jejak: Belajar Bahasa Jawa: Jadual Kandungan ". Dan asas bahasa (iaitu Asas Bahasa) bermula dengan Pembolehubah. Oleh itu, mari kita tulis kod mudah:

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

Ia bagus dalam segala-galanya, kecuali kita faham bahawa kod ini bagus dan cantik hanya untuk satu pembolehubah. Apa yang perlu dilakukan jika terdapat beberapa daripadanya? Tatasusunan dicipta untuk menyimpan data satu jenis. Dalam Jejak yang sama dari Oracle terdapat bahagian berasingan khusus untuk tatasusunan. Bahagian ini dipanggil: " Tatasusunan ". Bekerja dengan tatasusunan juga agak mudah:

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));
  }
}

Tatasusunan menyelesaikan masalah menyimpan berbilang nilai di satu tempat. Tetapi ia mengenakan had: saiz tatasusunan adalah malar. Jika, seperti dalam contoh, kita mengatakan bahawa saiz = 2, maka ia sama dengan dua. Itu sahaja. Jika kita mahukan tatasusunan yang lebih besar, kita perlu mencipta contoh baharu. Selain itu, mencari elemen juga merupakan perkara yang rumit untuk tatasusunan. Terdapat kaedah Arrays.binarySearch, tetapi carian ini hanya berfungsi pada tatasusunan yang diisih (untuk tatasusunan yang tidak diisih, hasilnya tidak ditentukan atau tidak dapat diramalkan). Maksudnya, carian akan mewajibkan kita menyusun setiap kali. Pemadaman juga hanya mengosongkan nilai. Oleh itu, kami masih tidak tahu berapa banyak data sebenarnya dalam tatasusunan, kami hanya tahu berapa banyak sel dalam tatasusunan. Untuk menyegarkan pengetahuan anda tentang tatasusunan:

• " JavaRush: Tatasusunan dalam Java "
• " Tutorial Java: Tatasusunan "

Dan sebagai akibat daripada pembangunan bahasa Java, Rangka Kerja Koleksi Java muncul dalam JDK 1.2, yang akan kita bincangkan hari ini.

Koleksi

Mulakan kos dari awal lagi. Mengapa Koleksi? Istilah itu sendiri berasal daripada perkara seperti "Teori Jenis" dan "Jenis Data Abstrak". Tetapi jika anda tidak melihat apa-apa perkara yang tinggi, maka apabila kita mempunyai beberapa perkara, kita boleh memanggilnya sebagai "koleksi perkara." Mereka yang mengumpul barang. Secara umumnya, perkataan collect sendiri berasal daripada Lat. collectio "berkumpul, mengumpul." Maksudnya, koleksi ialah himpunan sesuatu, bekas untuk beberapa unsur. Jadi kami mempunyai koleksi elemen. Perkara yang mungkin kita mahu lakukan dengannya: Seperti yang anda lihat, kami mungkin mahukan perkara yang agak logik. Kami juga memahami bahawa kami mungkin ingin melakukan sesuatu dengan berbilang koleksi: Sehubungan itu, pembangun Java menulis antara muka java.util.Collection untuk menerangkan tingkah laku umum ini untuk semua koleksi . Antara muka Koleksi ialah tempat asal semua koleksi. Koleksi adalah idea, ia adalah idea tentang bagaimana semua koleksi harus berkelakuan. Oleh itu, istilah "Koleksi" dinyatakan sebagai antara muka. Sememangnya, antara muka memerlukan pelaksanaan. Antara muka java.util.Collectionmempunyai kelas abstrak AbstractCollection, iaitu, beberapa "koleksi abstrak", yang mewakili rangka untuk pelaksanaan lain (seperti yang ditulis dalam JavaDoc di atas kelas java.util.AbstractCollection). Bercakap tentang koleksi, mari kita kembali dan ingat bahawa kita mahu mengulanginya. Ini bermakna kita ingin mengulangi elemen satu demi satu. Ini adalah konsep yang sangat penting. Oleh itu, antara muka Collectiondiwarisi daripada Iterable. Ini sangat penting kerana... pertama, semua Iterable mesti dapat mengembalikan Iterator berdasarkan kandungannya. Dan kedua, semua yang boleh Iterable boleh digunakan dalam gelung for-each-loop. Dan dengan bantuan iterator AbstractCollectionkaedah seperti contains, toArray, dilaksanakan remove. Dan laluan untuk memahami koleksi bermula dengan salah satu struktur data yang paling biasa - senarai, i.e. List.

Senarai

Jadi, senarai menduduki tempat penting dalam hierarki koleksi: Seperti yang kita lihat, senarai melaksanakan antara muka java.util.List . Senarai menyatakan bahawa kita mempunyai koleksi elemen yang disusun dalam beberapa urutan satu demi satu. Setiap elemen mempunyai indeks (seperti dalam tatasusunan). Biasanya, senarai membolehkan anda mempunyai elemen dengan nilai yang sama. Seperti yang kami katakan di atas, Listia tahu tentang indeks elemen. Ini membolehkan anda mendapatkan ( get) elemen mengikut indeks atau menetapkan nilai untuk indeks tertentu ( set). Kaedah pengumpulan add, addAll, removemembolehkan anda menentukan indeks untuk melaksanakannya. Selain itu, y Listmempunyai versi iteratornya sendiri yang dipanggil ListIterator. Iterator ini mengetahui tentang indeks elemen, jadi ia boleh melelakan bukan sahaja ke hadapan, tetapi juga ke belakang. Ia juga boleh dibuat dari tempat tertentu dalam koleksi. Di antara semua pelaksanaan, terdapat dua yang paling biasa digunakan: ArrayListdan LinkedList. Pertama, ArrayListia adalah senarai ( List) berdasarkan tatasusunan ( Array). Ini membolehkan anda mencapai "Akses Rawak" kepada elemen. Akses rawak ialah keupayaan untuk mendapatkan semula elemen mengikut indeks dengan segera, dan bukannya melalui semua elemen sehingga kami menemui elemen dengan indeks yang dikehendaki. Ia adalah tatasusunan sebagai asas yang membolehkan ini dicapai. Sebaliknya, LinkedListia adalah Senarai Berpaut. Setiap entri dalam senarai terpaut diwakili dalam borang Entry, yang menyimpan data itu sendiri, serta pautan ke seterusnya (seterusnya) dan sebelumnya (sebelumnya) Entry. Oleh itu LinkedListmelaksanakan "Akses Berurutan " . Adalah jelas bahawa untuk mencari elemen ke-5 kita perlu pergi dari elemen pertama ke yang terakhir, kerana kami tidak mempunyai akses langsung kepada elemen kelima. Kami hanya boleh mengaksesnya dari elemen ke-4. Perbezaan dalam konsep mereka diberikan di bawah: Dalam kerja, seperti yang anda faham, terdapat juga perbezaan. Sebagai contoh, menambah elemen. Unsur-unsur tersebut LinkedListhanya disambungkan seperti pautan dalam rantai. Tetapi ArrayListia menyimpan elemen dalam tatasusunan. Dan tatasusunan, seperti yang kita ketahui, tidak boleh mengubah saiznya. Bagaimanakah ia berfungsi kemudian ArrayList? Dan ia berfungsi dengan sangat mudah. Apabila ruang dalam tatasusunan kehabisan, ia meningkat sebanyak 1.5 kali ganda. Berikut ialah kod zum: int newCapacity = oldCapacity + (oldCapacity >> 1); Satu lagi perbezaan dalam operasi ialah sebarang anjakan elemen. Sebagai contoh, apabila menambah atau mengalih keluar elemen ke tengah. Untuk mengalih keluar daripada LinkedListelemen, hanya alih keluar rujukan kepada elemen ini. Dalam kes , ArrayListkami terpaksa mengalihkan elemen setiap kali menggunakan System.arraycopy. Oleh itu, lebih banyak elemen, lebih banyak tindakan perlu dilakukan. Penerangan yang lebih terperinci boleh didapati dalam artikel ini:

• " Struktur data dalam gambar. ArrayList "
• " Struktur data dalam gambar. LinkedList "
• " Apa yang ada di bawah hud LinkedList? "

Setelah meneliti ArrayList, seseorang tidak boleh tidak mengingati "pendahulunya", kelas java.util.Vector . Ia berbeza Vectorkerana ArrayListkaedah untuk bekerja dengan koleksi (menambah, memadam, dll.) disegerakkan. Iaitu, jika satu utas ( Thread) menambah elemen, maka utas lain akan menunggu sehingga utas pertama menyelesaikan kerjanya. Oleh kerana keselamatan benang selalunya tidak diperlukan, adalah disyorkan untuk menggunakan kelas dalam kes sedemikian ArrayList, seperti yang dinyatakan secara eksplisit dalam JavaDoc untuk kelas tersebut Vector. Di samping itu, Vectoria meningkatkan saiznya bukan sebanyak 1.5 kali, ArrayListtetapi sebanyak 2 kali. Jika tidak, tingkah laku adalah sama - Vectorpenyimpanan elemen dalam bentuk tatasusunan disembunyikan dan menambah/mengalih keluar elemen mempunyai akibat yang sama seperti dalam ArrayList. Sebenarnya, Vectorkami mengingati ini kerana suatu sebab. Jika kita melihat dalam Javadoc, kita akan melihat dalam "Subkelas Dikenali Langsung" struktur seperti java.util.Stack . Tindanan ialah struktur yang menarik iaitu last-in-first-outstruktur LIFO (masuk terakhir, keluar dahulu). Tindanan yang diterjemahkan daripada bahasa Inggeris ialah timbunan (seperti timbunan buku, contohnya). Tindanan melaksanakan kaedah tambahan: peek(lihat, lihat), pop(tolak), push(tolak). Kaedah ini peekditerjemahkan sebagai lihat (contohnya, jenguk ke dalam beg diterjemahkan sebagai " lihat ke dalam beg ", dan jenguk melalui lubang kunci diterjemahkan sebagai " jenguk melalui lubang kunci "). Kaedah ini membolehkan anda melihat "atas" timbunan, i.e. dapatkan elemen terakhir tanpa mengalih keluar (iaitu tanpa mengalihkannya) daripada timbunan. Kaedah pushmenolak (menambah) elemen baharu ke dalam timbunan dan mengembalikannya, dan kaedah elemen popmenolak (mengalih keluar) dan mengembalikan elemen yang dikeluarkan. Dalam ketiga-tiga kes (iaitu mengintip, pop dan tolak), kami hanya berfungsi dengan elemen terakhir (iaitu "bahagian atas timbunan"). Ini adalah ciri utama struktur tindanan. Ngomong-ngomong, terdapat tugas yang menarik untuk memahami tindanan, yang diterangkan dalam buku "A Programmer's Career" (Cracking Coding Interview). Terdapat tugas yang menarik di mana menggunakan struktur "stack" (LIFO) anda perlu melaksanakan "queue". ” struktur (FIFO). Ia sepatutnya kelihatan seperti ini: Analisis tugasan ini boleh didapati di sini: " Laksanakan Gilir Menggunakan Tindanan - ADT Baris Gilir ("Implement Queue using Stacks" pada LeetCode) ". Jadi kami lancar beralih kepada struktur data baharu - baris gilir.

Beratur

Baris Gilir ialah struktur yang biasa kita kenali dari kehidupan. Beratur ke kedai, ke doktor. Sesiapa yang datang dahulu (Masuk Dahulu) akan menjadi yang pertama meninggalkan barisan (Masuk Dahulu). Di Java, baris gilir diwakili oleh antara muka java.util.Queue . Menurut Javadoc baris gilir, baris gilir menambah kaedah berikut: Seperti yang anda lihat, terdapat kaedah pesanan (kegagalan untuk melaksanakannya penuh dengan pengecualian) dan terdapat kaedah permintaan (ketidakupayaan untuk melaksanakannya tidak membawa kepada ralat). Ia juga mungkin untuk mendapatkan elemen tanpa mengeluarkannya (mengintip atau elemen). Antara muka baris gilir juga mempunyai pengganti yang berguna - Deque . Ini adalah apa yang dipanggil "baris gilir dua hala". Iaitu, baris gilir sedemikian membolehkan anda menggunakan struktur ini dari awal dan dari akhir. Dokumentasi mengatakan bahawa "Deques juga boleh digunakan sebagai tindanan LIFO (Last-In-First-Out). Antara muka ini harus digunakan sebagai keutamaan kepada kelas Stack legasi.", iaitu, adalah disyorkan untuk menggunakan pelaksanaan Deque dan bukannya Timbunan. Javadoc menunjukkan kaedah yang diterangkan antara muka Deque: Mari lihat apakah pelaksanaan yang ada. Dan kita akan melihat fakta yang menarik - LinkedList telah masuk ke kem baris gilir) Iaitu, LinkedList melaksanakan kedua-dua List, dan Deque. Tetapi terdapat juga "baris gilir sahaja", contohnya PriorityQueue. Dia tidak sering diingati, tetapi sia-sia. Pertama, anda tidak boleh menggunakan "objek tidak setanding" dalam baris gilir ini, i.e. sama ada Pembanding mesti dinyatakan atau semua objek mesti setanding. Kedua, "pelaksanaan ini menyediakan masa O(log(n)) untuk kaedah enqueuing dan dequeuing". Kerumitan logaritma ada sebabnya. Dilaksanakan PriorityQueue berdasarkan timbunan. Javadoc berkata: "Baris gilir keutamaan diwakili sebagai timbunan binari yang seimbang." Storan itu sendiri untuk ini adalah tatasusunan biasa. Yang tumbuh apabila perlu. Apabila timbunan kecil, ia meningkat 2 kali ganda. Dan kemudian sebanyak 50%. Komen daripada kod: "Saiz dua kali ganda jika kecil; jika tidak berkembang sebanyak 50%". Barisan keutamaan dan Binary Heap adalah topik yang berasingan. Jadi untuk maklumat lanjut:

• Artikel super tentang Habré: " Struktur data. Panduan tidak rasmi "
• Penjelasan yang jelas tentang "timbunan": " Foxford: Sains Komputer. Struktur data: Timbunan "
• Artikel daripada Habr tentang Binary Heap: " Struktur data: binary heap "
• " Pengenalan kepada Binary Heaps (MaxHeaps) "

Pelaksanaan java.util.Dequeboleh menjadi kelas java.util.ArrayDeque . Iaitu, senarai boleh dilaksanakan menggunakan senarai terpaut dan tatasusunan, dan baris gilir juga boleh dilaksanakan menggunakan tatasusunan atau menggunakan senarai terpaut. Antara muka Queuedan Dequemempunyai keturunan yang mewakili "baris gilir menyekat": BlockingQueuedan BlockingDeque. Berikut ialah perubahan antara muka berbanding dengan baris gilir biasa: Mari lihat beberapa contoh menyekat baris gilir. Tetapi mereka menarik. Sebagai contoh, BlockingQueue dilaksanakan oleh: PriorityBlockingQueue , SynchronousQueue , ArrayBlockingQueue, DelayQueue , LinkedBlockingQueue . Tetapi BlockingDequemereka melaksanakan segala-galanya daripada Rangka Kerja Pengumpulan standard LinkedBlockingDeque. Setiap baris gilir adalah topik semakan yang berasingan. Dan dalam rangka kajian ini, kami akan menggambarkan hierarki kelas bukan sahaja dengan List, tetapi juga dengan Queue: Seperti yang dapat kita lihat daripada rajah, antara muka dan kelas Rangka Kerja Koleksi Java sangat berkait. Mari tambah satu lagi cabang hierarki - Set.

Tetapkan

Set— diterjemahkan sebagai “set.” Ia berbeza daripada baris gilir dan senarai Setdalam abstraksi yang lebih besar ke atas penyimpanan elemen. Set- seperti beg objek, di mana ia tidak diketahui bagaimana objek itu terletak dan dalam susunan apa ia diletakkan. Di Java, set sedemikian diwakili oleh antara muka java.util.Set . Seperti yang dinyatakan dalam dokumentasi, Setini ialah "koleksi yang tidak mengandungi unsur pendua". Menariknya, antara muka itu sendiri Settidak menambah kaedah baharu pada antara muka Collection, tetapi hanya menjelaskan keperluan (tentang perkara yang tidak sepatutnya mengandungi pendua). Di samping itu, dari penerangan sebelumnya, anda tidak boleh Setmendapatkan elemen daripadanya. Iterator digunakan untuk mendapatkan elemen. Setmempunyai beberapa lagi antara muka yang dikaitkan dengannya. Yang pertama ialah SortedSet. Seperti namanya, SortedSetia menunjukkan bahawa set sedemikian diisih, dan oleh itu elemen melaksanakan antara muka Comparableatau ditentukan Comparator. Di samping itu, SortedSetia menawarkan beberapa kaedah yang menarik: Selain itu, terdapat kaedah first(elemen terkecil mengikut nilai) dan last(elemen terbesar mengikut nilai). Ada SortedSetwaris - NavigableSet. Tujuan antara muka ini adalah untuk menerangkan kaedah navigasi yang diperlukan untuk mengenal pasti elemen yang sesuai dengan lebih tepat. Satu perkara yang menarik ialah NavigableSetia menambah kepada lelaran biasa (yang pergi dari terkecil ke terbesar) satu lelaran untuk susunan terbalik - descendingIterator. Di samping itu, NavigableSetia membolehkan anda menggunakan kaedah descendingSetuntuk mendapatkan pandangan diri anda (View), di mana unsur-unsur berada dalam susunan terbalik. Ini dipanggil Viewkerana melalui elemen yang terhasil anda boleh menukar elemen yang asal Set. Iaitu, pada dasarnya, ia adalah perwakilan data asal dengan cara yang berbeza, dan bukan salinannya. Menariknya, NavigableSet, seperti Queue, boleh mengendalikan elemen pollFirst(minimum) dan pollLast(maksimum). Iaitu, ia mendapat elemen ini dan mengeluarkannya dari set. Apakah jenis pelaksanaan yang ada? Pertama, pelaksanaan yang paling terkenal adalah berdasarkan kod cincang - HashSet . Satu lagi pelaksanaan yang sama terkenal adalah berdasarkan pokok merah-hitam - TreeSet . Mari lengkapkan rajah kami: Dalam koleksi, ia kekal untuk menyusun hierarki - pertapa. Yang pada pandangan pertama menepi - java.util.Map.

Peta

Peta ialah struktur data di mana data disimpan oleh kunci. Sebagai contoh, kunci boleh menjadi ID atau kod bandar. Dan dengan kunci inilah data akan dicari. Adalah menarik bahawa kad dipaparkan secara berasingan. Menurut pembangun (lihat " Soalan Lazim Reka Bentuk API Koleksi Java "), pemetaan nilai kunci bukan koleksi. Dan peta boleh lebih cepat dianggap sebagai koleksi kunci, koleksi nilai, koleksi pasangan nilai kunci. Ini adalah haiwan yang menarik. Apakah kaedah yang disediakan oleh kad? Mari lihat antara muka API Java java.util.Map . Kerana Memandangkan peta bukan koleksi (ia tidak mewarisi daripada Koleksi), ia tidak mengandungi contains. Dan ini adalah logik. Peta terdiri daripada kunci dan nilai. Yang manakah antara ini harus disemak kaedah containsdan bagaimana untuk tidak keliru? Oleh itu, antara muka Mapmempunyai dua versi berbeza: containsKey(mengandungi kunci) dan containsValue(mengandungi nilai). Menggunakannya keySetmembolehkan anda mendapatkan satu set kunci (yang sama Set). Dan menggunakan kaedah itu valueskita boleh mendapatkan koleksi nilai dalam peta. Kekunci dalam peta adalah unik, yang ditekankan oleh struktur data Set. Nilai boleh diulang, yang ditekankan oleh struktur data Pengumpulan. Di samping itu, dengan menggunakan kaedah itu entrySetkita boleh mendapatkan satu set pasangan nilai kunci. Anda boleh membaca lebih lanjut tentang pelaksanaan kad yang terdapat dalam analisis yang paling terperinci:

• " Struktur data dalam gambar. HashMap "
• " Struktur data dalam gambar. LinkedHashMap "
• " Kerja dalaman HashMap dalam Java (upd untuk Java 8) "

Saya juga ingin melihat apa yang HashMaphampir sama dengan HashSet, dan TreeMapkepada TreeSet. Mereka juga mempunyai antara muka yang serupa: NavigableSetdan NavigableMap, SortedSetdan SortedMap. Jadi peta akhir kami akan kelihatan seperti ini: SetKita boleh selesaikan dengan fakta menarik yang digunakan oleh koleksi secara dalaman Map, di mana nilai tambah adalah kunci, dan nilainya adalah sama di mana-mana. Ini menarik kerana ia Mapbukan koleksi dan pulangan Set, iaitu koleksi tetapi sebenarnya dilaksanakan sebagai Map. Sedikit nyata, tetapi itulah yang berlaku)

Kesimpulan

Berita baiknya ialah ulasan ini berakhir di sini. Berita buruknya ialah ini adalah artikel yang sangat ulasan. Setiap pelaksanaan setiap koleksi memerlukan artikel yang berasingan, dan juga untuk setiap algoritma yang tersembunyi dari mata kita. Tetapi tujuan semakan ini adalah untuk mengingati apa itu dan apakah hubungan antara antara muka. Saya harap selepas membaca dengan teliti anda akan dapat melukis gambar rajah koleksi dari ingatan. Nah, seperti biasa, beberapa pautan:

• " Jejak Oracle: Koleksi "
• " Tutorial IBM: Koleksi Java "
• " Yuri Tkach: Java Lanjutan - Koleksi "
• " Java Collections: The Force Awakens oleh Raoul-Gabriel Urma dan Richard Warburton "
• " Timur Batyrshinov: 22 - Asas java. Koleksi (dan video berikut daripada Senarai Main) "
• " Lima Perkara yang Anda Tidak Tahu Tentang... API Koleksi Java "

#Viacheslav