HashSet vs LinkedHashSet

153

Apa perbedaan di antara mereka? saya tahu itu

LinkedHashSet adalah versi HashSet yang diurutkan yang memelihara Daftar yang ditautkan ganda di semua elemen. Gunakan kelas ini alih-alih HashSet saat Anda peduli dengan urutan iterasi. Saat Anda mengulang melalui HashSet, urutannya tidak dapat diprediksi, sementara LinkedHashSet memungkinkan Anda mengulangi elemen-elemen sesuai urutan dimasukkannya.

Tetapi dalam kode sumber LinkedHashSet hanya ada memanggil konstruktor dari HashSet. Jadi di mana Daftar ditautkan ganda dan urutan penyisipan?

Shikarn-O
sumber
2
gunakan opsi Intellij (Ctrl + B) untuk melacak jawabannya. :)
Delta
tentu saja Anda perlu kode sumber terlampir. :)
Delta

Jawaban:

65

Jawaban terletak pada yang konstruktor yang LinkedHashSetmenggunakan untuk membangun kelas dasar:

public LinkedHashSet(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor, true);      // <-- boolean dummy argument
}

...

public LinkedHashSet(int initialCapacity) {
    super(initialCapacity, .75f, true);            // <-- boolean dummy argument
}

...

public LinkedHashSet() {
    super(16, .75f, true);                         // <-- boolean dummy argument
}

...

public LinkedHashSet(Collection<? extends E> c) {
    super(Math.max(2*c.size(), 11), .75f, true);   // <-- boolean dummy argument
    addAll(c);
}

Dan (salah satu contoh) HashSetkonstruktor yang mengambil argumen boolean dijelaskan, dan terlihat seperti ini:

/**
 * Constructs a new, empty linked hash set.  (This package private
 * constructor is only used by LinkedHashSet.) The backing
 * HashMap instance is a LinkedHashMap with the specified initial
 * capacity and the specified load factor.
 *
 * @param      initialCapacity   the initial capacity of the hash map
 * @param      loadFactor        the load factor of the hash map
 * @param      dummy             ignored (distinguishes this
 *             constructor from other int, float constructor.)
 * @throws     IllegalArgumentException if the initial capacity is less
 *             than zero, or if the load factor is nonpositive
 */
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<E,Object>(initialCapacity, loadFactor);
}
aioobe
sumber
2
Kelas induk memiliki fungsi secara eksplisit untuk kelas anak, argumen yang diabaikan untuk membedakan
Traubenfuchs
5
Bukan desain yang bersih menggunakan parameter dummy untuk disambiguasi konstruktor.
Eric J.
8
Ini adalah desain yang cukup bersih, karena APInya bersih (konstruktor HashSet ini adalah paket pribadi). Detail implementasi tidak masalah bagi pengguna kelas. Mempertahankan kode ini bisa lebih sulit, tetapi dalam kasus kelas java.util, bahkan peningkatan kinerja yang sangat kecil dapat membenarkan hal itu.
lbalazscs
25

LinkedHashSetKonstruktor memanggil konstruktor kelas dasar berikut:

HashSet(int initialCapacity, float loadFactor, boolean dummy) {
  map = new LinkedHashMap<E, Object>(initialCapacity, loadFactor);
}

Seperti yang Anda lihat, peta internal adalah a LinkedHashMap. Jika Anda melihat ke dalam LinkedHashMap, Anda akan menemukan bidang berikut:

private transient Entry<K, V> header;

Ini adalah daftar tertaut yang dimaksud.

NPE
sumber
24

HashSet tidak diatur dan tidak disortir .
LinkedHashSet adalah versi HashSet yang dipesan .

Satu-satunya perbedaan antara HashSet dan LinkedHashSet adalah bahwa:
LinkedHashSet mempertahankan urutan penyisipan.

Saat kami mengulang melalui HashSet , pesanannya tidak dapat diprediksi sementara itu dapat diprediksi dalam kasus LinkedHashSet .

Alasan bagaimana LinkedHashSet mempertahankan urutan penyisipan adalah bahwa:
Struktur data yang digunakan yang mendasarinya adalah Doubly-Linked-List .

Hema Ganapathy
sumber
9

Anda harus melihat pada sumber HashSetkonstruktor itu panggilan ... itu adalah konstruktor khusus yang membuat dukungan Mapyang LinkedHashMapbukan hanya HashMap.

ColinD
sumber
Terima kasih, di HashSet ada konstruktor untuk membuat LinkedHashMap, yang disebut di LinkedHashSet dan semua logika ada di LinkedHashMap
Shikarn-O
5

