Jak odzyskać rzeczywisty przedmiot z HashSet <T>?

86

Przeczytałem to pytanie, dlaczego nie jest to możliwe, ale nie znalazłem rozwiązania problemu.

Chciałbym pobrać element z platformy .NET HashSet<T>. Szukam metody, która miałaby taki podpis:

/// <summary>
/// Determines if this set contains an item equal to <paramref name="item"/>, 
/// according to the comparison mechanism that was used when the set was created. 
/// The set is not changed. If the set does contain an item equal to 
/// <paramref name="item"/>, then the item from the set is returned.
/// </summary>
bool TryGetItem<T>(T item, out T foundItem);

Przeszukanie zbioru pod kątem elementu taką metodą to O (1). Jedynym sposobem na pobranie elementu z a HashSet<T>jest wyliczenie wszystkich elementów, które są O (n).

Nie znalazłem innego rozwiązania tego problemu niż utworzenie własnego HashSet<T>lub użycie pliku Dictionary<K, V>. Masz inny pomysł?

Uwaga:
nie chcę sprawdzać, czy HashSet<T>zawiera element. Chcę uzyskać odniesienie do elementu, który jest przechowywany w pliku, HashSet<T>ponieważ muszę go zaktualizować (bez zastępowania go inną instancją). Element, do którego TryGetItemprzekażę, byłby równy (zgodnie z mechanizmem porównania, który przekazałem konstruktorowi), ale nie byłby to to samo odniesienie.

Francois C
źródło
1
Dlaczego nie użyć opcji Zawiera i nie zwrócić przekazanego elementu jako dane wejściowe?
Mathias
2
Jeśli chcesz wyszukać obiekt na podstawie wartości klucza, wówczas Dictionary <T> może być bardziej odpowiednią kolekcją do przechowywania go.
ThatBlairGuy
@ThatBlairGuy: Masz rację. Myślę, że zaimplementuję moją własną kolekcję zestawów, używając słownika wewnętrznie do przechowywania moich przedmiotów. Klucz będzie kodem HashCode elementu. Będę miał mniej więcej taką samą wydajność jak HashSet i zaoszczędzi mi to konieczności podawania klucza za każdym razem, gdy muszę dodać / usunąć / pobrać element z mojej kolekcji.
Francois C
2
@mathias Ponieważ hashset może zawierać element, który jest równy wejściu, ale w rzeczywistości nie jest taki sam. Na przykład możesz chcieć mieć zestaw skrótów typów odwołań, ale chcesz porównać zawartość, a nie odniesienie do równości.
Rzeczownik Verber

Odpowiedzi:

26

To, o co prosisz, zostało dodane do platformy .NET Core rok temu i niedawno zostało dodane do platformy .NET 4.7.2 :

W programie .NET Framework 4.7.2 dodaliśmy kilka interfejsów API do standardowych typów kolekcji, które umożliwią nowe funkcje w następujący sposób.
- „TryGetValue” jest dodawane do SortedSet i HashSet, aby dopasować wzorzec Try używany w innych typach kolekcji.

Podpis jest następujący (znajdujący się w .NET 4.7.2 i nowszych):

    //
    // Summary:
    //     Searches the set for a given value and returns the equal value it finds, if any.
    //
    // Parameters:
    //   equalValue:
    //     The value to search for.
    //
    //   actualValue:
    //     The value from the set that the search found, or the default value of T when
    //     the search yielded no match.
    //
    // Returns:
    //     A value indicating whether the search was successful.
    public bool TryGetValue(T equalValue, out T actualValue);

PS .: Jeśli jesteś zainteresowany, istnieje powiązana funkcja, którą dodają w przyszłości - HashSet.GetOrAdd (T).

Evdzhan Mustafa
źródło
65

W rzeczywistości jest to ogromne zaniedbanie w zestawie kolekcji. Potrzebny byłby albo słownik kluczy, albo zestaw HashSet, który umożliwia pobieranie odwołań do obiektów. Tak wielu ludzi prosiło o to, dlaczego nie zostanie naprawiony, jest poza mną.

