Tag: HashSet

Big Hash Set based on BigArray.cs

Uses a single array.

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
[DebuggerDisplay("Count = {" + nameof(Count) + "}")]
[Serializable]
public class BigHashsetSa<T> : MonitorActionFunc, IEnumerable
{
    public enum Method
    {
        Grow,
        Compress
    }
    private volatile BigArray<Bucket>        _buckets;
    private          long                    _count;
    private          Method                  _method;
    internal         IBigEqualityComparer<T> Comparer;
    public BigHashsetSa(long size, Method method = Method.Grow) : this(size, new BigComparer<T>(), method)
    {
    }
    public BigHashsetSa(long size, IBigEqualityComparer<T> comparer, Method method = Method.Grow)
    {
        if (comparer == null)
            comparer = new BigComparer<T>();
        Comparer = comparer;
        _buckets = new BigArray<Bucket>(size);
        Count    = 0;
        _method  = method;
    }
    public long Count
    {
        get
        {
            return Lock(this, () =>
            {
                return _count;
            });
        }
        private set
        {
            Lock(this, () =>
            {
                _count = value;
            });
        }
    }
    public long                       ElementCount         => GetElementCount();
    public long                       NumberOfEmptyBuckets => GetNumberOfEmptyBuckets();
    public (long mDepth, long index)  MaximumBucketDepth   => GetMaximumBucketDepth();
    public float                      LoadRatio            => GetLoadRatio();
    public KeyValuePair<long, long>[] BucketDepthList      => GetBucketDepthList();
    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
    public void Clear()
    {
        _buckets.Clear();
    }
    public bool Add(T item)
    {
        return Lock(this, () =>
        {
            if (_method == Method.Grow)
                EnsureSize();
            var hashCode = Comparer.GetHashCode(item) & long.MaxValue;
            if (FindEntry(item, hashCode).APos != -1)
                return false;
            var pos = hashCode % _buckets.Length;
            if (_buckets[pos] == null)
                _buckets[pos] = new Bucket();
            _buckets[pos].Add(item);
            Count++;
            return true;
        });
    }
    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 (long APos, long BPos) FindEntry(T item, long hashCode)
    {
        if (Count == 0)
            return (-1, -1);
        if (hashCode == 0)
        {
            var a = 0;
        }
        var aPos = hashCode % _buckets.Length;
        var bPos = 0;
        if (_buckets[aPos] == null)
        {
            _buckets[aPos] = new Bucket();
            return (-1, -1);
        }
        foreach (var i in _buckets[aPos].Values)
        {
            if (Comparer.Equals(i, item))
                return (aPos, bPos);
            bPos++;
        }
        return (-1, -1);
    }
    private void EnsureSize()
    {
        if (Count >= _buckets.Length)
        {
            var cArray = ToArray();
            _buckets = new BigArray<Bucket>(_buckets.Length + BigArray<T>.Granularity);
            foreach (var i in cArray)
            {
                var hashCode = Comparer.GetHashCode(i) & long.MaxValue;
                var pos      = hashCode % _buckets.Length;
                if (_buckets[pos] == null)
                    _buckets[pos] = new Bucket();
                _buckets[pos].Add(i);
            }
        }
    }
    public bool Contains(T item)
    {
        return Lock(this, () =>
        {
            var hashCode = Comparer.GetHashCode(item) & long.MaxValue;
            return FindEntry(item, hashCode).APos != -1;
        });
    }
    public IEnumerator<T> GetEnumerator()
    {
        return Lock(this, () =>
        {
            return GetEnum();
        });
    }
    public IEnumerator<T> GetEnum()
    {
        for (var i = 0; i < _buckets.Length; i++)
            if (_buckets[i] != null)
                for (var j = 0; j < _buckets[i].Count; ++j)
                    yield return _buckets[i].Values[j];
    }
    public long GetElementCount()
    {
        var count = 0;
        for (var i = 0; i < _buckets.Length; i++)
            if (_buckets[i] != null)
            {
                var c = _buckets[i].Count;
                count += c;
            }
        return count;
    }
    public long GetNumberOfEmptyBuckets()
    {
        var count = 0;
        for (var i = 0; i < _buckets.Length; i++)
            if (_buckets[i] == null)
                count++;
        return count;
    }
    public long GetNumberOfFilledBuckets()
    {
        var count = 0;
        for (var i = 0; i < _buckets.Length; i++)
            if (_buckets[i] != null)
                count++;
        return count;
    }
    public (long mDepth, long index) GetMaximumBucketDepth()
    {
        var max = 0;
        var j   = 0;
        for (var i = 0; i < _buckets.Length; i++)
            if (_buckets[i] != null)
            {
                var count = _buckets[i].Count;
                if (count > max)
                {
                    max = count;
                    j   = i;
                }
            }
        return (max, j);
    }
    public KeyValuePair<long, long>[] GetBucketDepthList()
    {
        var bdic = new Dictionary<long, long>();
        for (var i = 0; i < _buckets.Length; i++)
            if (_buckets[i] != null)
            {
                var count = _buckets[i].Count;
                if (!bdic.ContainsKey(count))
                {
                    bdic.Add(count, 0);
                    bdic[count]++;
                }
                else
                {
                    bdic[count]++;
                }
            }
        return bdic.OrderByDescending(x => x.Value).ToArray();
    }
    public float GetLoadRatio()
    {
        var x = Count;
        var y = _buckets.Length;
        var r = x / (float) y;
        return r;
    }
    internal class Bucket
    {
        public int Count;
        public T[] Values;
        public Bucket()
        {
            Values = new T[2];
            Count  = 0;
        }
        public void Add(T item)
        {
            if (Count >= Values.Length)
            {
                var ta = new T[Values.Length + 1];
                Array.Copy(Values, 0, ta, 0, Count);
                Values = ta;
            }
            Values[Count++] = item;
        }
    }
}