Come implementare ConcurrentHashSet in .Net

Sto cercando di implementare un ConcurrentHashSet nello spirito di ConcurrentDictionary, l’approccio adottato è quello di utilizzare un supporto interno ConcurrentDictionary e scrivere piccoli metodi di delega, questo è quanto ho ottenuto, ma i metodi teorici stabiliti sono su cui sono bloccato, esp. Non sono sicuro di poter utilizzare un foreach e comunque non violare la concorrenza

public class ConcurrentHashSet : ISet { private readonly ConcurrentDictionary _internal; public ConcurrentHashSet(IEnumerable elements = null) { _internal = new ConcurrentDictionary(); if (elements != null) UnionWith(elements); } public void UnionWith(IEnumerable other) { if (other == null) throw new ArgumentNullException("other"); foreach (var otherElement in other) Add(otherElement); } public void IntersectWith(IEnumerable other) { throw new NotImplementedException(); } public void ExceptWith(IEnumerable other) { throw new NotImplementedException(); } public void SymmetricExceptWith(IEnumerable other) { throw new NotImplementedException(); } public bool IsSubsetOf(IEnumerable other) { throw new NotImplementedException(); } public bool IsSupersetOf(IEnumerable other) { throw new NotImplementedException(); } public bool IsProperSupersetOf(IEnumerable other) { throw new NotImplementedException(); } public bool IsProperSubsetOf(IEnumerable other) { throw new NotImplementedException(); } public bool Overlaps(IEnumerable other) { return other.Any(otherElement => _internal.ContainsKey(otherElement)); } public bool SetEquals(IEnumerable other) { int otherCount = 0; int thisCount = Count; foreach (var otherElement in other) { otherCount++; if (!_internal.ContainsKey(otherElement)) return false; } return otherCount == thisCount; } public bool Add(TElement item) { return _internal.TryAdd(item, null); } public void Clear() { _internal.Clear(); } // I am not sure here if that fullfills contract correctly void ICollection.Add(TElement item) { Add(item); } public bool Contains(TElement item) { return _internal.ContainsKey(item); } public void CopyTo(TElement[] array, int arrayIndex) { _internal.Keys.CopyTo(array, arrayIndex); } public bool Remove(TElement item) { object ignore; return _internal.TryRemove(item, out ignore); } public int Count { get { return _internal.Count; } } public bool IsReadOnly { get { return false; } } public IEnumerator GetEnumerator() { return _internal.Keys.GetEnumerator(); } IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); } } 

Mi sono imbattuto in uno scenario simile (“Sono interessato a un veloce Add e Contains and Remove”) e ho implementato questo sucker:

