Small

MSet15.cs

Small Hash Set Class (Minimal)

Updated: July-23,2021

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

[DebuggerDisplay("Count = {" + nameof(Count) + "}")]
[Serializable]
public class MSet15<T>
{
    private  int[]                _hashBuckets;
    internal IEqualityComparer<T> Comparer;
    internal int                  Position;
    internal Slot[]               Slots;
    public   bool                 SlowGrowth;
    public MSet15() : this(101, EqualityComparer<T>.Default)
    {
    }
    public MSet15(int size) : this(size, EqualityComparer<T>.Default)
    {
    }
    public MSet15(IEqualityComparer<T> comparer) : this(31, 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;
        Position     = -1;
    }
    public MSet15(IEnumerable<T> collection, IEqualityComparer<T> comparer)
    {
        if (comparer == null)
            comparer = EqualityComparer<T>.Default;
        var enumerable = collection as T[] ?? collection.ToArray();
        var size       = enumerable.Length;
        Comparer     = comparer;
        _hashBuckets = new int[size];
        Slots        = new Slot[size];
        Count        = 0;
        Position     = -1;
        foreach (var i in enumerable)
            Add(i);
    }
    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;
        Position              = Count;
        ++Count;
        return false;
    }

    public void AddRange(IEnumerable<T> collection)
    {
        foreach (var i in collection)
            Add(i);
    }
    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;
    }
    public bool Contains(T item)
    {
        return FindEntry(item, Comparer.GetHashCode(item) & int.MaxValue) != -1;
    }
    public T[] ToArray()
    {
        var newArray = new T[Count];
        using (var en = GetEnumerator())
        {
            var ptr = 0;
            while (en.MoveNext())
            {
                var value = en.Current;
                if (value == null)
                    break;
                newArray[ptr++] = value;
            }
            return newArray;
        }
    }
    private void Resize()
    {
        var newSize        = !SlowGrowth ? _hashBuckets.Length + _hashBuckets.Length / 4 * 3 : _hashBuckets.Length + 1;
        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;
    }
    public 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);
    }
    internal struct Slot
    {
        public int HashCode;
        public int Next;
        public T   Value;
    }
}

TinyDictionary.cs

A Small Dictionary Class

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
[DebuggerDisplay("Count = {Count}")]
[Serializable]
public class TinyDictionary<TKey, TValue> : IEnumerable<KeyValuePair<TKey, TValue>>
{
    public MSet15<TKey> Keys;
    public int          Resizes;
    public TValue[]     Values;
    public TinyDictionary() : this(101, EqualityComparer<TKey>.Default)
    {
    }
    public TinyDictionary(int size) : this(size, EqualityComparer<TKey>.Default)
    {
    }
    public TinyDictionary(int size, IEqualityComparer<TKey> comparer)
    {
        if (comparer == null)
            comparer = EqualityComparer<TKey>.Default;
        Keys          = new MSet15<TKey>(size);
        Values        = new TValue[size];
        Keys.Comparer = comparer;
    }
    public TinyDictionary(IEnumerable<KeyValuePair<TKey, TValue>> collection, IEqualityComparer<TKey> comparer = null)
    {
        if (comparer == null)
            comparer = EqualityComparer<TKey>.Default;
        Keys.Comparer = comparer;
        foreach (var kp in collection)
            Add(kp.Key, kp.Value);
    }
    public int Count => Keys.Count;
    public TValue this[TKey key]
    {
        get
        {
            var pos = Keys.FindEntry(key);
            return pos == -1 ? default : Values[pos];
        }
        set => Add(key, value);
    }
    public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
    {
        for (var i = 0; i < Count; i++)
            if (Keys.Slots[i].HashCode > 0)
                yield return new KeyValuePair<TKey, TValue>(Keys.Slots[i].Value, Values[i]);
    }
    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
    public bool Add(TKey key, TValue value)
    {
        if (!Keys.Add(key))
        {
            if (Values.Length != Keys.Slots.Length)
            {
                var nValues = new TValue[Keys.Slots.Length];
                Array.Copy(Values, nValues, Values.Length);
                Values = nValues;
                Resizes++;
            }
            Values[Keys.Position] = value;
            return false;
        }
        Values[Keys.Position] = value;
        return true;
    }
    public void Remove(TKey key)
    {
        var pos = Keys.FindEntry(key);
        if (pos != -1)
        {
            Values[pos] = default;
            Keys.Remove(key);
        }
    }
    public bool ContainsKey(TKey key)
    {
        return Keys.FindEntry(key) != -1;
    }
    public int FindKeyIndex(TKey key)
    {
        return Keys.FindEntry(key);
    }
}

TinySet.cs

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;
    }
}