Bez bibliotek innych firm najlepszym obejściem jest użycie Dictionary<T, T>kluczy identycznych z wartościami, ponieważ słownik przechowuje swoje wpisy jako tabelę skrótów. Pod względem wydajności jest taki sam jak HashSet, ale oczywiście marnuje pamięć (rozmiar wskaźnika na wpis).

Dictionary<T, T> myHashedCollection;
...
if(myHashedCollection.ContainsKey[item])
    item = myHashedCollection[item]; //replace duplicate
else
    myHashedCollection.Add(item, item); //add previously unknown item
...
//work with unique item
JPE
źródło
1
Sugerowałbym, aby klucze do jego słownika były tym, co obecnie umieścił w swoim EqualityComparer dla hashsetu. Uważam, że używanie EqualityComparer jest brudne, gdy tak naprawdę nie mówisz, że elementy są równe (w przeciwnym razie możesz po prostu użyć elementu, który utworzyłeś do celów porównania). Zrobiłbym klasę / strukturę, która reprezentuje klucz. Odbywa się to oczywiście kosztem większej pamięci.
Ed T
1
Ponieważ klucz jest przechowywany w Value, sugeruję użycie kolekcji dziedziczonej po KeyedCollection zamiast Dictionary. msdn.microsoft.com/en-us/library/ms132438(v=vs.110).aspx
Odmowa dostępu
11

Ta metoda została dodana do .NET Framework 4.7.2 (i .NET Core 2.0 przed nią); zobacz HashSet<T>.TryGetValue. Cytując źródło :

/// <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)
Douglas
źródło
1
Jak również w przypadku SortedSet .
nawfal
4

A co z przeciążeniem funkcji porównującej równość ciągów:

  class StringEqualityComparer : IEqualityComparer<String>
{
    public string val1;
    public bool Equals(String s1, String s2)
    {
        if (!s1.Equals(s2)) return false;
        val1 = s1;
        return true;
    }

    public int GetHashCode(String s)
    {
        return s.GetHashCode();
    }
}
public static class HashSetExtension
{
    public static bool TryGetValue(this HashSet<string> hs, string value, out string valout)
    {
        if (hs.Contains(value))
        {
            valout=(hs.Comparer as StringEqualityComparer).val1;
            return true;
        }
        else
        {
            valout = null;
            return false;
        }
    }
}

A następnie zadeklaruj HashSet jako:

HashSet<string> hs = new HashSet<string>(new StringEqualityComparer());
mp666
źródło
Chodzi o zarządzanie pamięcią - zwracanie rzeczywistego elementu, który jest w skrócie, a nie identycznej kopii. Więc w powyższym kodzie znajdujemy ciąg o tej samej zawartości, a następnie zwracamy odniesienie do this. W przypadku strun jest to podobne do tego, co robi staż.
mp666,
@zumalifeguard @ mp666 nie ma gwarancji, że będzie działać tak, jak jest. Wymagałoby to kogoś, kto utworzyłby instancję, HashSetaby udostępnił określony konwerter wartości. Optymalnym rozwiązaniem byłoby TryGetValueprzekazanie nowej instancji wyspecjalizowanej StringEqualityComparer(w przeciwnym razie as StringEqualityComparermogłoby to skutkować wartością null powodującą .val1zgłoszenie dostępu do właściwości). W ten sposób StringEqualityComparer może stać się zagnieżdżoną klasą prywatną w ramach HashSetExtension. Co więcej, w przypadku zastąpionego modułu porównującego równość StringEqualityComparer powinien wywołać wartość domyślną.
Graeme Wicksted
musisz zadeklarować swój HashSet jako: HashSet <string> valueCash = new HashSet <string> (new StringEqualityComparer ())
mp666
1
Brudny hack. Wiem, jak to działa, ale jest leniwy, po prostu sprawia, że ​​działa to rodzaj rozwiązania
M.kazem Akhgary
2

Ok, więc możesz to zrobić w ten sposób

YourObject x = yourHashSet.Where(w => w.Name.Contains("strin")).FirstOrDefault();

Ma to na celu uzyskanie nowej instancji wybranego obiektu. Aby zaktualizować swój obiekt, powinieneś użyć:

