Kapan saya harus menggunakan tipe HashSet <T>?

Saya sedang menjelajahi HashSet<T> tipenya, tapi saya tidak mengerti di mana koleksi itu berada.

Bisakah seseorang menggunakannya untuk mengganti List<T>? Saya membayangkan kinerja a HashSet<T>menjadi lebih baik, tetapi saya tidak bisa melihat akses individu ke elemen-elemennya.

Apakah hanya untuk pencacahan?

Yang penting tentang HashSet<T>ada di sana dalam nama: itu satu set . Satu-satunya hal yang dapat Anda lakukan dengan satu set adalah menetapkan apa anggotanya, dan untuk memeriksa apakah suatu item adalah anggota.

Bertanya apakah Anda dapat mengambil elemen tunggal (mis. set[45]) Adalah salah paham konsep himpunan. Tidak ada yang namanya elemen 45 set. Item dalam satu set tidak memiliki pemesanan. Set {1, 2, 3} dan {2, 3, 1} identik dalam segala hal karena mereka memiliki keanggotaan yang sama, dan keanggotaan adalah yang terpenting.

Ini agak berbahaya untuk diulang lebih dari satu HashSet<T> karena melakukan memaksakan pesanan pada item di set. Urutan itu sebenarnya bukan properti dari himpunan. Anda tidak harus bergantung padanya. Jika pemesanan barang-barang dalam koleksi penting bagi Anda, koleksi itu bukan satu set.

Set sangat terbatas dan dengan anggota yang unik. Di sisi lain, mereka sangat cepat.

Inilah contoh nyata tempat saya menggunakan HashSet<string>:

Bagian dari stabilo sintaksis saya untuk file UnrealScript adalah fitur baru yang menyoroti komentar gaya Doxygen . Saya harus tahu apakah perintah @atau \valid untuk menentukan apakah akan ditampilkan dalam warna abu-abu (valid) atau merah (tidak valid). Saya memiliki HashSet<string>semua perintah yang valid, jadi setiap kali saya menekan @xxxtoken di lexer, saya menggunakan validCommands.Contains(tokenText)sebagai cek validitas O (1) saya. Saya benar-benar tidak peduli tentang apa pun kecuali keberadaan perintah di set perintah yang valid. Mari kita lihat alternatif yang saya hadapi:

• Dictionary<string, ?>: Jenis apa yang saya gunakan untuk nilai? Nilai tidak ada artinya karena saya hanya akan menggunakan ContainsKey. Catatan: Sebelum. NET 3.0 ini adalah satu-satunya pilihan untuk pencarian O (1) - HashSet<T>ditambahkan untuk 3.0 dan diperluas untuk diterapkan ISet<T>untuk 4.0.
• List<string>: Jika saya menjaga daftar diurutkan, saya dapat menggunakan BinarySearch, yaitu O (log n) (tidak melihat fakta ini disebutkan di atas). Namun, karena daftar perintah saya yang valid adalah daftar tetap yang tidak pernah berubah, ini tidak akan pernah lebih tepat daripada sekadar ...
• string[]: Sekali lagi, Array.BinarySearchmemberikan O (log n) kinerja. Jika daftar ini pendek, ini bisa menjadi opsi dengan kinerja terbaik. Selalu memiliki overhead kurang ruang dari HashSet, Dictionaryatau List. Bahkan dengan BinarySearch, itu tidak lebih cepat untuk set besar, tetapi untuk set kecil itu layak untuk dicoba. Tambang saya memiliki beberapa ratus item, jadi saya meneruskan ini.

A HashSet<T>mengimplementasikan ICollection<T>antarmuka:

public interface ICollection<T> : IEnumerable<T>, IEnumerable
{
    // Methods
    void Add(T item);
    void Clear();
    bool Contains(T item);
    void CopyTo(T[] array, int arrayIndex);
    bool Remove(T item);

