Gleichzeitiges HashSet <T> in .NET Framework?

151

Ich habe die folgende Klasse.

class Test{
    public HashSet<string> Data = new HashSet<string>();
}

Ich muss das Feld "Daten" aus verschiedenen Threads ändern, daher möchte ich einige Meinungen zu meiner aktuellen thread-sicheren Implementierung haben.

class Test{
    public HashSet<string> Data = new HashSet<string>();

    public void Add(string Val){
            lock(Data) Data.Add(Val);
    }

    public void Remove(string Val){
            lock(Data) Data.Remove(Val);
    }
}

Gibt es eine bessere Lösung, um direkt zum Feld zu gelangen und es vor dem gleichzeitigen Zugriff durch mehrere Threads zu schützen?

Kukab
quelle
Wie wäre es mit einer der Sammlungen unterSystem.Collections.Concurrent
I4V
8
Machen Sie es natürlich privat.
Hans Passant
3
Aus Sicht der Parallelität sehe ich nicht viel Falsches an dem, was Sie getan haben, außer dass das Datenfeld öffentlich ist! Wenn dies ein Problem darstellt, können Sie mit ReaderWriterLockSlim eine bessere Leseleistung erzielen. msdn.microsoft.com/en-us/library/…
Allan Elder
@AllanElder ReaderWriterLockist hilfreich (effizient), wenn mehrere Leser und ein einzelner Schreiber vorhanden sind. Wir müssen wissen, ob dies bei OP der Fall ist
Sriram Sakthivel
2
Die aktuelle Implementierung ist nicht wirklich "gleichzeitig" :) Es ist nur threadsicher.
undefiniert

Antworten:

164

Ihre Implementierung ist korrekt. Das .NET Framework bietet leider keinen integrierten gleichzeitigen Hashset-Typ. Es gibt jedoch einige Problemumgehungen.

ConcurrentDictionary (empfohlen)

Diese erste besteht darin, die Klasse ConcurrentDictionary<TKey, TValue>im Namespace zu verwenden System.Collections.Concurrent. In diesem Fall ist der Wert sinnlos, sodass wir ein einfaches byte(1 Byte im Speicher) verwenden können.

private ConcurrentDictionary<string, byte> _data;

Dies ist die empfohlene Option, da der Typ threadsicher ist und Ihnen dieselben Vorteile bietet, als HashSet<T>wenn ein Ausnahmeschlüssel und ein Wert unterschiedliche Objekte sind.

Quelle: Soziale MSDN

ConcurrentBag

Wenn Ihnen die doppelten Einträge nichts ausmachen, können Sie die Klasse ConcurrentBag<T>im selben Namespace wie die vorherige Klasse verwenden.

private ConcurrentBag<string> _data;

Selbstimplementierung

Schließlich können Sie wie Sie Ihren eigenen Datentyp implementieren, indem Sie Sperren oder andere Methoden verwenden, die .NET Ihnen bietet, um threadsicher zu sein. Hier ist ein gutes Beispiel: So implementieren Sie ConcurrentHashSet in .Net

Der einzige Nachteil dieser Lösung besteht darin, dass der Typ HashSet<T>selbst für Lesevorgänge keinen offiziell gleichzeitigen Zugriff bietet.

Ich zitiere den Code des verlinkten Beitrags (ursprünglich von Ben Mosher geschrieben ).

using System;
using System.Collections.Generic;
using System.Threading;

namespace BlahBlah.Utilities
{
    public class ConcurrentHashSet<T> : IDisposable
    {
        private readonly ReaderWriterLockSlim _lock = new ReaderWriterLockSlim(LockRecursionPolicy.SupportsRecursion);
        private readonly HashSet<T> _hashSet = new HashSet<T>();

        #region Implementation of ICollection<T> ...ish
        public bool Add(T item)
        {
            _lock.EnterWriteLock();
            try
            {
                return _hashSet.Add(item);
            }
            finally
            {
                if (_lock.IsWriteLockHeld) _lock.ExitWriteLock();
            }
        }