yourHashSet.Where(w => w.Name.Contains("strin")).FirstOrDefault().MyProperty = "something";
Vulovic Vukasin
źródło
To ciekawy sposób, po prostu musisz zawinąć drugą próbę - tak, że jeśli szukasz czegoś, czego nie ma na liście, otrzymasz NullReferenceExpection. Ale to krok we właściwym kierunku?
Piotr Kula
11
LINQ przechodzi przez kolekcję w pętli foreach, tj. Czas wyszukiwania O (n). Chociaż jest to rozwiązanie problemu, w pewnym sensie niweczy cel używania HashSet w pierwszej kolejności.
Niklas Ekman
2

Kolejna sztuczka zrobi odbicie, uzyskując dostęp do wewnętrznej funkcji InternalIndexOfHashSet. Pamiętaj, że nazwy pól są zakodowane na stałe, więc jeśli zmienią się one w nadchodzących wersjach .NET, to się zepsuje.

Uwaga: Jeśli używasz Mono, powinieneś zmienić nazwę pola z m_slotsna _slots.

internal static class HashSetExtensions<T>
{
    public delegate bool GetValue(HashSet<T> source, T equalValue, out T actualValue);

    public static GetValue TryGetValue { get; }

    static HashSetExtensions() {
        var targetExp = Expression.Parameter(typeof(HashSet<T>), "target");
        var itemExp   = Expression.Parameter(typeof(T), "item");
        var actualValueExp = Expression.Parameter(typeof(T).MakeByRefType(), "actualValueExp");

        var indexVar = Expression.Variable(typeof(int), "index");
        // ReSharper disable once AssignNullToNotNullAttribute
        var indexExp = Expression.Call(targetExp, typeof(HashSet<T>).GetMethod("InternalIndexOf", BindingFlags.NonPublic | BindingFlags.Instance), itemExp);

        var truePart = Expression.Block(
            Expression.Assign(
                actualValueExp, Expression.Field(
                    Expression.ArrayAccess(
                        // ReSharper disable once AssignNullToNotNullAttribute
                        Expression.Field(targetExp, typeof(HashSet<T>).GetField("m_slots", BindingFlags.NonPublic | BindingFlags.Instance)), indexVar),
                    "value")),
            Expression.Constant(true));

        var falsePart = Expression.Constant(false);

        var block = Expression.Block(
            new[] { indexVar },
            Expression.Assign(indexVar, indexExp),
            Expression.Condition(
                Expression.GreaterThanOrEqual(indexVar, Expression.Constant(0)),
                truePart,
                falsePart));

        TryGetValue = Expression.Lambda<GetValue>(block, targetExp, itemExp, actualValueExp).Compile();
    }
}

public static class Extensions
{
    public static bool TryGetValue2<T>(this HashSet<T> source, T equalValue,  out T actualValue) {
        if (source.Count > 0) {
            if (HashSetExtensions<T>.TryGetValue(source, equalValue, out actualValue)) {
                return true;
            }
        }
        actualValue = default;
        return false;
    }
}

Test:

var x = new HashSet<int> { 1, 2, 3 };
if (x.TryGetValue2(1, out var value)) {
    Console.WriteLine(value);
}
Lukas
źródło
1

SortedSet prawdopodobnie miałby czas wyszukiwania O (log n) w tych okolicznościach, jeśli jest to opcja. Wciąż nie O (1), ale przynajmniej lepiej.

Erik Dietrich
źródło
1

Zmodyfikowana implementacja odpowiedzi @ mp666, dzięki czemu może być używana dla dowolnego typu HashSet i umożliwia przesłonięcie domyślnej funkcji porównującej równość.

public interface IRetainingComparer<T> : IEqualityComparer<T>
{
    T Key { get; }
    void ClearKeyCache();
}

