Perbandingan HashSet dan TreeSet

1. Perkenalan

Pada artikel ini, kita akan membandingkan dua implementasi Java yang paling populer dari antarmuka java.util.Set - HashSet dan TreeSet .

2. Perbedaan

HashSet dan TreeSet adalah daun dari cabang yang sama, tetapi mereka berbeda dalam beberapa hal penting.

2.1. Memerintah

HashSet menyimpan objek dalam urutan acak, sedangkan TreeSet menerapkan urutan alami elemen. Mari kita lihat contoh berikut ini:

@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 , kita melihat bahwa yang pertama adalah "Awesome", meskipun itu ditambahkan di bagian paling akhir. Operasi serupa yang dilakukan dengan HashSet tidak menjamin bahwa urutan elemen akan tetap konstan dari waktu ke waktu.

2.2. Objek Nol

Perbedaan lainnya adalah HashSet dapat menyimpan objek null , sedangkan TreeSet tidak mengizinkannya :

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

Jika kita mencoba untuk menyimpan objek null di TreeSet , operasi akan menghasilkan NullPointerException yang dilempar . Satu-satunya pengecualian adalah di Java 7 ketika diizinkan untuk memiliki tepat satu elemen null di TreeSet .

2.3. Performa

Sederhananya, HashSet lebih cepat dari TreeSet .

HashSet menyediakan kinerja waktu konstan untuk sebagian besar operasi seperti add () , remove () dan contains () , versus waktu log ( n ) yang ditawarkan oleh TreeSet.

Biasanya, kita dapat melihat bahwa waktu eksekusi untuk menambahkan elemen ke TreeSet jauh lebih baik daripada HashSet .

Harap diingat bahwa JVM mungkin tidak melakukan pemanasan, sehingga waktu eksekusi bisa berbeda. Diskusi yang baik tentang cara merancang dan melakukan pengujian mikro menggunakan berbagai implementasi Set tersedia di sini.

2.4. Metode yang Diimplementasikan

TreeSet kaya akan fungsionalitas , menerapkan metode tambahan seperti:

  • pollFirst () - untuk mengembalikan elemen pertama, atau null jika Set kosong
  • pollLast () - untuk mengambil dan menghapus elemen terakhir, atau mengembalikan null jika Set kosong
  • first () - untuk mengembalikan item pertama
  • last () - untuk mengembalikan item terakhir
  • ceiling () - untuk mengembalikan elemen terkecil yang lebih besar dari atau sama dengan elemen yang diberikan, atau null jika elemen tersebut tidak ada
  • lower () - untuk mengembalikan elemen terbesar secara ketat lebih kecil dari elemen yang diberikan, atau null jika tidak ada elemen seperti itu

Metode yang disebutkan di atas membuat TreeSet lebih mudah digunakan dan lebih kuat daripada HashSet .

3. Persamaan

3.1. Elemen Unik

Baik TreeSet dan HashSet menjamin koleksi elemen bebas duplikat, karena ini adalah bagian dari antarmuka Set generik :

@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 tersinkronisasi

Tak satu pun dari implementasi Set yang dijelaskan disinkronkan . Ini berarti bahwa jika beberapa thread mengakses sebuah Set secara bersamaan, dan setidaknya salah satu thread memodifikasinya, maka itu harus disinkronkan secara eksternal.

3.3. Iterator cepat gagal

The Iterator s dikembalikan oleh TreeSet dan HashSet yang gagal-cepat.

Itu berarti bahwa setiap modifikasi Set kapan saja setelah Iterator dibuat akan memunculkan 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. Implementasi Mana yang Akan Digunakan?

Kedua implementasi tersebut memenuhi kontrak gagasan himpunan sehingga terserah konteks implementasi mana yang mungkin kita gunakan.

Berikut beberapa hal cepat yang perlu diingat:

  • Jika kita ingin menyimpan entri kita diurutkan, kita perlu menggunakan TreeSet
  • Jika kita menghargai kinerja lebih dari konsumsi memori, kita harus menggunakan HashSet
  • Jika kita kekurangan memori, kita harus memilih TreeSet
  • Jika kita ingin mengakses elemen yang relatif dekat satu sama lain sesuai dengan urutan aslinya, kita mungkin ingin mempertimbangkan TreeSet karena memiliki lokalitas yang lebih besar.
  • Kinerja HashSet dapat disetel menggunakan initialCapacity dan loadFactor , yang tidak dimungkinkan untuk TreeSet
  • Jika kita ingin mempertahankan urutan penyisipan dan mendapatkan keuntungan dari akses waktu yang konstan, kita dapat menggunakan LinkedHashSet

5. Kesimpulan

Pada artikel ini, kami membahas perbedaan dan persamaan antara TreeSet dan HashSet .

Seperti biasa, contoh kode untuk artikel ini tersedia di GitHub.