        public void Clear()
        {
            _lock.EnterWriteLock();
            try
            {
                _hashSet.Clear();
            }
            finally
            {
                if (_lock.IsWriteLockHeld) _lock.ExitWriteLock();
            }
        }

        public bool Contains(T item)
        {
            _lock.EnterReadLock();
            try
            {
                return _hashSet.Contains(item);
            }
            finally
            {
                if (_lock.IsReadLockHeld) _lock.ExitReadLock();
            }
        }

        public bool Remove(T item)
        {
            _lock.EnterWriteLock();
            try
            {
                return _hashSet.Remove(item);
            }
            finally
            {
                if (_lock.IsWriteLockHeld) _lock.ExitWriteLock();
            }
        }

        public int Count
        {
            get
            {
                _lock.EnterReadLock();
                try
                {
                    return _hashSet.Count;
                }
                finally
                {
                    if (_lock.IsReadLockHeld) _lock.ExitReadLock();
                }
            }
        }
        #endregion

        #region Dispose
        public void Dispose()
        {
            Dispose(true);
            GC.SuppressFinalize(this);
        }
        protected virtual void Dispose(bool disposing)
        {
            if (disposing)
                if (_lock != null)
                    _lock.Dispose();
        }
        ~ConcurrentHashSet()
        {
            Dispose(false);
        }
        #endregion
    }
}

BEARBEITEN: Verschieben Sie die Eingangsverriegelungsmethoden außerhalb der tryBlöcke, da sie eine Ausnahme auslösen und die in den finallyBlöcken enthaltenen Anweisungen ausführen können .

ZenLulz
quelle
8
Ein Wörterbuch mit Junk-Werten ist eine Liste
Ralf
44
@Ralf Nun, es ist ein Set, keine Liste, da es ungeordnet ist.
Servy
10
Laut dem relativ kurzen Dokument von MSDN zu "Sammlungen und Synchronisation (Thread-Sicherheit)" können Klassen in System.Collections und zugehörigen Namespaces von mehreren Threads sicher gelesen werden. Dies bedeutet, dass HashSet von mehreren Threads sicher gelesen werden kann.
Hank Schultz
7
@Oliver, eine Referenz verwendet viel mehr Speicher pro Eintrag, selbst wenn es sich um eine nullReferenz handelt (die Referenz benötigt 4 Byte in einer 32-Bit-Laufzeit und 8 Byte in einer 64-Bit-Laufzeit). Daher kann die Verwendung von a byte, einer leeren Struktur oder ähnlichem den Speicherbedarf verringern (oder nicht, wenn die Laufzeit die Daten an nativen Speichergrenzen ausrichtet, um einen schnelleren Zugriff zu ermöglichen).
Lucero
4
Die Selbstimplementierung ist kein ConcurrentHashSet, sondern ein ThreadSafeHashSet. Es gibt einen großen Unterschied zwischen diesen beiden und deshalb hat Micorosft SynchronizedCollections aufgegeben (die Leute haben es falsch verstanden). Um "Concurrent" -Operationen wie GetOrAdd usw. zu sein, sollten sie implementiert werden (wie das Wörterbuch), da sonst die Parallelität nicht ohne zusätzliche Sperren sichergestellt werden kann. Wenn Sie jedoch zusätzliche Sperren außerhalb der Klasse benötigen, warum verwenden Sie dann nicht von Anfang an ein einfaches HashSet?
George Mavritsakis
36

Anstatt ein zu verpacken ConcurrentDictionaryoder ein zu sperren, habe HashSetich ein aktuelles ConcurrentHashSetbasierend auf erstellt ConcurrentDictionary.

Diese Implementierung unterstützt grundlegende Operationen pro Element ohne HashSetfestgelegte Operationen, da sie in gleichzeitigen Szenarien weniger sinnvoll sind. IMO:

var concurrentHashSet = new ConcurrentHashSet<string>(
    new[]
    {
        "hamster",
        "HAMster",
        "bar",
    },
    StringComparer.OrdinalIgnoreCase);