/// <summary>
/// An <see cref="IEqualityComparer{T}"/> that retains the last key that successfully passed <see cref="IEqualityComparer{T}.Equals(T,T)"/>.
/// This class relies on the fact that <see cref="HashSet{T}"/> calls the <see cref="IEqualityComparer{T}.Equals(T,T)"/> with the first parameter
/// being an existing element and the second parameter being the one passed to the initiating call to <see cref="HashSet{T}"/> (eg. <see cref="HashSet{T}.Contains(T)"/>).
/// </summary>
/// <typeparam name="T">The type of object being compared.</typeparam>
/// <remarks>This class is thread-safe but may should not be used with any sort of parallel access (PLINQ).</remarks>
public class RetainingEqualityComparerObject<T> : IRetainingComparer<T> where T : class
{
    private readonly IEqualityComparer<T> _comparer;

    [ThreadStatic]
    private static WeakReference<T> _retained;

    public RetainingEqualityComparerObject(IEqualityComparer<T> comparer)
    {
        _comparer = comparer;
    }

    /// <summary>
    /// The retained instance on side 'a' of the <see cref="Equals"/> call which successfully met the equality requirement agains side 'b'.
    /// </summary>
    /// <remarks>Uses a <see cref="WeakReference{T}"/> so unintended memory leaks are not encountered.</remarks>
    public T Key
    {
        get
        {
            T retained;
            return _retained == null ? null : _retained.TryGetTarget(out retained) ? retained : null;
        }
    }


    /// <summary>
    /// Sets the retained <see cref="Key"/> to the default value.
    /// </summary>
    /// <remarks>This should be called prior to performing an operation that calls <see cref="Equals"/>.</remarks>
    public void ClearKeyCache()
    {
        _retained = _retained ?? new WeakReference<T>(null);
        _retained.SetTarget(null);
    }

    /// <summary>
    /// Test two objects of type <see cref="T"/> for equality retaining the object if successful.
    /// </summary>
    /// <param name="a">An instance of <see cref="T"/>.</param>
    /// <param name="b">A second instance of <see cref="T"/> to compare against <paramref name="a"/>.</param>
    /// <returns>True if <paramref name="a"/> and <paramref name="b"/> are equal, false otherwise.</returns>
    public bool Equals(T a, T b)
    {
        if (!_comparer.Equals(a, b))
        {
            return false;
        }

        _retained = _retained ?? new WeakReference<T>(null);
        _retained.SetTarget(a);
        return true;
    }

    /// <summary>
    /// Gets the hash code value of an instance of <see cref="T"/>.
    /// </summary>
    /// <param name="o">The instance of <see cref="T"/> to obtain a hash code from.</param>
    /// <returns>The hash code value from <paramref name="o"/>.</returns>
    public int GetHashCode(T o)
    {
        return _comparer.GetHashCode(o);
    }
}

/// <summary>
/// An <see cref="IEqualityComparer{T}"/> that retains the last key that successfully passed <see cref="IEqualityComparer{T}.Equals(T,T)"/>.
/// This class relies on the fact that <see cref="HashSet{T}"/> calls the <see cref="IEqualityComparer{T}.Equals(T,T)"/> with the first parameter
/// being an existing element and the second parameter being the one passed to the initiating call to <see cref="HashSet{T}"/> (eg. <see cref="HashSet{T}.Contains(T)"/>).
/// </summary>
/// <typeparam name="T">The type of object being compared.</typeparam>
/// <remarks>This class is thread-safe but may should not be used with any sort of parallel access (PLINQ).</remarks>
public class RetainingEqualityComparerStruct<T> : IRetainingComparer<T> where T : struct 
{
    private readonly IEqualityComparer<T> _comparer;

    [ThreadStatic]
    private static T _retained;

    public RetainingEqualityComparerStruct(IEqualityComparer<T> comparer)
    {
        _comparer = comparer;
    }

    /// <summary>
    /// The retained instance on side 'a' of the <see cref="Equals"/> call which successfully met the equality requirement agains side 'b'.
    /// </summary>
    public T Key => _retained;


    /// <summary>
    /// Sets the retained <see cref="Key"/> to the default value.
    /// </summary>
    /// <remarks>This should be called prior to performing an operation that calls <see cref="Equals"/>.</remarks>
    public void ClearKeyCache()
    {
        _retained = default(T);
    }

