Pertanyaan Mengapa saya tidak dapat mengambil item dari HashSet tanpa enumerasi?


Saya mencari wawasan tentang kepala para desainer HashSet. Sejauh yang saya ketahui, pertanyaan saya berlaku untuk Java dan C # HashSets, membuat saya berpikir pasti ada beberapa alasan bagus untuk itu, meskipun saya tidak dapat memikirkannya sendiri.

Setelah saya memasukkan sebuah item ke dalam HashSet, mengapa tidak mungkin untuk mengambil item tersebut tanpa penghitungan, bukan operasi yang efisien? Terutama karena HashSet secara eksplisit dibangun dengan cara yang mendukung pengambilan yang efisien.

Akan sangat berguna bagi saya untuk memiliki Remove (x) dan Contains (x) mengembalikan item yang sebenarnya yang sedang dihapus atau terkandung. Ini belum tentu item yang saya masukkan ke fungsi Hapus (x) atau Berisi (x). Tentu, saya kira saya bisa mencapai efek yang sama melalui HashMap tetapi mengapa membuang semua ruang dan usaha itu padahal seharusnya sangat mungkin untuk melakukan ini dengan satu set?

Saya dapat menghargai bahwa mungkin ada kekhawatiran desain yang menambahkan fungsi ini akan memungkinkan penggunaan HashSet yang tidak konsisten dengan peran mereka atau peran masa depan dalam kerangka kerja, tetapi jika memang demikian, apa masalah desain ini?

Edit

Untuk menjawab beberapa pertanyaan lagi, berikut ini detailnya:

Saya menggunakan jenis referensi yang tidak dapat diubah dengan kode hash yang diganti, sama dengan, dll untuk meniru tipe nilai dalam C #. Katakanlah tipe ini memiliki anggota A, B, dan C. Hashcode, sama, dll hanya bergantung pada A dan B. Mengingat beberapa A dan BI ingin dapat mengambil item yang setara dari hashset dan mendapatkannya C. Saya menang ' t dapat menggunakan HashSet untuk ini muncul, tapi saya setidaknya ingin tahu apakah ada alasan yang baik untuk ini. Kode semu mengikuti:

public sealed class X{
 object A;
 object B;
 object extra;

 public int HashCode(){
  return A.hashCode() + B.hashCode();
 }

 public bool Equals(X obj){
  return obj.A == A && obj.B == B;
 }
}

hashset.insert(new X(1,2, extra1));
hashset.contains(new X(1,2)); //returns true, but I can't retrieve extra

32
2017-09-29 20:41


asal


Jawaban:


Bagaimana Anda mengusulkan untuk mengambil item dari himpunan hash? Seperangkat menurut definisi tidak diperintahkan dengan cara apa pun dan oleh karena itu, tidak ada indeks yang digunakan untuk mengambil objek yang dimaksud.

Set, sebagai sebuah konsep, digunakan untuk menguji penyertaan, yaitu apakah elemen yang dimaksud dalam kumpulan data hash. Jika Anda mencari untuk mengambil nilai dari sumber data menggunakan nilai kunci atau indeks, saya akan menyarankan untuk melihat apakah a Peta atau a Daftar.

EDIT: Jawaban tambahan berdasarkan pada Edit ke pertanyaan asli

Soonil, berdasarkan informasi baru Anda, sepertinya Anda mungkin tertarik untuk mengimplementasikan data Anda sebagai Java Enum, sesuatu yang mirip dengan ini:

 public enum SoonilsDataType {
      A, B, C;

      // Just an example of what's possible
      public static SoonilsDataType getCompositeValue(SoonilsDataType item1,
           SoonilsDataType item2) {
           if (item1.equals(A) && 
                     item2.equals(B)) {
                return C;
           }
      }
 }

