Cukuplah untuk membaca artikel ini tentang rangka kerja koleksi Java

Tanpa berlengah lagi, inilah gambarnya:

Koleksi Java, juga dikenali sebagai bekas, kebanyakannya terdiri daripada Diperoleh daripada dua antara muka utama (Antaramuka): 两大接口 (Interface) 派生出来的：
Collection 和 MapKoleksi dan Peta

Seperti namanya, bekas digunakan untuk menyimpan data.

Maka perbezaan antara dua antara muka ini ialah:

• Koleksi menyimpan satu elemen;
• Peta menyimpan pasangan nilai kunci.

Iaitu, bujang diletakkan dalam Koleksi, dan pasangan diletakkan dalam Peta. (Jadi, di manakah anda berada?

Mempelajari rangka kerja koleksi ini, saya rasa terdapat 4 matlamat:

1. Kosongkan surat-menyurat antara setiap antara muka dan kelas;
2. Biasakan diri dengan API yang biasa digunakan untuk setiap antara muka dan kelas;
3. Dapat memilih struktur data yang sesuai dan menganalisis kelebihan dan kekurangan untuk senario yang berbeza
4. Mempelajari reka bentuk kod sumber dan dapat menjawab temu bual

, artikel sebelumnya di HashMap telah membincangkannya dengan sangat teliti dan terperinci, jadi saya tidak akan membincangkan butiran dalam artikel ini Jika anda belum membaca artikel itu lagi, sila pergi ke akaun rasmi dan balas "

HashMap. " untuk membaca artikel~

Koleksi

Mari kita lihat Koleksi peringkat teratas dahulu.

Koleksi juga mentakrifkan banyak kaedah, yang juga diwarisi ke dalam pelbagai sub-antara muka dan kelas pelaksanaan Penggunaan API ini juga merupakan ujian biasa dalam kerja harian dan temu duga, jadi mari kita lihat kaedah ini terlebih dahulu.

Set operasi tidak lebih daripada empat kategori "Tambah, Padam, Ubah Suai dan Semak", juga dipanggil CRUD:

Buat, Baca, Kemas Kini dan Padam.

Kemudian saya juga membahagikan API ini kepada ini empat kategori:

Fungsi	kaedah
add	add()/addAll()
	()
berubah	Tidak tersedia dalam Antara Muka Koleksi
Semak	mengandungi()/mengandungiSemua()

Lain-lain🎜🎜isKosong()/size()/toArray()🎜🎜🎜

Lihat secara terperinci di bawah:

Ditambah:

boolean add(E e);

add() Jenis data yang dihantar mestilah Object, jadi apabila menulis jenis data asas, auto-boxing dan automatik unpacking akan dilakukan Box unboxing. add() 方法传入的数据类型必须是 Object，所以当写入基本数据类型的时候，会做自动装箱 auto-boxing 和自动拆箱 unboxing。

还有另外一个方法 addAll()，可以把另一个集合里的元素加到此集合中。

boolean addAll(Collection<? extends E> c);

删：

boolean remove(Object o);

remove()是删除的指定元素。

那和 addAll() 对应的，
自然就有removeAll()

Terdapat kaedah lainaddAll(), anda boleh menambah elemen daripada koleksi lain pada koleksi ini.

boolean removeAll(Collection<?> c);

Padam:

boolean contains(Object o);

remove() ialah elemen tertentu yang dipadamkan. 🎜🎜NaheaddAll ( ) Selaras dengan itu,
secara semula jadi terdapat removeAll() adalah untuk memadam semua elemen dalam set B. 🎜

boolean containsAll(Collection<?> c);

🎜🎜🎜Tukar: 🎜🎜🎜🎜Tiada operasi langsung untuk menukar elemen dalam Antara Muka Koleksi Bagaimanapun, pemadaman dan penambahan boleh melengkapkan perubahan! 🎜

查：

• 查下集合中有没有某个特定的元素：

boolean contains(Object o);

• 查集合 A 是否包含了集合 B：

boolean containsAll(Collection<?> c);

还有一些对集合整体的操作：

• 判断集合是否为空：

boolean isEmpty();

• 集合的大小：

int size();

• 把集合转成数组：

Object[] toArray();

以上就是 Collection 中常用的 API 了。

在接口里都定义好了，子类不要也得要。

当然子类也会做一些自己的实现，这样就有了不同的数据结构。

那我们一个个来看。

List

List 最大的特点就是：有序，可重复。

看官网说的：

An ordered collection (also known as a sequence).

Unlike sets, lists typically allow duplicate elements.

Kali ini saya sebutkan pula ciri-ciri Set Berlawanan sama sekali dengan Set ialah 无序，不重复.

Senarai boleh dilaksanakan dalam dua cara: LinkedList dan ArrayList Soalan yang paling biasa ditanya semasa temu duga ialah cara memilih antara dua struktur data ini.

Untuk masalah pemilihan jenis ini:
Pertama ialah mempertimbangkan sama ada struktur data boleh melengkapkan fungsi yang diperlukan
Jika kedua-duanya boleh diselesaikan, yang kedua ialah mempertimbangkan yang lebih cekap.

(Semuanya seperti ini.

Mari lihat secara khusus pada API kedua-dua kelas ini dan kerumitan masanya:

O(1)O(1)meningkatkantambah(int index, E e)O(n)O(n)deletemove(int index)O(n)O(n)O(n)O(n)ubahset(int index, E e)O(1)O(n)indeks

Sedikit penjelasan:

add(E e) menambah elemen pada ekor. Walaupun ArrayList mungkin berkembang, kerumitan masa terlunas masih O(1). add(E e) 是在尾巴上加元素，虽然 ArrayList 可能会有扩容的情况出现，但是均摊复杂度（amortized time complexity）还是 O(1) 的。

add(int index, E e)是在特定的位置上加元素，LinkedList 需要先找到这个位置，再加上这个元素，虽然单纯的「加」这个动作是 O(1) 的，但是要找到这个位置还是 O(n) 的。（这个有的人就认为是 O(1)，和面试官解释清楚就行了，拒绝扛精。

remove(int index)是 remove 这个 index 上的元素，所以

• ArrayList 找到这个元素的过程是 O(1)，但是 remove 之后，后续元素都要往前移动一位，所以均摊复杂度是 O(n)；
• LinkedList 也是要先找到这个 index，这个过程是 O(n) 的，所以整体也是 O(n)。

remove(E e)

add(int index, E e) ialah untuk menambah elemen pada kedudukan tertentu LinkedList perlu mencari kedudukan ini dahulu, dan kemudian menambah elemen ini Walaupun tindakan "tambah" yang mudah ialah O(1), ia perlu mencari ini Kedudukan masih O(n). (Sesetengah orang menganggap ini O(1). Hanya terangkan dengan jelas kepada penemuduga dan enggan mengambil tanggungjawab.

• remove(int index) adalah untuk mengalih keluar elemen pada indeks ini, jadi
• ArrayList mencari elemen ini Ia ialah O(1), tetapi selepas dialih keluar, elemen berikutnya mesti dialihkan ke hadapan dengan satu kedudukan, jadi kerumitan terlunas ialah O(n); ) , jadi keseluruhannya juga O(n)

remove(E e) ialah elemen pertama yang dilihat oleh remove, kemudian

ArrayList mesti mencari elemen ini dahulu. Proses ini ialah O(n), dan kemudian alih Selepas pembahagian, anda perlu bergerak satu kedudukan ke hadapan, iaitu O(n), dan jumlahnya masih O(n); dialih keluar, proses ini Ia adalah O(1), dan jumlahnya ialah O(n).

• Apakah sebab perbezaan kerumitan masa

  Jawapan
  :

• Sebab ArrayList dilaksanakan? dengan tatasusunan .

Ciri ini memungkinkan untuk mendapatkan nombor di mana-mana kedudukan dalam tatasusunan dalam masa O(1) melalui langganan, tetapi ini tidak boleh dilakukan dengan senarai terpaut, dan ia hanya boleh dilalui satu demi satu daripada permulaan.

Maksudnya, dari segi dua fungsi "pengubahsuaian dan carian", kerana tatasusunan boleh diakses secara rawak, ArrayList sangat cekap.

Bagaimana pula dengan "penambahan dan pemadaman"?

Jika masa untuk mencari elemen ini tidak dipertimbangkan,

Disebabkan kesinambungan fizikal tatasusunan, apabila menambah atau memadam elemen, ia adalah baik di bahagian ekor, tetapi tempat lain akan menyebabkan elemen seterusnya dipindahkan, jadi kecekapan adalah lebih rendah; dan Senarai terpaut boleh dengan mudah memutuskan sambungan daripada elemen seterusnya, terus memasukkan elemen baharu atau mengalih keluar elemen lama.

Tetapi, sebenarnya, anda perlu mengambil kira masa untuk mencari elemen. . . Dan jika ia dikendalikan pada ekor, ArrayList akan menjadi lebih pantas apabila jumlah data adalah besar.

Jadi:

1. Tukar dan pilih ArrayList;
2. Tambah dan padam ArrayList yang dipilih di akhir
3. ; ini adalah sama, adalah disyorkan untuk memilih ArrayList Kerana overhed adalah lebih kecil, atau penggunaan memori adalah lebih cekap.

VektorSebagai titik pengetahuan terakhir tentang Senarai, mari bercakap tentang Vektor. Ini juga merupakan siaran yang mendedahkan usia, digunakan oleh semua orang besar.

Kemudian Vektor, seperti ArrayList, juga mewarisi daripada java.util.AbstractList

, dan lapisan bawah juga dilaksanakan menggunakan tatasusunan.

Tetapi ia telah ditamatkan sekarang kerana...ia menambahkan terlalu banyak segerak!

Setiap faedah datang pada harga Kos keselamatan benang adalah kecekapan yang rendah, yang boleh menjadi halangan dalam sesetengah sistem Jadi sekarang kami tidak lagi menyegerakkan pada tahap struktur data, tetapi memindahkan tugas ini ke program kami ==

Jadi soalan temu bual biasa: Apakah perbezaan antara Vector dan ArrayList hanya menjawab ini tidak begitu komprehensif.

Mari kita lihat jawapan undian tinggi pada limpahan timbunan:

Yang pertama ialah isu keselamatan benang yang baru disebut;

Anda perlu melihat kod sumber untuk ini:

Ini adalah pelaksanaan pengembangan ArrayList Operasi anjakan kanan aritmetik

ini adalah untuk mengalihkan nombor perduaan bit nombor satu ini ke kanan, dan. paling kiri

melengkapkan bit tanda, tetapi kerana Tiada nombor negatif dalam kapasiti, jadi kami masih menambah 0.Kesan peralihan satu kedudukan ke kanan ialah membahagi dengan 2, maka kapasiti baru yang ditakrifkan ialah 1.5 kali ganda

daripada kapasiti asal.

Mari kita lihat Vektor sekali lagi:

Oleh kerana lazimnya capacityIncrement tidak ditentukan oleh kami, jadi secara lalai ia diperluas dua kali.

Jika anda menjawab dua perkara ini, anda pasti akan baik-baik saja.

Baris & Deque

Barisan ialah struktur data linear yang masuk pada satu hujung dan keluar pada hujung yang lain; .

Tetapi terdapat pengecualian di sini, iaitu, PriorityQueue, juga dipanggil heap, tidak keluar mengikut urutan masa masuk, tetapi keluar mengikut keutamaan yang ditetapkan, dan operasinya bukan O(1), pengiraan kerumitan masa Ia agak rumit, jadi kami akan membincangkannya dalam artikel berasingan kemudian.

Kaedah Queue

laman web rasmi[1] telah diringkaskan Ia mempunyai dua set API dan fungsi asasnya adalah sama, tetapi:

• Satu kumpulan akan membuang pengecualian;
• Kumpulan yang lain akan mengembalikan nilai istimewa. . padam
buang()

Fungsi	Kaedah	ArrayList	LinkedList
add(E e)	O(1)	O(1)
			erem
)	O(1)	O(n)

poll() Lihatelemen()peek()

Mengapa ia membuang pengecualian?

• Sebagai contoh, jika baris gilir kosong, maka remove() akan membuang pengecualian, tetapi poll() akan mengembalikan null() akan membuang pengecualian, dan peek() hanya akan mengembalikan null.

Bagaimana mungkin add(e) membuang pengecualian?

Sesetengah Baris mempunyai had kapasiti, seperti BlockingQueue Jika ia telah mencapai kapasiti maksimumnya dan tidak akan dikembangkan, pengecualian akan dilemparkan; macam mana nak pilih? :

Pertama sekali, jika anda ingin menggunakannya, gunakan
• set API yang sama
  , dan bahagian depan dan belakang harus bersatu

kedua, mengikut keperluan. Jika anda memerlukannya untuk membuang pengecualian, gunakan satu yang membuang pengecualian tetapi pada dasarnya ia tidak digunakan semasa melakukan masalah algoritma, jadi pilih sahaja yang mengembalikan nilai istimewa.

deque

deque boleh dimasukkan dan keluar dari kedua -dua hujungnya. pengecualian dan kumpulan yang lain Mengembalikan nilai istimewa:

fungsi membuang pengecualian nilai pulangan addaddaddoffer/First(e)/First(e) Terakhir (e)DeleteremoveFirst()/ removeLast()pollFirst()/ pollLast()Look

Begitu juga apabila menggunakannya Jika anda ingin menggunakannya, gunakan kumpulan yang sama.

API Baris Gilir dan Deque ini mempunyai kerumitan masa O(1). . capai;

Jika anda ingin melaksanakan semantik "gilir keutamaan", gunakan PriorityQueue

Jika anda ingin melaksanakan semantik "stack", gunakan ArrayDeque.

Jom tengok satu persatu.

Apabila melaksanakan baris gilir biasa,

Bagaimana untuk memilih antara LinkedList atau ArrayDeque?
• Mari kita lihat jawapan undian tinggi pada
StackOverflow
• [2]
  :
Ringkasnya, adalah disyorkan untuk menggunakan ArrayDeque kerana kecekapan tambahan tinggi LinkedL yang lain akan mempunyai kelebihan yang tinggi, manakala (overhead).

Apakah perbezaan antara ArrayDeque dan LinkedList? . tetapi LinkedList boleh;

ArrayDeque lebih cekap apabila mengendalikan operasi penambahan dan pemadaman pada permulaan dan penghujung, tetapi LinkedList hanya mengalih keluar elemen di tengah apabila ia akan dialih keluar dan elemen itu telah ditemui O( 1);

^{ArrayDeque lebih cekap dari segi penggunaan memori.}

Jadi, selagi anda tidak perlu menyimpan nilai nol, pilih ArrayDeque!

Kemudian jika penemuduga yang sangat senior bertanya kepada anda, dalam keadaan apakah anda harus memilih untuk menggunakan LinkedList?

• 答：Java 6 以前。。。因为 ArrayDeque 在 Java 6 之后才有的。。

为了版本兼容的问题，实际工作中我们不得不做一些妥协。。

那最后一个问题，就是关于 Stack 了。

Stack

Stack 在语义上是 后进先出（LIFO） 的线性数据结构。

有很多高频面试题都是要用到栈的，比如接水问题，虽然最优解是用双指针，但是用栈是最直观的解法也是需要了解的，之后有机会再专门写吧。

那在 Java 中是怎么实现栈的呢？

虽然 Java 中有 Stack 这个类，但是呢，官方文档都说不让用了！

原因也很简单，因为 Vector 已经过被弃用了，而 Stack 是继承 Vector 的。

那么想实现 Stack 的语义，就用 ArrayDeque 吧：

Deque<Integer> stack = new ArrayDeque<>();

Set

最后一个 Set，刚才已经说过了 Set 的特定是无序，不重复的。

就和数学里学的「集合」的概念一致。

Set 的常用实现类有三个：

HashSet: 采用 Hashmap 的 key 来储存元素，主要特点是无序的，基本操作都是 O(1) 的时间复杂度，很快。

LinkedHashSet: 这个是一个 HashSet + LinkedList 的结构，特点就是既拥有了 O(1) 的时间复杂度，又能够保留插入的顺序。

TreeSet: 采用红黑树结构，特点是可以有序，可以用自然排序或者自定义比较器来排序；缺点就是查询速度没有 HashSet 快。

那每个 Set 的底层实现其实就是对应的 Map：

Nilai diletakkan pada kekunci dalam peta, dan PRESENT diletakkan pada nilai Ia adalah Objek statik, bersamaan dengan pemegang tempat, dan setiap kunci menunjukkan objek ini. . , di sini saya tidak akan pergi ke butiran. Rakan-rakan yang belum membacanya boleh membalas “HashMap” di latar belakang akaun rasmi untuk mendapatkan artikel~

Ringkasan

kembali kepada gambar pada permulaan, adakah ia jelas? Sebenarnya terdapat banyak kandungan di bawah setiap struktur data, seperti PriorityQueue Artikel ini tidak menerangkan secara terperinci, kerana lelaki ini akan mengambil masa yang lama untuk membincangkannya. . Jika anda rasa artikel itu bagus, seperti di penghujung artikel itu kembali lagi, Ingat untuk memberi saya "like" dan "membaca"~

Akhirnya, ramai pembaca bertanyakan soalan tentang komunikasi itu. kumpulan, kerana saya memikirkannya, saya mengalami jet lag dan sukar untuk diuruskan, jadi saya belum melakukannya lagi.

Tetapi sekarang saya telah menemui pentadbir profesional untuk menguruskannya bersama saya, jadi "Pangkalan Rahsia Adik Qi" sedang dalam persediaan, dan saya akan menjemput beberapa nama besar di dalam dan luar negara untuk menyertainya bagi membawakan anda perspektif yang berbeza .

Fasa pertama pertukaran kumpulan dirancang untuk dibuka pada pertengahan hingga awal bulan Julai saya akan menghantar jemputan dalam kalangan rakan-rakan kemudian, jadi tunggu!

	First()/getLast ekLast()

Atas ialah kandungan terperinci Cukuplah untuk membaca artikel ini tentang rangka kerja koleksi Java. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!