    /// <summary>
    /// Test two objects of type <see cref="T"/> for equality retaining the object if successful.
    /// </summary>
    /// <param name="a">An instance of <see cref="T"/>.</param>
    /// <param name="b">A second instance of <see cref="T"/> to compare against <paramref name="a"/>.</param>
    /// <returns>True if <paramref name="a"/> and <paramref name="b"/> are equal, false otherwise.</returns>
    public bool Equals(T a, T b)
    {
        if (!_comparer.Equals(a, b))
        {
            return false;
        }

        _retained = a;
        return true;
    }

    /// <summary>
    /// Gets the hash code value of an instance of <see cref="T"/>.
    /// </summary>
    /// <param name="o">The instance of <see cref="T"/> to obtain a hash code from.</param>
    /// <returns>The hash code value from <paramref name="o"/>.</returns>
    public int GetHashCode(T o)
    {
        return _comparer.GetHashCode(o);
    }
}

/// <summary>
/// Provides TryGetValue{T} functionality similar to that of <see cref="IDictionary{TKey,TValue}"/>'s implementation.
/// </summary>
public class ExtendedHashSet<T> : HashSet<T>
{
    /// <summary>
    /// This class is guaranteed to wrap the <see cref="IEqualityComparer{T}"/> with one of the <see cref="IRetainingComparer{T}"/>
    /// implementations so this property gives convenient access to the interfaced comparer.
    /// </summary>
    private IRetainingComparer<T> RetainingComparer => (IRetainingComparer<T>)Comparer;

    /// <summary>
    /// Creates either a <see cref="RetainingEqualityComparerStruct{T}"/> or <see cref="RetainingEqualityComparerObject{T}"/>
    /// depending on if <see cref="T"/> is a reference type or a value type.
    /// </summary>
    /// <param name="comparer">(optional) The <see cref="IEqualityComparer{T}"/> to wrap. This will be set to <see cref="EqualityComparer{T}.Default"/> if none provided.</param>
    /// <returns>An instance of <see cref="IRetainingComparer{T}"/>.</returns>
    private static IRetainingComparer<T> Create(IEqualityComparer<T> comparer = null)
    {
        return (IRetainingComparer<T>) (typeof(T).IsValueType ? 
            Activator.CreateInstance(typeof(RetainingEqualityComparerStruct<>)
                .MakeGenericType(typeof(T)), comparer ?? EqualityComparer<T>.Default)
            :
            Activator.CreateInstance(typeof(RetainingEqualityComparerObject<>)
                .MakeGenericType(typeof(T)), comparer ?? EqualityComparer<T>.Default));
    }

    public ExtendedHashSet() : base(Create())
    {
    }

    public ExtendedHashSet(IEqualityComparer<T> comparer) : base(Create(comparer))
    {
    }

    public ExtendedHashSet(IEnumerable<T> collection) : base(collection, Create())
    {
    }

    public ExtendedHashSet(IEnumerable<T> collection, IEqualityComparer<T> comparer) : base(collection, Create(comparer))
    {
    }

    /// <summary>
    /// Attempts to find a key in the <see cref="HashSet{T}"/> and, if found, places the instance in <paramref name="original"/>.
    /// </summary>
    /// <param name="value">The key used to search the <see cref="HashSet{T}"/>.</param>
    /// <param name="original">
    /// The matched instance from the <see cref="HashSet{T}"/> which is not neccessarily the same as <paramref name="value"/>.
    /// This will be set to null for reference types or default(T) for value types when no match found.
    /// </param>
    /// <returns>True if a key in the <see cref="HashSet{T}"/> matched <paramref name="value"/>, False if no match found.</returns>
    public bool TryGetValue(T value, out T original)
    {
        var comparer = RetainingComparer;
        comparer.ClearKeyCache();

        if (Contains(value))
        {
            original = comparer.Key;
            return true;
        }

        original = default(T);
        return false;
    }
}

