LightHashSet.cs

using System;
using System.Collections;
using System.Collections.Generic;
using System.Runtime.CompilerServices;

using NUnit.Framework;

public class LightHashSet<T> : IEnumerable<T>
{
    private struct Node
    {
        public int nextNodeId;
        public T value;

        public override string ToString()
        {
            return $"{nameof(nextNodeId)}: {nextNodeId}, {nameof(value)}: {value}";
        }
    }

    private Node[] _nodes;
    private int _nodeCount;
    private readonly int[] _table;
    private int _modCount;
    
    private static readonly EqualityComparer<T> _comparer = EqualityComparer<T>.Default;

    public LightHashSet(int tableSize, int initialNodePoolSize)
    {
        _table = new int[tableSize];
        _nodes = new Node[initialNodePoolSize];
        _nodeCount = 0;
    }

    public void Clear()
    {
        _nodeCount = 0;
        Array.Clear(_table, 0, _table.Length);
        Array.Clear(_nodes, 0, _nodeCount);
        _modCount++;
    }

    public bool Add(in T value)
    {
        int bucket = Bucket(value);

        int nodeId = _table[bucket];
        while (nodeId > 0)
        {
            ref Node node = ref _nodes[nodeId - 1];
            if (_comparer.Equals(node.value, value))
            {
                return false;
            }

            nodeId = node.nextNodeId;
        }

        if (_nodes.Length <= _nodeCount)
        {
            Array.Resize(ref _nodes, _nodes.Length * 2);
        }

        int newNodeId = _nodeCount + 1;
        ref Node newNode = ref _nodes[newNodeId - 1];
        newNode.value = value;
        newNode.nextNodeId = _table[bucket];
        _nodeCount++;
        _table[bucket] = newNodeId;
        _modCount++;

        return true;
    }

    public bool Contains(in T value)
    {
        int bucket = Bucket(value);

        int nodeId = _table[bucket];
        while (nodeId > 0)
        {
            ref Node node = ref _nodes[nodeId - 1];
            if (_comparer.Equals(node.value, value))
            {
                return true;
            }

            nodeId = node.nextNodeId;
        }

        return false;
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    private int Bucket(in T value)
    {
        return Math.Abs(_comparer.GetHashCode(value)) % _table.Length;
    }

    public Enumerator GetEnumerator()
    {
        Enumerator it = default;
        it.set = this;
        it.modCount = _modCount;
        it.Reset();
        return it;
    }

    public struct Enumerator : IEnumerator<T>
    {
        internal LightHashSet<T> set;
        private int _idx;
        internal int modCount;

        public bool MoveNext()
        {
            if (modCount != set._modCount)
            {
                throw new Exception("set was modified during its iteration");
            }

            _idx++;
            return _idx < set._nodeCount;
        }

        public void Reset()
        {
            _idx = -1;
        }

        object IEnumerator.Current => Current;

        public T Current => set._nodes[_idx].value;

        public void Dispose() { }
    }

    IEnumerator<T> IEnumerable<T>.GetEnumerator() => GetEnumerator();

    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
}


public class LightHashSetTest
{
    [Test]
    public void ContainsAdded()
    {
        LightHashSet<string> set = new LightHashSet<string>(16, 16);
        set.Add("A");
        Assert.True(set.Contains("A"));
    }
    [Test]
    public void NotContainsNotAdded()
    {
        LightHashSet<string> set = new LightHashSet<string>(16, 16);
        set.Add("A");
        Assert.False(set.Contains("B"));
    }

    [Test]
    public void ContainsBothWithCollision()
    {
        LightHashSet<string> set = new LightHashSet<string>(1, 16);
        set.Add("A");
        set.Add("B");
        Assert.True(set.Contains("A"));
        Assert.True(set.Contains("B"));
    }

    [Test]
    public void ReportsOnAdd()
    {
        LightHashSet<string> set = new LightHashSet<string>(16, 16);
        Assert.True(set.Add("A"));
        Assert.False(set.Add("A"));
    }

    [Test]
    public void ClearWorks()
    {
        LightHashSet<string> set = new LightHashSet<string>(16, 16);
        set.Add("A");
        set.Clear();
        Assert.False(set.Contains("A"));
    }

    [Test]
    public void Linq()
    {
        LightHashSet<string> set = new LightHashSet<string>(16, 16);
        set.Add("A");
        set.Add("B");
        string s = string.Join(", ", set.OrderBy(it => it));
        Assert.AreEqual("A, B", s);
    }
}