concurrentHashSet.TryRemove("foo");

if (concurrentHashSet.Contains("BAR"))
{
    Console.WriteLine(concurrentHashSet.Count);
}

Ausgabe: 2

Sie können es von NuGet hier bekommen und die Quelle auf GitHub hier sehen .

i3arnon
quelle
3
Dies sollte die akzeptierte Antwort sein, großartige Implementierung
Grinsender
Sollte Add nicht in TryAdd umbenannt werden, damit es mit ConcurrentDictionary übereinstimmt ?
Neo
8
@Neo Nein ... weil absichtlich die HashSet <T> -Semantik verwendet wird , bei der Sie Add aufrufen und ein Boolescher Wert zurückgegeben wird , der angibt, ob das Element hinzugefügt wurde (true) oder bereits vorhanden war (false). msdn.microsoft.com/en-us/library/bb353005(v=vs.110).aspx
G-Mac
Sollte es nicht implementieren, dass die ISet<T>Schnittstelle bo tatsächlich der HashSet<T>Semantik entspricht?
Nekromant
1
@Nekromancer Wie ich in der Antwort sagte, halte ich es nicht für sinnvoll, diese festgelegten Methoden in einer gleichzeitigen Implementierung bereitzustellen. OverlapsBeispielsweise müsste entweder die Instanz während des gesamten Laufs gesperrt werden oder eine Antwort bereitgestellt werden, die möglicherweise bereits falsch ist. Beide Optionen sind schlechte IMO (und können von Verbrauchern extern hinzugefügt werden).
i3arnon
21

Da es niemand anderes erwähnt hat, werde ich einen alternativen Ansatz anbieten, der für Ihren speziellen Zweck geeignet sein kann oder nicht:

Unveränderliche Microsoft-Sammlungen

Aus einem Blogbeitrag des dahinter stehenden MS-Teams:

Während das gleichzeitige Erstellen und Ausführen einfacher als je zuvor ist, besteht immer noch eines der grundlegenden Probleme: der veränderbare gemeinsame Zustand. Das Lesen aus mehreren Threads ist normalerweise sehr einfach, aber sobald der Status aktualisiert werden muss, wird es viel schwieriger, insbesondere bei Designs, die gesperrt werden müssen.

Eine Alternative zum Sperren ist die Verwendung eines unveränderlichen Zustands. Unveränderliche Datenstrukturen ändern sich garantiert nie und können somit frei zwischen verschiedenen Threads übertragen werden, ohne sich Gedanken darüber machen zu müssen, jemand anderem auf die Zehen zu treten.

Dieses Design schafft jedoch ein neues Problem: Wie verwalten Sie Statusänderungen, ohne jedes Mal den gesamten Status zu kopieren? Dies ist besonders schwierig, wenn es sich um Sammlungen handelt.

Hier kommen unveränderliche Sammlungen ins Spiel.

Diese Sammlungen umfassen ImmutableHashSet <T> und ImmutableList <T> .

Performance

Da die unveränderlichen Sammlungen darunter liegende Baumdatenstrukturen verwenden, um die gemeinsame Nutzung von Strukturen zu ermöglichen, unterscheiden sich ihre Leistungsmerkmale von veränderlichen Sammlungen. Beim Vergleich mit einer veränderlichen Sammlung von Sperren hängen die Ergebnisse von Sperrenkonflikten und Zugriffsmustern ab. Aus einem anderen Blog-Beitrag über die unveränderlichen Sammlungen:

F: Ich habe gehört, dass unveränderliche Sammlungen langsam sind. Sind diese anders? Kann ich sie verwenden, wenn Leistung oder Speicher wichtig sind?

