Perbandingan HashSet dan TreeSet

1. Pengenalan

Dalam artikel ini, kita akan membandingkan dua pelaksanaan Java yang paling popular dari antara muka java.util.Set - HashSet dan TreeSet .

2. Perbezaan

HashSet dan TreeSet adalah daun dari cabang yang sama, tetapi berbeza dalam beberapa perkara penting.

2.1. Memesan

HashSet menyimpan objek dalam urutan rawak, sedangkan TreeSet menerapkan susunan semula jadi elemen. Mari lihat contoh berikut:

@Test public void givenTreeSet_whenRetrievesObjects_thenNaturalOrder() { Set set = new TreeSet(); set.add("Baeldung"); set.add("is"); set.add("Awesome"); assertEquals(3, set.size()); assertTrue(set.iterator().next().equals("Awesome")); }

Setelah menambahkan objek String ke TreeSet , kami melihat yang pertama adalah "Hebat", walaupun ia telah ditambahkan pada akhir. Operasi serupa yang dilakukan dengan HashSet tidak menjamin bahawa susunan elemen akan tetap berterusan sepanjang masa.

2.2. Objek Batal

Perbezaan lain ialah HashSet dapat menyimpan objek kosong , sementara TreeSet tidak membenarkannya :

@Test(expected = NullPointerException.class) public void givenTreeSet_whenAddNullObject_thenNullPointer() { Set set = new TreeSet(); set.add("Baeldung"); set.add("is"); set.add(null); } @Test public void givenHashSet_whenAddNullObject_thenOK() { Set set = new HashSet(); set.add("Baeldung"); set.add("is"); set.add(null); assertEquals(3, set.size()); }

Sekiranya kita cuba menyimpan objek null di TreeSet , operasi akan menghasilkan NullPointerException yang dilemparkan . Satu-satunya pengecualian adalah di Java 7 apabila ia dibenarkan memiliki satu elemen null di TreeSet .

2.3. Persembahan

Ringkasnya, HashSet lebih pantas daripada TreeSet .

HashSet memberikan prestasi masa berterusan untuk kebanyakan operasi seperti tambah () , hapus () dan mengandungi () , berbanding log ( n ) masa yang ditawarkan oleh TreeSet.

Biasanya, kita dapat melihat bahawa masa pelaksanaan untuk menambahkan elemen ke dalam TreeSet jauh lebih baik daripada untuk HashSet .

Ingatlah bahawa JVM mungkin tidak dipanaskan, jadi masa pelaksanaannya mungkin berbeza. Perbincangan yang baik bagaimana merancang dan melaksanakan ujian mikro menggunakan pelbagai pelaksanaan Set terdapat di sini.

2.4. Kaedah yang Dilaksanakan

TreeSet kaya dengan fungsi , menerapkan kaedah tambahan seperti:

  • pollFirst () - untuk mengembalikan elemen pertama, atau nol jika Set kosong
  • pollLast () - untuk mengambil dan mengeluarkan elemen terakhir, atau mengembalikan null jika Set kosong
  • pertama () - untuk mengembalikan item pertama
  • terakhir () - untuk mengembalikan item terakhir
  • siling () - untuk mengembalikan elemen paling kecil yang lebih besar daripada atau sama dengan elemen yang diberikan, atau batal jika tidak ada unsur tersebut
  • lebih rendah () - untuk mengembalikan elemen terbesar dengan betul kurang daripada elemen yang diberikan, atau batal jika tidak ada unsur tersebut

Kaedah yang disebutkan di atas menjadikan TreeSet lebih mudah digunakan dan lebih berkuasa daripada HashSet .

3. Persamaan

3.1. Unsur Unik

Kedua-dua TreeSet dan HashSet menjamin koleksi salinan bebas daripada unsur-unsur, kerana ia adalah sebahagian daripada generik Set muka:

@Test public void givenHashSetAndTreeSet_whenAddDuplicates_thenOnlyUnique() { Set set = new HashSet(); set.add("Baeldung"); set.add("Baeldung"); assertTrue(set.size() == 1); Set set2 = new TreeSet(); set2.add("Baeldung"); set2.add("Baeldung"); assertTrue(set2.size() == 1); }

3.2. Tidak disegerakkan

Tiada pelaksanaan Set yang dijelaskan diselaraskan . Ini bermaksud bahawa jika beberapa utas mengakses Set secara serentak, dan sekurang-kurangnya salah satu utas mengubahnya, maka ia mesti disegerakkan secara luaran.

3.3. Iterator gagal cepat

The Pelelar s dikembalikan oleh TreeSet dan HashSet adalah gagal pantas.

Itu bermaksud bahawa pengubahsuaian Set pada bila-bila masa selepas Iterator dibuat akan melancarkan ConcurrentModificationException:

@Test(expected = ConcurrentModificationException.class) public void givenHashSet_whenModifyWhenIterator_thenFailFast() { Set set = new HashSet(); set.add("Baeldung"); Iterator it = set.iterator(); while (it.hasNext()) { set.add("Awesome"); it.next(); } }

4. Pelaksanaan Yang Mana Yang Digunakan?

Kedua-dua pelaksanaan memenuhi kontrak idea satu set sehingga terserah pada konteks implementasi yang mungkin kita gunakan.

Berikut adalah beberapa perkara cepat yang perlu diingat:

  • Sekiranya kita ingin memastikan penyertaan kita disusun, kita perlu mencari TreeSet
  • Sekiranya kita menilai prestasi lebih daripada penggunaan memori, kita harus menggunakan HashSet
  • Sekiranya kita kekurangan memori, kita harus mencari TreeSet
  • Sekiranya kita ingin mengakses elemen yang agak dekat satu sama lain mengikut susunan semula jadi mereka, kita mungkin ingin mempertimbangkan TreeSet kerana mempunyai lokasi yang lebih besar
  • Prestasi HashSet dapat diselaraskan dengan menggunakan Kapasitas awal dan LoadFactor , yang tidak mungkin untuk TreeSet
  • Sekiranya kita ingin mengekalkan pesanan penyisipan dan mendapat keuntungan dari akses masa yang berterusan, kita dapat menggunakan LinkedHashSet

5. Kesimpulan

Dalam artikel ini, kami membahas perbezaan dan persamaan antara TreeSet dan HashSet .

Seperti biasa, contoh kod untuk artikel ini terdapat di GitHub.