Small Hash Set Class (Minimal)
using System; using System.Collections.Generic; using System.Diagnostics; [DebuggerDisplay("Count = {" + nameof(Count) + "}")] [Serializable] public class MSet15<T> { private IEqualityComparer<T> _comparer; private int[] _hashBuckets; private Slot[] _slots; public MSet15() : this(11, EqualityComparer<T>.Default) { } public MSet15(int size) : this(size, EqualityComparer<T>.Default) { } public MSet15(IEqualityComparer<T> comparer) : this(11, comparer) { } public MSet15(int size, IEqualityComparer<T> comparer) { if (comparer == null) comparer = EqualityComparer<T>.Default; _comparer = comparer; _hashBuckets = new int[size]; _slots = new Slot[size]; Count = 0; } public int Count { get; private set; } public IEnumerator<T> GetEnumerator() { for (var i = 0; i < Count; i++) if (_slots[i].HashCode > 0) yield return _slots[i].Value; } public bool Add(T item) { var hashCode = _comparer.GetHashCode(item) & int.MaxValue; if (FindEntry(item, hashCode) != -1) return true; if (Count >= _slots.Length) Resize(); var hashPos = hashCode % _hashBuckets.Length; _slots[Count].Next = _hashBuckets[hashPos] - 1; _slots[Count].Value = item; _slots[Count].HashCode = hashCode; _hashBuckets[hashPos] = Count + 1; ++Count; return false; } public bool Contains(T item) { return FindEntry(item, _comparer.GetHashCode(item) & int.MaxValue) != -1; } private void Resize() { var newSize = _hashBuckets.Length * 2; var newSlots = new Slot[newSize]; var newHashBuckets = new int[newSize]; var newCount = 0; var en = GetEnumerator(); while (en.MoveNext()) { var item = en.Current; var hashCode = _comparer.GetHashCode(item) & int.MaxValue; var hashPos = hashCode % newHashBuckets.Length; newSlots[newCount].Next = newHashBuckets[hashPos] - 1; newSlots[newCount].Value = item; newSlots[newCount].HashCode = hashCode; newHashBuckets[hashPos] = newCount + 1; ++newCount; } _slots = newSlots; _hashBuckets = newHashBuckets; Count = newCount; } private int FindEntry(T item, int hashCode) { for (var position = _hashBuckets[hashCode % _hashBuckets.Length] - 1; position >= 0; position = _slots[position].Next) if (_slots[position].HashCode == hashCode && _comparer.Equals(_slots[position].Value, item)) return position; return -1; } public int FindEntry(T item) { return FindEntry(item, _comparer.GetHashCode(item) & int.MaxValue); } internal struct Slot { public int HashCode; public int Next; public T Value; } }