Define: Apa itu HashSet?

420

HashSet Struktur data C # HashSet diperkenalkan di .NET Framework 3.5. Daftar lengkap anggota yang diimplementasikan dapat ditemukan di halaman MSDN HashSet .

  1. Di mana itu digunakan?
  2. Mengapa Anda ingin menggunakannya?
c# hashset 001
sumber
4
en.wikipedia.org/wiki/Set_(computer_science)
Claus Jørgensen
3
kemungkinan duplikat Kapan saya harus menggunakan tipe HashSet <T>?
nawfal
Ini menggunakan hashtable secara internal. jika Anda memiliki implementasi hashtable yang bagus (misalnya Kamus <T>), Anda dapat mengimplementasikan HashSet sendiri dengan mudah.
Raz Megrelidze

Jawaban:

614

    1. A HashSetmemegang satu set objek, tetapi dengan cara yang memungkinkan Anda untuk dengan mudah dan cepat menentukan apakah suatu objek sudah di set atau tidak. Itu melakukannya dengan secara internal mengelola array dan menyimpan objek menggunakan indeks yang dihitung dari kode hash objek. Coba lihat di sini

    2. HashSetadalah koleksi tidak berurutan yang mengandung elemen unik. Ini memiliki operasi pengumpulan standar Tambahkan, Hapus, Berisi, tetapi karena menggunakan implementasi berbasis hash, operasi ini adalah O (1). (Berbeda dengan Daftar misalnya, yang O (n) untuk Berisi dan Hapus.) HashSetJuga menyediakan operasi set standar seperti penyatuan , persimpangan , dan perbedaan simetris . Coba lihat di sini

  2. Ada implementasi Sets yang berbeda. Beberapa membuat operasi penyisipan dan pencarian sangat cepat dengan elemen hashing. Namun, itu berarti bahwa urutan unsur-unsur ditambahkan hilang. Implementasi lain mempertahankan pesanan tambahan dengan biaya waktu berjalan yang lebih lambat.

The HashSetkelas dalam C # berlaku untuk pendekatan pertama, sehingga tidak menjaga urutan elemen. Ini jauh lebih cepat daripada yang biasa List. Beberapa tolok ukur dasar menunjukkan bahwa HashSet lumayan cepat ketika berhadapan dengan tipe primer (int, double, bool, dll.). Ini jauh lebih cepat ketika bekerja dengan objek kelas. Jadi intinya adalah HashSet cepat.

Satu-satunya kelemahan HashSetadalah bahwa tidak ada akses oleh indeks. Untuk mengakses elemen, Anda dapat menggunakan enumerator atau menggunakan fungsi bawaan untuk mengonversikannya HashSetmenjadi Listdan mengulanginya. Coba lihat di sini

kamaci
sumber
13
Dua hal, hashset dan yang serupa adalah .NET, bukan C #. HashSet juga tidak mempertahankan pesanan. Coba tambahkan dan hapus item dari hash set, Anda akan tahu jika Anda mengulanginya nanti ..
nawfal
13

A HashSetmemiliki struktur internal (hash), di mana item dapat dicari dan diidentifikasi dengan cepat. The downside adalah bahwa iterasi melalui HashSet(atau mendapatkan item dengan indeks) agak lambat.

Jadi mengapa seseorang ingin dapat mengetahui apakah suatu entri sudah ada dalam set?

Satu situasi di mana a HashSetberguna adalah dalam mendapatkan nilai yang berbeda dari daftar tempat duplikat mungkin ada. Setelah item ditambahkan ke item HashSet, cepat untuk menentukan apakah item ada ( Containsoperator).

Keuntungan lain dari HashSetyang operasi Set: IntersectWith, IsSubsetOf, IsSupersetOf, Overlaps, SymmetricExceptWith, UnionWith.

Jika Anda terbiasa dengan bahasa kendala objek maka Anda akan mengidentifikasi operasi set ini. Anda juga akan melihat bahwa ini selangkah lebih dekat dengan implementasi UML yang dapat dieksekusi.

k rey
sumber
20
Re: downside. Tidak, iterasi melalui HashSet sangat cepat. Kedua, tidak mungkin mendapatkan item berdasarkan indeks. Faktanya, elemen-elemen disimpan tanpa urutan.
Nigel Touch
@Nigel Touch. Iterasi cepat jika Anda tidak peduli dengan indeks (urutan penambahannya). Namun, jika Anda khawatir tentang indeks maka indeks harus disimpan dengan masing-masing kunci hash dan karena itu bisa agak lambat karena daftar harus dicari secara mendalam untuk mengambil item yang benar. Perilaku ini sangat berbeda dari daftar di mana item diindeks oleh urutan penambahannya.
k rey
Masuk akal mengapa itu akan cepat, karena tidak ada dua hash yang sama. Mengaktifkan kueri untuk mengambil keuntungan dari pendekatan "hubungan pendek", dengan cepat mengesampingkan kriteria tertentu.
Chef_Code
8

Sederhananya dan tanpa mengungkapkan rahasia dapur: satu set secara umum, adalah koleksi yang tidak mengandung unsur duplikat, dan yang unsur-unsurnya tidak ada dalam urutan tertentu. Jadi, A HashSet<T>mirip dengan generik List<T>, tetapi dioptimalkan untuk pencarian cepat (melalui hashtable, seperti namanya) dengan biaya kehilangan pesanan.

Ditumpuk
sumber
1
Tetapi dapatkah HashSet <T> menyimpan dua objek yang memiliki data yang sama, seperti dua kelas Produk yang masing-masing memiliki properti yang sama dengan konten yang sama?
Johan Herstad
Saya kira kita tidak akan pernah tahu
Denny
@JohanHerstad Mengasumsikan EqualityComparer untuk kelas Anda peduli dengan properti tersebut atau Anda membangun HashSet dengan IEqualityComparer yang peduli tentang properti itu, saya tidak mengerti mengapa tidak. The dokumentasi untuk HashSet membuat jelas bahwa itu bergantung pada satu atau yang lain untuk menentukan keunikan.
Bacon Bits
2

Dari perspektif aplikasi, jika seseorang hanya perlu menghindari duplikat maka HashSetapa yang Anda cari sejak itu adalah Pencarian, Masukkan dan Hapus kompleksitas adalah O (1) - konstan . Apa artinya ini tidak masalah berapa banyak elemen yang HashSetmemerlukan waktu yang sama untuk memeriksa apakah ada elemen seperti itu atau tidak, ditambah karena Anda memasukkan elemen pada O (1) juga membuatnya sempurna untuk hal semacam ini.

Matas Vaitkevicius
sumber