A: Diese unveränderlichen Sammlungen wurden stark optimiert, um wettbewerbsfähige Leistungsmerkmale für die veränderlichen Sammlungen zu erzielen und gleichzeitig die Speicherfreigabe auszugleichen. In einigen Fällen sind sie sowohl algorithmisch als auch in tatsächlicher Zeit fast so schnell wie die veränderlichen Sammlungen, manchmal sogar schneller, während sie in anderen Fällen algorithmisch komplexer sind. In vielen Fällen ist der Unterschied jedoch vernachlässigbar. Im Allgemeinen sollten Sie den einfachsten Code verwenden, um die Aufgabe zu erledigen, und dann die Leistung nach Bedarf einstellen. Die unveränderlichen Sammlungen helfen Ihnen beim Schreiben von einfachem Code, insbesondere wenn die Thread-Sicherheit berücksichtigt werden muss.

Mit anderen Worten, in vielen Fällen wird der Unterschied nicht spürbar und Sie sollten sich für die einfachere Wahl entscheiden - die für gleichzeitige Sets verwendet werden sollte ImmutableHashSet<T>, da Sie keine veränderbare veränderbare Locking-Implementierung haben! :-)

Søren Boisen
quelle
1
ImmutableHashSet<T>hilft nicht viel, wenn Sie beabsichtigen, den freigegebenen Status von mehreren Threads zu aktualisieren, oder fehlt mir hier etwas?
Tugberk
7
@ Tugberk Ja und nein. Da das Set unveränderlich ist, müssen Sie den Verweis darauf aktualisieren, was Ihnen bei der Sammlung selbst nicht hilft. Die gute Nachricht ist, dass Sie das komplexe Problem der Aktualisierung einer gemeinsam genutzten Datenstruktur von mehreren Threads auf das viel einfachere Problem der Aktualisierung einer gemeinsam genutzten Referenz reduziert haben. Die Bibliothek bietet Ihnen die ImmutableInterlocked.Update- Methode, die Ihnen dabei hilft.
Søren Boisen
1
@ SørenBoisenjust las über unveränderliche Sammlungen und versuchte herauszufinden, wie man sie threadsicher verwendet. ImmutableInterlocked.Updatescheint das fehlende Glied zu sein. Danke dir!
xneg
4

Der schwierige Teil beim ISet<T>gleichzeitigen Erstellen besteht darin, dass die festgelegten Methoden (Vereinigung, Schnittmenge, Differenz) iterativer Natur sind. Zumindest müssen Sie alle n Mitglieder eines der an der Operation beteiligten Sätze durchlaufen, während Sie beide Sätze sperren.

Sie verlieren die Vorteile von a, ConcurrentDictionary<T,byte>wenn Sie den gesamten Satz während der Iteration sperren müssen. Ohne Sperren sind diese Vorgänge nicht threadsicher.

Angesichts des zusätzlichen Overheads von ConcurrentDictionary<T,byte>ist es wahrscheinlich klüger, nur das geringere Gewicht zu verwenden HashSet<T>und alles in Schlössern zu umgeben.

Wenn Sie die festgelegten Operationen nicht benötigen, verwenden Sie ConcurrentDictionary<T,byte>und verwenden Sie sie nur default(byte)als Wert, wenn Sie Schlüssel hinzufügen.

Rugby
quelle
2

Ich bevorzuge Komplettlösungen, deshalb habe ich Folgendes getan: Wohlgemerkt, meine Zählung wird auf eine andere Weise implementiert, da ich nicht verstehe, warum es verboten sein sollte, das Hashset zu lesen, während versucht wird, seine Werte zu zählen.

@ Zen, Danke, dass du damit angefangen hast.

[DebuggerDisplay("Count = {Count}")]
[Serializable]
public class ConcurrentHashSet<T> : ICollection<T>, ISet<T>, ISerializable, IDeserializationCallback
{
    private readonly ReaderWriterLockSlim _lock = new ReaderWriterLockSlim(LockRecursionPolicy.SupportsRecursion);

    private readonly HashSet<T> _hashSet = new HashSet<T>();

    public ConcurrentHashSet()
    {
    }

    public ConcurrentHashSet(IEqualityComparer<T> comparer)
    {
        _hashSet = new HashSet<T>(comparer);
    }

    public ConcurrentHashSet(IEnumerable<T> collection)
    {
        _hashSet = new HashSet<T>(collection);
    }

