MSet15.cs

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