 using System.Collections.Generic; using System.Threading; namespace BlahBlah.Utilities { public class ConcurrentHashSet : IDisposable { private readonly ReaderWriterLockSlim _lock = new ReaderWriterLockSlim(LockRecursionPolicy.SupportsRecursion); private readonly HashSet _hashSet = new HashSet(); #region Implementation of ICollection ...ish public bool Add(T item) { try { _lock.EnterWriteLock(); return _hashSet.Add(item); } finally { if (_lock.IsWriteLockHeld) _lock.ExitWriteLock(); } } public void Clear() { try { _lock.EnterWriteLock(); _hashSet.Clear(); } finally { if (_lock.IsWriteLockHeld) _lock.ExitWriteLock(); } } public bool Contains(T item) { try { _lock.EnterReadLock(); return _hashSet.Contains(item); } finally { if (_lock.IsReadLockHeld) _lock.ExitReadLock(); } } public bool Remove(T item) { try { _lock.EnterWriteLock(); return _hashSet.Remove(item); } finally { if (_lock.IsWriteLockHeld) _lock.ExitWriteLock(); } } public int Count { get { try { _lock.EnterReadLock(); return _hashSet.Count; } finally { if (_lock.IsReadLockHeld) _lock.ExitReadLock(); } } } #endregion #region Dispose public void Dispose() { if (_lock != null) _lock.Dispose(); } #endregion } } 

Non l’ho mai testato (prestazioni o affidabilità). YMMV.

Ecco un’implementazione di un insieme concorrente basato sul ConcurrentDictionary :

 public class ConcurrentSet : IEnumerable, ISet, ICollection { private readonly ConcurrentDictionary _dictionary = new ConcurrentDictionary(); ///  /// Returns an enumerator that iterates through the collection. ///  ///  /// A  that can be used to iterate through the collection. ///  public IEnumerator GetEnumerator() { return _dictionary.Keys.GetEnumerator(); } ///  /// Returns an enumerator that iterates through a collection. ///  ///  /// An  object that can be used to iterate through the collection. ///  IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); } ///  /// Removes the first occurrence of a specific object from the . ///  ///  /// true if  was successfully removed from the ; otherwise, false. This method also returns false if  is not found in the original . ///  /// The object to remove from the .The  is read-only. public bool Remove(T item) { return TryRemove(item); } ///  /// Gets the number of elements in the set. ///  public int Count { get { return _dictionary.Count; } } ///  /// Gets a value indicating whether the  is read-only. ///  ///  /// true if the  is read-only; otherwise, false. ///  public bool IsReadOnly { get { return false; } } ///  /// Gets a value that indicates if the set is empty. ///  public bool IsEmpty { get { return _dictionary.IsEmpty; } } public ICollection Values { get { return _dictionary.Keys; } } ///  /// Adds an item to the . ///  /// The object to add to the .The  is read-only. void ICollection.Add(T item) { if(!Add(item)) throw new ArgumentException("Item already exists in set."); } ///  /// Modifies the current set so that it contains all elements that are present in both the current set and in the specified collection. ///  /// The collection to compare to the current set. is null. public void UnionWith(IEnumerable other) { foreach (var item in other) TryAdd(item); } ///  /// Modifies the current set so that it contains only elements that are also in a specified collection. ///  /// The collection to compare to the current set. is null. public void IntersectWith(IEnumerable other) { var enumerable = other as IList ?? other.ToArray(); foreach (var item in this) { if (!enumerable.Contains(item)) TryRemove(item); } } ///  /// Removes all elements in the specified collection from the current set. ///  /// The collection of items to remove from the set. is null. public void ExceptWith(IEnumerable other) { foreach (var item in other) TryRemove(item); } ///  /// Modifies the current set so that it contains only elements that are present either in the current set or in the specified collection, but not both. ///  /// The collection to compare to the current set. is null. public void SymmetricExceptWith(IEnumerable other) { throw new NotImplementedException(); } ///  /// Determines whether a set is a subset of a specified collection. ///  ///  /// true if the current set is a subset of ; otherwise, false. ///  /// The collection to compare to the current set. is null. public bool IsSubsetOf(IEnumerable other) { var enumerable = other as IList ?? other.ToArray(); return this.AsParallel().All(enumerable.Contains); } ///  /// Determines whether the current set is a superset of a specified collection. ///  ///  /// true if the current set is a superset of ; otherwise, false. ///  /// The collection to compare to the current set. is null. public bool IsSupersetOf(IEnumerable other) { return other.AsParallel().All(Contains); } ///  /// Determines whether the current set is a correct superset of a specified collection. ///  ///  /// true if the  object is a correct superset of ; otherwise, false. ///  /// The collection to compare to the current set.  is null. public bool IsProperSupersetOf(IEnumerable other) { var enumerable = other as IList ?? other.ToArray(); return this.Count != enumerable.Count && IsSupersetOf(enumerable); } ///  /// Determines whether the current set is a property (strict) subset of a specified collection. ///  ///  /// true if the current set is a correct subset of ; otherwise, false. ///  /// The collection to compare to the current set. is null. public bool IsProperSubsetOf(IEnumerable other) { var enumerable = other as IList ?? other.ToArray(); return Count != enumerable.Count && IsSubsetOf(enumerable); } ///  /// Determines whether the current set overlaps with the specified collection. ///  ///  /// true if the current set and  share at least one common element; otherwise, false. ///  /// The collection to compare to the current set. is null. public bool Overlaps(IEnumerable other) { return other.AsParallel().Any(Contains); } ///  /// Determines whether the current set and the specified collection contain the same elements. ///  ///  /// true if the current set is equal to ; otherwise, false. ///  /// The collection to compare to the current set. is null. public bool SetEquals(IEnumerable other) { var enumerable = other as IList ?? other.ToArray(); return Count == enumerable.Count && enumerable.AsParallel().All(Contains); } ///  /// Adds an element to the current set and returns a value to indicate if the element was successfully added. ///  ///  /// true if the element is added to the set; false if the element is already in the set. ///  /// The element to add to the set. public bool Add(T item) { return TryAdd(item); } public void Clear() { _dictionary.Clear(); } public bool Contains(T item) { return _dictionary.ContainsKey(item); } ///  /// Copies the elements of the  to an , starting at a particular  index. ///  /// The one-dimensional  that is the destination of the elements copied from . The  must have zero-based indexing.The zero-based index in  at which copying begins. is null. is less than 0. is multidimensional.-or-The number of elements in the source  is greater than the available space from  to the end of the destination .-or-Type  cannot be cast automatically to the type of the destination . public void CopyTo(T[] array, int arrayIndex) { Values.CopyTo(array, arrayIndex); } public T[] ToArray() { return _dictionary.Keys.ToArray(); } public bool TryAdd(T item) { return _dictionary.TryAdd(item, default(byte)); } public bool TryRemove(T item) { byte donotcare; return _dictionary.TryRemove(item, out donotcare); } } 

ConcurrentDictionary ha caratteristiche di prestazioni migliori in quanto utilizza un modo lockfree per le letture (almeno in .NET 4.0+). Quindi per le prestazioni in scenari mulithreaded pesanti un ConcurrentDictionary probabilmente funzionerà meglio come un wrapper readerwriterlockslim. Ma devi portare in giro un byte vuoto come dummyvalue (sono d’accordo, sembra orribile).

Per cosa intendi usarlo?

Anche se ottieni i metodi per funzionare, potresti avere il seguente scenario:

 var set1 = new ConcurrentHashSet(); ... if (set1.Overlaps(set2)) { set1.IntersectWith(set2); assert(! set1.IsEmpty()); // might fail } 

Potrebbe essere accettabile, ma un Set ha meno probabilità di essere utile in un’impostazione simultanea di una coda.