Enum secara otomatis mewarisi nilai () yang mengembalikan daftar semua nilai dalam "set" enum, yang dapat Anda gunakan untuk menguji penyertaan terhadap dengan cara yang sama seperti Set. Juga, karena kelasnya yang penuh, Anda dapat menentukan metode statis baru untuk melakukan logika gabungan (seperti saya mencoba menyinggung dalam kode contoh). Satu-satunya hal tentang Enum adalah Anda tidak dapat menambahkan instance baru saat runtime, yang mungkin bukan yang Anda inginkan (meskipun jika ukuran data set tidak akan bertambah pada saat runtime, Enum adalah yang Anda inginkan).


9
2017-09-29 20:57



Di .Net, yang mungkin Anda cari adalah KeyedCollection http://msdn.microsoft.com/en-us/library/ms132438.aspx

Anda bisa mendapatkan sekitar nastiness mengimplementasikan kembali kelas abstrak ini setiap kali dengan kecerdasan "generik". (Lihat IKeyedObject`1.)

Catatan: Setiap objek transfer data yang mengimplementasikan IKeyedObject`1 harus memiliki metode GetHashCode yang diganti hanya dengan mengembalikan this.Key.GetHashCode (); dan hal yang sama berlaku untuk ...

My Base Class Library biasanya berakhir dengan sesuatu seperti ini di dalamnya:

public class KeyedCollection<TItem> : System.Collections.ObjectModel.KeyedCollection<TItem, TItem>
    where TItem : class
{
    public KeyedCollection() : base()
    {
    }

    public KeyedCollection(IEqualityComparer<TItem> comparer) : base(comparer)
    {
    }

    protected override TItem GetKeyForItem(TItem item)
    {
        return item;
    }
}

public class KeyedObjectCollection<TKey, TItem> : System.Collections.ObjectModel.KeyedCollection<TKey, TItem>
    where TItem : class, IKeyedObject<TKey>
    where TKey : struct
{
    public KeyedCollection() : base()
    {
    }

    protected override TItem GetKeyForItem(TItem item)
    {
        return item.Key;
    }
}

///<summary>
/// I almost always implement this explicitly so the only
/// classes that have access without some rigmarole
/// are generic collections built to be aware that an object
/// is keyed.
///</summary>
public interface IKeyedObject<TKey>
{
    TKey Key { get; }
}

10
2018-01-26 15:56



Jika Anda mengubah objek setelah disisipkan, hash itu mungkin telah berubah (ini terutama kemungkinan jika hashCode () telah ditimpa). Jika hash berubah, pencariannya di set akan gagal, karena Anda akan mencoba mencari objek yang di-hash di lokasi yang berbeda daripada disimpan.

Juga, Anda harus memastikan bahwa Anda telah menimpa hashCode dan setara dalam objek Anda jika Anda ingin mencari objek yang sama yang merupakan contoh berbeda.

Perhatikan bahwa ini semua untuk Java - Saya mengasumsikan C # memiliki sesuatu yang serupa, tetapi karena sudah beberapa tahun sejak saya menggunakan C #, saya akan membiarkan orang lain berbicara tentang kemampuannya.


4
2017-09-29 20:46



Saya membayangkan para desainer dari Set antarmuka dan HashSet kelas ingin memastikan bahwa remove(Object) metode yang didefinisikan pada Collection antarmuka juga berlaku untuk Set; metode ini mengembalikan boolean yang menunjukkan apakah objek berhasil dihapus. Jika para desainer ingin memberikan fungsionalitas dimana menghapus (Object) mengembalikan objek "sama" yang sudah ada di Set ini berarti tanda tangan metode yang berbeda.

Juga, mengingat bahwa objek yang dihapus secara logis sama dengan objek yang dilewatkan untuk menghapus (Objek) dapat diperdebatkan tentang nilai yang ditambahkan dalam mengembalikan objek yang terkandung. Namun, saya pernah mengalami masalah ini sebelumnya dan telah menggunakan Peta untuk memecahkan masalah.

Perhatikan bahwa di Java, a HashSet menggunakan a HashMap secara internal dan tidak ada overhead penyimpanan tambahan dalam menggunakan HashMap sebagai gantinya.


3
2017-09-29 21:01



Kenapa tidak pakai saja HashMap<X,X>? Ini persis apa yang Anda inginkan. Kerjakan saja .put(x,x) setiap kali dan kemudian Anda bisa mendapatkan elemen yang tersimpan sama dengan x dengan .get(x).


3
2017-09-13 22:18



Tampak pada saya seperti Anda sebenarnya mencari Map<X,Y>, di mana Y adalah tipe extra1.


(kata-kata kasar di bawah)

Metode equals dan hashCode mendefinisikan persamaan objek yang berarti. Kelas HashSet mengasumsikan bahwa jika dua objek sama seperti yang didefinisikan oleh Object.equals(Object) tidak ada perbedaan antara dua benda ini.

Saya akan pergi sejauh mengatakan bahwa jika object extra berarti, desain Anda tidak ideal.


1
2017-09-30 17:54



TERPECAHKAN. Berharap untuk menemukan elemen tampaknya sangat valid bagi saya, karena perwakilan yang digunakan untuk pencarian mungkin berbeda dari elemen yang ditemukan. Ini terutama benar jika elemen mengandung informasi kunci dan nilai, dan pembanding kesetaraan khusus membandingkan bagian kunci saja. Lihat contoh kode. Kode berisi komparator yang mengimplementasikan pencarian kustom dan yang menangkap elemen yang ditemukan. Ini membutuhkan instance dari komparator. Hapus referensi ke elemen yang ditemukan. Lakukan pencarian dengan cara Berisi. Akses elemen yang ditemukan. Waspadai masalah multithread saat berbagi instance pembanding.

using System;
using System.Collections.Generic;

namespace ConsoleApplication1 {

class Box
{
    public int Id;
    public string Name;
    public Box(int id, string name)
    {
        Id = id;
        Name = name;
    }
}

class BoxEq: IEqualityComparer<Box>
{
    public Box Element;

    public bool Equals(Box element, Box representative)
    {
        bool found = element.Id == representative.Id;
        if (found)
        {
            Element = element;
        }
        return found;
    }

    public int GetHashCode(Box box)
    {
        return box.Id.GetHashCode();
    }
}

class Program
{
    static void Main()
    {
        var boxEq = new BoxEq();
        var hashSet = new HashSet<Box>(boxEq);
        hashSet.Add(new Box(3, "Element 3"));
        var box5 = new Box(5, "Element 5");
        hashSet.Add(box5);
        var representative = new Box(5, "Representative 5");
        boxEq.Element = null;
        Console.WriteLine("Contains {0}: {1}", representative.Id, hashSet.Contains(representative));
        Console.WriteLine("Found id: {0}, name: {1}", boxEq.Element.Id, boxEq.Element.Name);
        Console.WriteLine("Press enter");
        Console.ReadLine();
    }
}

} // namespace

1
2018-03-11 07:30



Ini adalah kekhilafan dari perancang perpustakaan. Seperti yang saya sebutkan di bawah jawaban lain, metode ini telah ditambahkan .NET Framework 4.7.2 (dan .NET Core 2.0 sebelum itu); Lihat HashSet<T>.TryGetValue. Mengutip sumber:

/// <summary>
/// Searches the set for a given value and returns the equal value it finds, if any.
/// </summary>
/// <param name="equalValue">The value to search for.
/// </param>
/// <param name="actualValue">
/// The value from the set that the search found, or the default value
/// of <typeparamref name="T"/> when the search yielded no match.</param>
/// <returns>A value indicating whether the search was successful.</returns>
/// <remarks>
/// This can be useful when you want to reuse a previously stored reference instead of 
/// a newly constructed one (so that more sharing of references can occur) or to look up
/// a value that has more complete data than the value you currently have, although their
/// comparer functions indicate they are equal.
/// </remarks>
public bool TryGetValue(T equalValue, out T actualValue)

1
2017-07-07 07:53