A Small HashSet Class
using System; using System.Collections.Generic; using System.Diagnostics; using System.Linq; [DebuggerTypeProxy(typeof(HashSetDebugView<>))] [DebuggerDisplay("Count = {" + nameof(Count) + "}")] [Serializable] public class TinySet<T> { private int[] _hashBuckets; private SizeHelper<T> _newSize = new SizeHelper<T>(); internal IEqualityComparer<T> Comparer; public int Position; internal Slot[] Slots; public TinySet() : this(101, EqualityComparer<T>.Default) { } public TinySet(int size) : this(size, EqualityComparer<T>.Default) { } public TinySet(IEqualityComparer<T> comparer) : this(101, comparer) { } public TinySet(int size, IEqualityComparer<T> comparer) { if (comparer == null) comparer = EqualityComparer<T>.Default; Comparer = comparer; _hashBuckets = new int[size]; Slots = new Slot[size]; Count = 0; Position = -1; } public TinySet(IEnumerable<T> collection, IEqualityComparer<T> comparer) { if (comparer == null) comparer = EqualityComparer<T>.Default; Comparer = comparer; if (!(collection is ICollection<T> coll)) return; var size = coll.Count; _hashBuckets = new int[size]; Slots = new Slot[size]; UnionWith(coll); } public int Count { get; private set; } public T[] ToArray() { var newArray = new T[Count]; var copied = 0; for (var i = 0; i < Count && copied < Count; i++) if (Slots[i].HashCode > 0) newArray[copied++] = Slots[i].Value; return newArray; } public void Create(int size, IEqualityComparer<T> comparer) { if (comparer == null) comparer = EqualityComparer<T>.Default; Comparer = comparer; _hashBuckets = new int[size]; Slots = new Slot[size]; Count = 0; Position = -1; } public void Clear() { var size = Slots.Length; _hashBuckets = new int[size]; Slots = new Slot[size]; Count = 0; Position = -1; } public bool Add(T item) { return Insert(item, true); } public bool Contains(T item) { return Insert(item, false); } internal bool Insert(T item, bool add) { var hashCode = Comparer.GetHashCode(item) & int.MaxValue; if (FindEntry(item, hashCode) != -1) return true; if (add) { if (Count >= Slots.Length) SetSizeAndOrForceNewHashCodes(_newSize.GetNewSize(_hashBuckets.Length)); var hashPos = hashCode % _hashBuckets.Length; Slots[Count].Next = _hashBuckets[hashPos] - 1; Slots[Count].Value = item; Slots[Count].HashCode = hashCode; _hashBuckets[hashPos] = Count + 1; Position = Count; ++Count; } return false; } public void ForceNewHashCodes() { SetSizeAndOrForceNewHashCodes(); } private void SetSizeAndOrForceNewHashCodes(int Size = 0) { if (Count == 0) return; var newSize = Size == 0 ? Count : Size; var newSlots = new Slot[newSize]; var newHashBuckets = new int[newSize]; if (Slots != null) Array.Copy(Slots, 0, newSlots, 0, Count); for (var i = 0; i < newSize; ++i) if (newSlots[i].HashCode > 0 && newSlots[i].Value != null) newSlots[i].HashCode = Comparer.GetHashCode(newSlots[i].Value) & int.MaxValue; for (var i = 0; i < newSize; ++i) { var pos = newSlots[i].HashCode % newSize; newSlots[i].Next = newHashBuckets[pos] - 1; newHashBuckets[pos] = i + 1; } Slots = newSlots; _hashBuckets = newHashBuckets; } public void TrimExcess() { var newHashBuckets = new int[Count]; var newSlots = new Slot[Count]; Array.Copy(Slots, newSlots, Count); for (var i = 0; i < Count; i++) { var pos = newSlots[i].HashCode % Count; newSlots[i].Next = newHashBuckets[pos] - 1; newHashBuckets[pos] = i + 1; } _hashBuckets = newHashBuckets; Slots = newSlots; } public bool Remove(T item) { if (Count != 0) { var hashCode = Comparer.GetHashCode(item) & int.MaxValue; var iPos = hashCode % _hashBuckets.Length; var tPos = -1; for (var sPos = _hashBuckets[iPos] - 1; sPos >= 0; sPos = Slots[sPos].Next) { if (Slots[sPos].HashCode == hashCode && Comparer.Equals(Slots[sPos].Value, item)) { if (tPos < 0) _hashBuckets[iPos] = Slots[sPos].Next + 1; else Slots[tPos].Next = Slots[sPos].Next; Slots[sPos].HashCode = -1; Slots[sPos].Value = default; Slots[sPos].Next = 0; --Count; return true; } tPos = sPos; } } return false; } 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)) { Position = position; return position; } return -1; } public int FindEntry(T item) { return FindEntry(item, Comparer.GetHashCode(item) & int.MaxValue); } public void ExceptWith(IEnumerable<T> other) { if (other == null) throw new Exception("The other set must not be null."); if (Count == 0) return; if (Equals(other, this)) Clear(); else foreach (var obj in other) Remove(obj); } public void UnionWith(IEnumerable<T> other) { if (other == null) throw new Exception("The other set must not be null."); foreach (var obj in other) Add(obj); } public bool Overlaps(IEnumerable<T> other) { if (other == null) throw new Exception("The other set must not be null."); return Count != 0 && other.Any(Contains); } public bool ContainsAllElements(IEnumerable<T> other) { return other.All(Contains); } public int RemoveWhere(Predicate<T> pred) { if (pred == null) throw new Exception("The Predicate cannot be null."); var matches = 0; for (var i = 0; i < Count; ++i) if (Slots[i].HashCode >= 0) { var obj = Slots[i].Value; if (pred(obj) && Remove(obj)) ++matches; } return matches; } internal struct Slot { public int HashCode; public int Next; public T Value; } }