    public ConcurrentHashSet(IEnumerable<T> collection, IEqualityComparer<T> comparer)
    {
        _hashSet = new HashSet<T>(collection, comparer);
    }

    protected ConcurrentHashSet(SerializationInfo info, StreamingContext context)
    {
        _hashSet = new HashSet<T>();

        // not sure about this one really...
        var iSerializable = _hashSet as ISerializable;
        iSerializable.GetObjectData(info, context);
    }

    #region Dispose

    public void Dispose()
    {
        Dispose(true);
        GC.SuppressFinalize(this);
    }

    protected virtual void Dispose(bool disposing)
    {
        if (disposing)
            if (_lock != null)
                _lock.Dispose();
    }

    public IEnumerator<T> GetEnumerator()
    {
        return _hashSet.GetEnumerator();
    }

    ~ConcurrentHashSet()
    {
        Dispose(false);
    }

    public void OnDeserialization(object sender)
    {
        _hashSet.OnDeserialization(sender);
    }

    public void GetObjectData(SerializationInfo info, StreamingContext context)
    {
        _hashSet.GetObjectData(info, context);
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }

    #endregion

    public void Add(T item)
    {
        _lock.EnterWriteLock();
        try
        {
            _hashSet.Add(item);
        }
        finally
        {
            if(_lock.IsWriteLockHeld) _lock.ExitWriteLock();
        }
    }

    public void UnionWith(IEnumerable<T> other)
    {
        _lock.EnterWriteLock();
        _lock.EnterReadLock();
        try
        {
            _hashSet.UnionWith(other);
        }
        finally
        {
            if (_lock.IsWriteLockHeld) _lock.ExitWriteLock();
            if (_lock.IsReadLockHeld) _lock.ExitReadLock();
        }
    }

    public void IntersectWith(IEnumerable<T> other)
    {
        _lock.EnterWriteLock();
        _lock.EnterReadLock();
        try
        {
            _hashSet.IntersectWith(other);
        }
        finally
        {
            if (_lock.IsWriteLockHeld) _lock.ExitWriteLock();
            if (_lock.IsReadLockHeld) _lock.ExitReadLock();
        }
    }

    public void ExceptWith(IEnumerable<T> other)
    {
        _lock.EnterWriteLock();
        _lock.EnterReadLock();
        try
        {
            _hashSet.ExceptWith(other);
        }
        finally
        {
            if (_lock.IsWriteLockHeld) _lock.ExitWriteLock();
            if (_lock.IsReadLockHeld) _lock.ExitReadLock();
        }
    }

    public void SymmetricExceptWith(IEnumerable<T> other)
    {
        _lock.EnterWriteLock();
        try
        {
            _hashSet.SymmetricExceptWith(other);
        }
        finally
        {
            if (_lock.IsWriteLockHeld) _lock.ExitWriteLock();
        }
    }

    public bool IsSubsetOf(IEnumerable<T> other)
    {
        _lock.EnterWriteLock();
        try
        {
            return _hashSet.IsSubsetOf(other);
        }
        finally
        {
            if (_lock.IsWriteLockHeld) _lock.ExitWriteLock();
        }
    }

    public bool IsSupersetOf(IEnumerable<T> other)
    {
        _lock.EnterWriteLock();
        try
        {
            return _hashSet.IsSupersetOf(other);
        }
        finally
        {
            if (_lock.IsWriteLockHeld) _lock.ExitWriteLock();
        }
    }

    public bool IsProperSupersetOf(IEnumerable<T> other)
    {
        _lock.EnterWriteLock();
        try
        {
            return _hashSet.IsProperSupersetOf(other);
        }
        finally
        {
            if (_lock.IsWriteLockHeld) _lock.ExitWriteLock();
        }
    }

    public bool IsProperSubsetOf(IEnumerable<T> other)
    {
        _lock.EnterWriteLock();
        try
        {
            return _hashSet.IsProperSubsetOf(other);
        }
        finally
        {
            if (_lock.IsWriteLockHeld) _lock.ExitWriteLock();
        }
    }