public static class HashSetExtensions
{
    /// <summary>
    /// Attempts to find a key in the <see cref="HashSet{T}"/> and, if found, places the instance in <paramref name="original"/>.
    /// </summary>
    /// <param name="hashSet">The instance of <see cref="HashSet{T}"/> extended.</param>
    /// <param name="value">The key used to search the <see cref="HashSet{T}"/>.</param>
    /// <param name="original">
    /// The matched instance from the <see cref="HashSet{T}"/> which is not neccessarily the same as <paramref name="value"/>.
    /// This will be set to null for reference types or default(T) for value types when no match found.
    /// </param>
    /// <returns>True if a key in the <see cref="HashSet{T}"/> matched <paramref name="value"/>, False if no match found.</returns>
    /// <exception cref="ArgumentNullException">If <paramref name="hashSet"/> is null.</exception>
    /// <exception cref="ArgumentException">
    /// If <paramref name="hashSet"/> does not have a <see cref="HashSet{T}.Comparer"/> of type <see cref="IRetainingComparer{T}"/>.
    /// </exception>
    public static bool TryGetValue<T>(this HashSet<T> hashSet, T value, out T original)
    {
        if (hashSet == null)
        {
            throw new ArgumentNullException(nameof(hashSet));
        }

        if (hashSet.Comparer.GetType().IsInstanceOfType(typeof(IRetainingComparer<T>)))
        {
            throw new ArgumentException($"HashSet must have an equality comparer of type '{nameof(IRetainingComparer<T>)}' to use this functionality", nameof(hashSet));
        }

        var comparer = (IRetainingComparer<T>)hashSet.Comparer;
        comparer.ClearKeyCache();

        if (hashSet.Contains(value))
        {
            original = comparer.Key;
            return true;
        }

        original = default(T);
        return false;
    }
}
Graeme Wicksted
źródło
1
Ponieważ używasz metody rozszerzenia Linq Enumerable.Contains, wyliczy ona wszystkie elementy zestawu i porówna je, tracąc wszelkie korzyści, jakie zapewnia implementacja skrótu zestawu. Wtedy równie dobrze możesz po prostu napisać set.SingleOrDefault(e => set.Comparer.Equals(e, obj)), który ma takie same cechy zachowania i wydajności jak Twoje rozwiązanie.
Daniel AA Pelsmaeker
@Virtlink Dobry chwyt - masz całkowitą rację. Zmodyfikuję odpowiedź.
Graeme Wicksted
Jeśli jednak zapakowałbyś HashSet, który używa twojego komparatora wewnętrznie, zadziałałoby. W ten sposób: Utillib / ExtHashSet
Daniel AA Pelsmaeker
@Virtlink dziękuję! Skończyło się na tym, że zawijam HashSet jako jedną opcję, ale zapewniam elementy porównujące i metodę rozszerzenia dla dodatkowej wszechstronności. Jest teraz bezpieczny dla wątków i nie spowoduje wycieku pamięci ... ale zawiera trochę więcej kodu, niż się spodziewałem!
Graeme Wicksted
@Francois Pisanie powyższego kodu było bardziej ćwiczeniem polegającym na znalezieniu „optymalnego” rozwiązania czasu / pamięci; jednak nie sugeruję, abyś korzystał z tej metody. Używanie Dictionary <T, T> z niestandardowym IEqualityComparer jest znacznie prostsze i przyszłościowe!
Graeme Wicksted
-2

HashSet ma metodę Contains (T) .

Możesz określić IEqualityComparer, jeśli potrzebujesz niestandardowej metody porównania (np. Przechowuj obiekt osoby, ale użyj numeru SSN do porównania równości).

Philipp Schmid
źródło
-11

Możesz również użyć metody ToList () i zastosować do niej indeksator.

HashSet<string> mySet = new HashSet();
mySet.Add("mykey");
string key = mySet.toList()[0];
Eric
źródło
Nie jestem pewien, dlaczego straciliście głosy, kiedy zastosowałem tę logikę, zadziałało. Musiałem wyodrębnić wartości ze struktury, która rozpoczęła się od Dictionary <string, ISet <String>>, gdzie ISet zawierał x liczbę wartości. Najbardziej bezpośrednim sposobem uzyskania tych wartości było zapętlenie przez słownik, wyciąganie klucza i wartości ISet. Następnie przejrzałem ISet, aby wyświetlić poszczególne wartości. Nie jest elegancki, ale zadziałał.
j.hull