Saya sarankan Anda untuk menggunakan LinkedHashSetsebagian besar waktu, karena memiliki kinerja yang lebih baik secara keseluruhan ):

  1. Pesanan iterasi yang dapat diprediksi, LinkedHashSet (Oracle)
  2. LinkedHashSet lebih mahal untuk pemasangan daripada HashSet;
  3. Secara umum kinerja sedikit lebih baik daripada HashMap, karena sebagian besar waktu kita menggunakan struktur Set untuk iterasi.

Tes kinerja:

------------- TreeSet -------------
 size       add  contains   iterate
   10       746       173        89
  100       501       264        68
 1000       714       410        69
10000      1975       552        69
------------- HashSet -------------
 size       add  contains   iterate
   10       308        91        94
  100       178        75        73
 1000       216       110        72
10000       711       215       100
---------- LinkedHashSet ----------
 size       add  contains   iterate
   10       350        65        83
  100       270        74        55
 1000       303       111        54
10000      1615       256        58

Anda dapat melihat halaman uji sumber di sini: Contoh Pengujian Kinerja Akhir

Dmytro Melnychuk
sumber
2
Saya tidak melihat adanya pemanasan JVM sebelum "benchmark" itu, jadi saya tidak akan menganggap serius data itu. Baca selengkapnya
Felix S
3

HashSet: Sebenarnya tidak teratur. jika Anda melewatkan parameter berarti

Set<Integer> set=new HashSet<Integer>();
for(int i=0;i<set.length;i++)
{
  SOP(set)`enter code here`
}

Put Out: Mungkin 2,1,3tidak dapat diprediksi. lain kali pesanan lain.

LinkedHashSet() yang menghasilkan Pesanan FIFO.

Justin
sumber
3

HashSet tidak mempertahankan urutan item penyisipan
LinkedHashSet mempertahankan urutan item penyisipan

Contoh

Set<String> set = ...;// using new HashSet<>() OR new LinkedHashSet<>()
set.add("2");
set.add("1");
set.add("ab");
for(String value : set){
   System.out.println(value);
}  

HashSet keluaran

1
ab
2

LinkedHashSet keluaran

2
1
ab
Phan Van Linh
sumber
2

HashSet:

Struktur data yang digarisbawahi adalah Hashtable. Objek duplikat tidak diizinkan. Urutan pemasukan tidak disimpan dan didasarkan pada kode objek hash. Penyisipan kosong dapat dilakukan (hanya sekali). Ini mengimplementasikan antarmuka Serializable, Clonable tetapi tidak RandomAccess. HashSet sebaiknya dipilih jika operasi yang sering dilakukan adalah operasi pencarian.

Dalam HashSet, duplikat tidak diperbolehkan. Jika pengguna mencoba untuk memasukkan duplikat ketika kami tidak akan mendapatkan pengecualian kompilasi atau runtime. tambah metode pengembalian hanya salah.

Konstruktor:

HashSet h = HashSet baru (); membuat objek HashSet kosong dengan kapasitas awal default 16 dan rasio pengisian default (Load factor) adalah 0,75.

HashSet h = HashSet baru (int initialCapacity); membuat objek HashSet kosong dengan initialCapacity yang ditentukan dan rasio pengisian standar adalah 0,75.

HashSet h = HashSet baru (int initialCapacity, float fillRatio);

HashSet h = HashSet baru (Koleksi c); membuat objek HashSet yang setara untuk koleksi yang diberikan. Konstruktor ini dimaksudkan untuk konversi antar antara objek koleksi.

LinkedHashSet:

Ini adalah kelas anak dari HashSet. itu persis sama dengan HashSet termasuk (Konstruktor dan Metode) kecuali perbedaan berikut.

Perbedaan HashSet:

  1. Struktur data yang digarisbawahi adalah Hashtable.
  2. Pesanan penyisipan tidak dipertahankan.
  3. memperkenalkan versi 1.2.

LinkedHashSet:

  1. Struktur data yang digarisbawahi adalah kombinasi dari LinkedList dan Hashtable.
  2. Urutan penyisipan dipertahankan.
  3. Diproduksi dalam versi 1.4.
Umapathi
sumber
1

Jika Anda melihat konstruktor yang dipanggil dari LinkedHashSetkelas, Anda akan melihat bahwa secara internal itu LinkedHashMapadalah yang digunakan untuk tujuan backing.

karang
sumber
0

Semua Metode dan konstruktor sama tetapi hanya satu perbedaan adalah LinkedHashset akan mempertahankan urutan penyisipan tetapi tidak akan memungkinkan duplikat.

Hashset tidak akan mempertahankan urutan penyisipan apa pun. Ini adalah kombinasi dari Daftar dan Atur sederhana :)

Anand Mohan
sumber