    public bool Overlaps(IEnumerable<T> other)
    {
        _lock.EnterWriteLock();
        try
        {
            return _hashSet.Overlaps(other);
        }
        finally
        {
            if (_lock.IsWriteLockHeld) _lock.ExitWriteLock();
        }
    }

    public bool SetEquals(IEnumerable<T> other)
    {
        _lock.EnterWriteLock();
        try
        {
            return _hashSet.SetEquals(other);
        }
        finally
        {
            if (_lock.IsWriteLockHeld) _lock.ExitWriteLock();
        }
    }

    bool ISet<T>.Add(T item)
    {
        _lock.EnterWriteLock();
        try
        {
            return _hashSet.Add(item);
        }
        finally
        {
            if (_lock.IsWriteLockHeld) _lock.ExitWriteLock();
        }
    }

    public void Clear()
    {
        _lock.EnterWriteLock();
        try
        {
            _hashSet.Clear();
        }
        finally
        {
            if (_lock.IsWriteLockHeld) _lock.ExitWriteLock();
        }
    }

    public bool Contains(T item)
    {
        _lock.EnterWriteLock();
        try
        {
            return _hashSet.Contains(item);
        }
        finally
        {
            if (_lock.IsWriteLockHeld) _lock.ExitWriteLock();
        }
    }

    public void CopyTo(T[] array, int arrayIndex)
    {
        _lock.EnterWriteLock();
        try
        {
            _hashSet.CopyTo(array, arrayIndex);
        }
        finally
        {
            if (_lock.IsWriteLockHeld) _lock.ExitWriteLock();
        }
    }

    public bool Remove(T item)
    {
        _lock.EnterWriteLock();
        try
        {
            return _hashSet.Remove(item);
        }
        finally
        {
            if (_lock.IsWriteLockHeld) _lock.ExitWriteLock();
        }
    }

    public int Count
    {
        get
        {
            _lock.EnterWriteLock();
            try
            {
                return _hashSet.Count;
            }
            finally
            {
                if(_lock.IsWriteLockHeld) _lock.ExitWriteLock();
            }

        }
    }

    public bool IsReadOnly
    {
        get { return false; }
    }
}
Dbl
quelle
Das Schloss wird entsorgt ... aber was ist mit dem inneren Hashset, wann wird sein Speicher freigegeben?
David Rettenbacher
1
@ Warappa wird bei der Speicherbereinigung freigegeben. Das einzige Mal, wenn ich Dinge manuell auf Null setze und ihre gesamte Präsenz innerhalb einer Klasse lösche, ist, wenn die Subjekte Ereignisse enthalten und somit möglicherweise Speicher verlieren (wie wenn Sie ObservableCollection und das geänderte Ereignis verwenden würden). Ich bin offen für Vorschläge, wenn Sie mein Verständnis zum Thema erweitern können. Ich habe ein paar Tage damit verbracht, über die Müllabfuhr zu recherchieren und bin immer neugierig auf neue Informationen
Dbl
@ AndreasMüller gute Antwort, aber ich frage mich, warum Sie '_lock.EnterWriteLock () verwenden;' gefolgt von '_lock.EnterReadLock ();' Bei einigen Methoden wie 'IntersectWith' ist der Lese-Look hier nicht erforderlich, da die Schreibsperre bei der Eingabe standardmäßig Lesevorgänge verhindert.
Jalal sagte am
Wenn Sie immer müssen EnterWriteLock, warum gibt EnterReadLockes überhaupt? Kann es nicht die Lesesperre für Methoden wie verwendet werden Contains?
ErikE
2
Dies ist kein ConcurrentHashSet, sondern ein ThreadSafeHashSet. Siehe meinen Kommentar zur @ ZenLulz-Antwort bezüglich der Selbstimplementierung. Ich bin zu 99% sicher, dass jeder, der diese Implementierungen verwendet hat, einen schwerwiegenden Fehler in seiner Anwendung hat.
George Mavritsakis