代码之家 › 专栏 › 技术社区 › Sebastian

如何在.NET中实现ConcurrentHashSet

hashset dictionary concurrency .net c#

Sebastian · 技术社区 · 15 年前

我正试图以同谋的精神实施一个同谋, 所采取的方法是使用一个内部支持的并发事务,并编写一些小的委托方法,这就是我所取得的进展,但是我仍然坚持使用集合理论方法,特别是,我不确定是否可以使用foreach,并且仍然不违反并发性。

public class ConcurrentHashSet<TElement> : ISet<TElement>
{
    private readonly ConcurrentDictionary<TElement, object> _internal;

    public ConcurrentHashSet(IEnumerable<TElement> elements = null)
    {
        _internal = new ConcurrentDictionary<TElement, object>();
        if (elements != null)
            UnionWith(elements);
    }

    public void UnionWith(IEnumerable<TElement> other)
    {
        if (other == null) throw new ArgumentNullException("other");

        foreach (var otherElement in other)
            Add(otherElement);
    }

    public void IntersectWith(IEnumerable<TElement> other)
    {
        throw new NotImplementedException();
    }

    public void ExceptWith(IEnumerable<TElement> other)
    {
        throw new NotImplementedException();
    }

    public void SymmetricExceptWith(IEnumerable<TElement> other)
    {
        throw new NotImplementedException();
    }

    public bool IsSubsetOf(IEnumerable<TElement> other)
    {
        throw new NotImplementedException();
    }

    public bool IsSupersetOf(IEnumerable<TElement> other)
    {
        throw new NotImplementedException();
    }

    public bool IsProperSupersetOf(IEnumerable<TElement> other)
    {
        throw new NotImplementedException();
    }

    public bool IsProperSubsetOf(IEnumerable<TElement> other)
    {
        throw new NotImplementedException();
    }

    public bool Overlaps(IEnumerable<TElement> other)
    {
        return other.Any(otherElement => _internal.ContainsKey(otherElement));
    }

    public bool SetEquals(IEnumerable<TElement> 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<TElement>.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<TElement> GetEnumerator()
    {
        return _internal.Keys.GetEnumerator();
    }

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

4 回复 | 直到 10 年前

Ben Mosher 10 年前

我刚刚遇到一个类似的场景(“我对快速添加感兴趣,并包含和删除”)并实现了这个吸盘:

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)
        {
            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
    }
}

还没有真正测试过(性能或可靠性方面)。YMMV。

David Pfeffer 13 年前

下面是基于 ConcurrentDictionary :

public class ConcurrentSet<T> : IEnumerable<T>, ISet<T>, ICollection<T>
{
    private readonly ConcurrentDictionary<T, byte> _dictionary = new ConcurrentDictionary<T, byte>();

    /// <summary>
    /// Returns an enumerator that iterates through the collection.
    /// </summary>
    /// <returns>
    /// A <see cref="T:System.Collections.Generic.IEnumerator`1"/> that can be used to iterate through the collection.
    /// </returns>
    public IEnumerator<T> GetEnumerator()
    {
        return _dictionary.Keys.GetEnumerator();
    }