    // Properties
   int Count { get; }
   bool IsReadOnly { get; }
}

Sebuah List<T>implementasi IList<T>, yang memperluasICollection<T>

public interface IList<T> : ICollection<T>
{
    // Methods
    int IndexOf(T item);
    void Insert(int index, T item);
    void RemoveAt(int index);

    // Properties
    T this[int index] { get; set; }
}

HashSet telah menetapkan semantik, diimplementasikan melalui hashtable secara internal:

Set adalah kumpulan yang tidak mengandung elemen duplikat, dan yang elemennya tidak ada dalam urutan tertentu.

Apa yang didapat HashSet, jika kehilangan perilaku indeks / posisi / daftar?

Menambahkan dan mengambil item dari HashSet selalu oleh objek itu sendiri, bukan melalui pengindeks, dan dekat dengan operasi O (1) (Daftar adalah O (1) tambahkan, O (1) ambil dengan indeks, O (n) cari /menghapus).

Perilaku HashSet dapat dibandingkan dengan menggunakan Dictionary<TKey,TValue>hanya dengan menambahkan / menghapus kunci sebagai nilai, dan mengabaikan nilai kamus itu sendiri. Anda akan berharap kunci dalam kamus tidak memiliki nilai duplikat, dan itulah inti dari bagian "Set".

Kinerja akan menjadi alasan buruk untuk memilih HashSet daripada Daftar. Sebaliknya, apa yang lebih baik menangkap maksud Anda? Jika pesanan penting, maka Set (atau HashSet) keluar. Jika duplikat diizinkan, juga. Tetapi ada banyak keadaan ketika kita tidak peduli tentang pesanan, dan kami lebih suka tidak memiliki duplikat - dan saat itulah Anda menginginkan Set.

HashSet adalah a himpunan yang diimplementasikan dengan hashing. Set adalah kumpulan nilai yang tidak mengandung elemen duplikat. Nilai-nilai dalam set juga biasanya tidak terurut. Jadi tidak, satu set tidak dapat digunakan untuk mengganti daftar (kecuali Anda seharusnya menggunakan set di tempat pertama).

Jika Anda bertanya-tanya untuk apa set yang bagus: di mana saja Anda ingin menyingkirkan duplikat, jelas. Sebagai contoh yang sedikit dibuat-buat, katakanlah Anda memiliki daftar 10.000 revisi proyek perangkat lunak, dan Anda ingin mengetahui berapa banyak orang yang berkontribusi pada proyek itu. Anda bisa menggunakan Set<string>dan mengulangi daftar revisi dan menambahkan masing-masing penulis revisi ke set. Setelah Anda selesai iterasi, ukuran set adalah jawaban yang Anda cari.

HashSet akan digunakan untuk menghapus elemen duplikat dalam koleksi IEnumerable. Sebagai contoh,

List<string> duplicatedEnumrableStrings = new List<string> {"abc", "ghjr", "abc", "abc", "yre", "obm", "ghir", "qwrt", "abc", "vyeu"};
HashSet<string> uniqueStrings = new HashSet(duplicatedEnumrableStrings);

setelah kode-kode itu dijalankan, uniqueStrings memegang {"abc", "ghjr", "yre", "obm", "qwrt", "vyeu"};

Mungkin penggunaan yang paling umum untuk hashsets adalah untuk melihat apakah mereka mengandung elemen tertentu, yang dekat dengan operasi O (1) untuk mereka (dengan asumsi fungsi hashing yang cukup kuat), sebagai lawan dari daftar yang memeriksa inklusi adalah O ( n) (dan set diurutkan yang merupakan O (log n)). Jadi, jika Anda melakukan banyak pemeriksaan, apakah suatu item terkandung dalam beberapa daftar, hahssets mungkin merupakan peningkatan kinerja. Jika Anda hanya mengulanginya, tidak akan ada banyak perbedaan (iterasi pada seluruh set adalah O (n), sama dengan daftar dan hash memiliki overhead yang agak lebih banyak saat menambahkan item).