    /// <summary>
    /// Returns an enumerator that iterates through a collection.
    /// </summary>
    /// <returns>
    /// An <see cref="T:System.Collections.IEnumerator"/> object that can be used to iterate through the collection.
    /// </returns>
    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }

    /// <summary>
    /// Removes the first occurrence of a specific object from the <see cref="T:System.Collections.Generic.ICollection`1"/>.
    /// </summary>
    /// <returns>
    /// true if <paramref name="item"/> was successfully removed from the <see cref="T:System.Collections.Generic.ICollection`1"/>; otherwise, false. This method also returns false if <paramref name="item"/> is not found in the original <see cref="T:System.Collections.Generic.ICollection`1"/>.
    /// </returns>
    /// <param name="item">The object to remove from the <see cref="T:System.Collections.Generic.ICollection`1"/>.</param><exception cref="T:System.NotSupportedException">The <see cref="T:System.Collections.Generic.ICollection`1"/> is read-only.</exception>
    public bool Remove(T item)
    {
        return TryRemove(item);
    }

    /// <summary>
    /// Gets the number of elements in the set.
    /// </summary>
    public int Count
    {
        get { return _dictionary.Count; }
    }

    /// <summary>
    /// Gets a value indicating whether the <see cref="T:System.Collections.Generic.ICollection`1"/> is read-only.
    /// </summary>
    /// <returns>
    /// true if the <see cref="T:System.Collections.Generic.ICollection`1"/> is read-only; otherwise, false.
    /// </returns>
    public bool IsReadOnly { get { return false; } }

    /// <summary>
    /// Gets a value that indicates if the set is empty.
    /// </summary>
    public bool IsEmpty
    {
        get { return _dictionary.IsEmpty; }
    }

    public ICollection<T> Values
    {
        get { return _dictionary.Keys; }
    }

    /// <summary>
    /// Adds an item to the <see cref="T:System.Collections.Generic.ICollection`1"/>.
    /// </summary>
    /// <param name="item">The object to add to the <see cref="T:System.Collections.Generic.ICollection`1"/>.</param><exception cref="T:System.NotSupportedException">The <see cref="T:System.Collections.Generic.ICollection`1"/> is read-only.</exception>
    void ICollection<T>.Add(T item)
    {
        if(!Add(item))
            throw new ArgumentException("Item already exists in set.");
    }

    /// <summary>
    /// Modifies the current set so that it contains all elements that are present in both the current set and in the specified collection.
    /// </summary>
    /// <param name="other">The collection to compare to the current set.</param><exception cref="T:System.ArgumentNullException"><paramref name="other"/> is null.</exception>
    public void UnionWith(IEnumerable<T> other)
    {
        foreach (var item in other)
            TryAdd(item);
    }

    /// <summary>
    /// Modifies the current set so that it contains only elements that are also in a specified collection.
    /// </summary>
    /// <param name="other">The collection to compare to the current set.</param><exception cref="T:System.ArgumentNullException"><paramref name="other"/> is null.</exception>
    public void IntersectWith(IEnumerable<T> other)
    {
        var enumerable = other as IList<T> ?? other.ToArray();
        foreach (var item in this)
        {
            if (!enumerable.Contains(item))
                TryRemove(item);
        }
    }

    /// <summary>
    /// Removes all elements in the specified collection from the current set.
    /// </summary>
    /// <param name="other">The collection of items to remove from the set.</param><exception cref="T:System.ArgumentNullException"><paramref name="other"/> is null.</exception>
    public void ExceptWith(IEnumerable<T> other)
    {
        foreach (var item in other)
            TryRemove(item);
    }

    /// <summary>
    /// 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. 
    /// </summary>
    /// <param name="other">The collection to compare to the current set.</param><exception cref="T:System.ArgumentNullException"><paramref name="other"/> is null.</exception>
    public void SymmetricExceptWith(IEnumerable<T> other)
    {
        throw new NotImplementedException();
    }

    /// <summary>
    /// Determines whether a set is a subset of a specified collection.
    /// </summary>
    /// <returns>
    /// true if the current set is a subset of <paramref name="other"/>; otherwise, false.
    /// </returns>
    /// <param name="other">The collection to compare to the current set.</param><exception cref="T:System.ArgumentNullException"><paramref name="other"/> is null.</exception>
    public bool IsSubsetOf(IEnumerable<T> other)
    {
        var enumerable = other as IList<T> ?? other.ToArray();
        return this.AsParallel().All(enumerable.Contains);
    }

    /// <summary>
    /// Determines whether the current set is a superset of a specified collection.
    /// </summary>
    /// <returns>
    /// true if the current set is a superset of <paramref name="other"/>; otherwise, false.
    /// </returns>
    /// <param name="other">The collection to compare to the current set.</param><exception cref="T:System.ArgumentNullException"><paramref name="other"/> is null.</exception>
    public bool IsSupersetOf(IEnumerable<T> other)
    {
        return other.AsParallel().All(Contains);
    }

    /// <summary>
    /// Determines whether the current set is a correct superset of a specified collection.
    /// </summary>
    /// <returns>
    /// true if the <see cref="T:System.Collections.Generic.ISet`1"/> object is a correct superset of <paramref name="other"/>; otherwise, false.
    /// </returns>
    /// <param name="other">The collection to compare to the current set. </param><exception cref="T:System.ArgumentNullException"><paramref name="other"/> is null.</exception>
    public bool IsProperSupersetOf(IEnumerable<T> other)
    {
        var enumerable = other as IList<T> ?? other.ToArray();
        return this.Count != enumerable.Count && IsSupersetOf(enumerable);
    }

    /// <summary>
    /// Determines whether the current set is a property (strict) subset of a specified collection.
    /// </summary>
    /// <returns>
    /// true if the current set is a correct subset of <paramref name="other"/>; otherwise, false.
    /// </returns>
    /// <param name="other">The collection to compare to the current set.</param><exception cref="T:System.ArgumentNullException"><paramref name="other"/> is null.</exception>
    public bool IsProperSubsetOf(IEnumerable<T> other)
    {
        var enumerable = other as IList<T> ?? other.ToArray();
        return Count != enumerable.Count && IsSubsetOf(enumerable);
    }

    /// <summary>
    /// Determines whether the current set overlaps with the specified collection.
    /// </summary>
    /// <returns>
    /// true if the current set and <paramref name="other"/> share at least one common element; otherwise, false.
    /// </returns>
    /// <param name="other">The collection to compare to the current set.</param><exception cref="T:System.ArgumentNullException"><paramref name="other"/> is null.</exception>
    public bool Overlaps(IEnumerable<T> other)
    {
        return other.AsParallel().Any(Contains);
    }

    /// <summary>
    /// Determines whether the current set and the specified collection contain the same elements.
    /// </summary>
    /// <returns>
    /// true if the current set is equal to <paramref name="other"/>; otherwise, false.
    /// </returns>
    /// <param name="other">The collection to compare to the current set.</param><exception cref="T:System.ArgumentNullException"><paramref name="other"/> is null.</exception>
    public bool SetEquals(IEnumerable<T> other)
    {
        var enumerable = other as IList<T> ?? other.ToArray();
        return Count == enumerable.Count && enumerable.AsParallel().All(Contains);
    }

    /// <summary>
    /// Adds an element to the current set and returns a value to indicate if the element was successfully added. 
    /// </summary>
    /// <returns>
    /// true if the element is added to the set; false if the element is already in the set.
    /// </returns>
    /// <param name="item">The element to add to the set.</param>
    public bool Add(T item)
    {
        return TryAdd(item);
    }

    public void Clear()
    {
        _dictionary.Clear();
    }

    public bool Contains(T item)
    {
        return _dictionary.ContainsKey(item);
    }

    /// <summary>
    /// Copies the elements of the <see cref="T:System.Collections.Generic.ICollection`1"/> to an <see cref="T:System.Array"/>, starting at a particular <see cref="T:System.Array"/> index.
    /// </summary>
    /// <param name="array">The one-dimensional <see cref="T:System.Array"/> that is the destination of the elements copied from <see cref="T:System.Collections.Generic.ICollection`1"/>. The <see cref="T:System.Array"/> must have zero-based indexing.</param><param name="arrayIndex">The zero-based index in <paramref name="array"/> at which copying begins.</param><exception cref="T:System.ArgumentNullException"><paramref name="array"/> is null.</exception><exception cref="T:System.ArgumentOutOfRangeException"><paramref name="arrayIndex"/> is less than 0.</exception><exception cref="T:System.ArgumentException"><paramref name="array"/> is multidimensional.-or-The number of elements in the source <see cref="T:System.Collections.Generic.ICollection`1"/> is greater than the available space from <paramref name="arrayIndex"/> to the end of the destination <paramref name="array"/>.-or-Type <paramref name="T"/> cannot be cast automatically to the type of the destination <paramref name="array"/>.</exception>
    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);
    }
}

IvoTops 13 年前

ConcurrentDictionary具有更好的性能特征,因为它使用无锁方式进行读取(至少在.NET 4.0+中)。因此,对于多重读取场景中的性能,ConcurrentDictionary作为readerWriterLockSlim包装可能会表现得更好。但是你需要携带一个空字节作为dummyValue(我同意,这看起来很糟糕)。

Henk Holterman 15 年前

你打算用它做什么?

即使您确实让这些方法起作用,您也可以有以下场景:

var set1 = new ConcurrentHashSet<int>();
...

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

这可能是可以接受的,但是一个集合在并发设置中的用处要比一个队列小得多。