Dan tidak, Anda tidak dapat mengindeks satu set, yang tidak masuk akal, karena set tidak dipesan. Jika Anda menambahkan beberapa item, set tidak akan mengingat yang pertama, dan yang kedua dll.

HashSet<T>adalah strucutre data dalam kerangka NET. Yang mampu mewakili set matematika sebagai objek. Dalam hal ini, ia menggunakan kode hash ( GetHashCodehasil dari setiap item) untuk membandingkan kesetaraan elemen yang ditetapkan.

Himpunan berbeda dari daftar karena hanya memungkinkan satu kemunculan elemen yang sama yang terkandung di dalamnya. HashSet<T>hanya akan kembali falsejika Anda mencoba menambahkan elemen identik kedua. Memang, pencarian elemen sangat cepat ( O(1)waktu), karena struktur data internal hanyalah sebuah hashtable.

Jika Anda bertanya-tanya mana yang harus digunakan, perhatikan bahwa menggunakan di List<T>mana HashSet<T>yang tepat bukanlah kesalahan terbesar, meskipun mungkin berpotensi menimbulkan masalah di mana Anda memiliki item duplikat yang tidak diinginkan dalam koleksi Anda. Terlebih lagi, pencarian (pengambilan item) jauh lebih efisien - idealnya O(1)(untuk bucket sempurna) daripada O(n)waktu - yang cukup penting dalam banyak skenario.

List<T>digunakan untuk menyimpan set informasi yang dipesan. Jika Anda mengetahui urutan relatif dari elemen daftar, Anda dapat mengaksesnya dalam waktu yang konstan. Namun, untuk menentukan di mana elemen terletak di daftar atau untuk memeriksa apakah ada dalam daftar, waktu pencarian adalah linier. Di samping itu,HashedSet<T> tidak membuat jaminan urutan data yang disimpan dan akibatnya memberikan waktu akses yang konstan untuk elemen-elemennya.

Seperti namanya, HashedSet<T>adalah struktur data yang mengimplementasikan set semantik . Struktur data dioptimalkan untuk mengimplementasikan operasi yang ditetapkan (yaitu Union, Difference, Intersect), yang tidak dapat dilakukan seefisien dengan implementasi Daftar tradisional.

Jadi, untuk memilih tipe data mana yang akan digunakan sangat tergantung pada apa yang Anda coba lakukan dengan aplikasi Anda. Jika Anda tidak peduli tentang bagaimana elemen Anda disusun dalam koleksi, dan hanya ingin merinci atau memeriksa keberadaannya, gunakan HashSet<T>. Kalau tidak, pertimbangkan untuk menggunakan List<T>atau struktur data lain yang sesuai.

Singkatnya - kapan saja Anda tergoda untuk menggunakan Kamus (atau Kamus di mana S adalah properti T) maka Anda harus mempertimbangkan HashSet (atau HashSet + menerapkan IEquatable pada T yang sama dengan S)

Dalam skenario yang dimaksudkan dasar HashSet<T>harus digunakan ketika Anda ingin operasi set yang lebih spesifik pada dua koleksi daripada menyediakan LINQ. Metode LINQ seperti Distinct, Union, Intersectdan Exceptcukup dalam kebanyakan situasi, tapi kadang-kadang Anda mungkin perlu operasi lebih berbutir halus, dan HashSet<T>menyediakan:

• UnionWith
• IntersectWith
• ExceptWith
• SymmetricExceptWith
• Overlaps
• IsSubsetOf
• IsProperSubsetOf
• IsSupersetOf
• IsProperSubsetOf
• SetEquals

Perbedaan lain antara HashSet<T>metode LINQ dan "tumpang tindih" adalah bahwa LINQ selalu mengembalikan yang baru IEnumerable<T>, dan HashSet<T>metode memodifikasi koleksi sumber.