Single Array HashSet Class<\/p>\n\n\n\n
Uses only a single array for tracking and storage.<\/p>\n\n\n\n
Updated: July-11,2021<\/p>\n\n\n\n
using System;\nusing System.Collections;\nusing System.Collections.Generic;\nusing System.Diagnostics;\n[DebuggerDisplay(\"Count = {Count}\")]\npublic class BucketHashSet3<T> : IEnumerable\n{\n private Bucket[] _buckets;\n internal IEqualityComparer<T> Comparer;\n private int HiBucketCount;\n public BucketHashSet3() : this(1_000_000, 10, null)\n {\n }\n public BucketHashSet3(int sizeHint, int sizeHintBucket) : this(sizeHint, sizeHintBucket, null)\n {\n }\n public BucketHashSet3(int sizeHint, int sizeHintBucket, IEqualityComparer<T> comparer)\n {\n if (comparer == null)\n comparer = EqualityComparer<T>.Default;\n Comparer = comparer;\n _buckets = new Bucket[sizeHint];\n Count = 0;\n HiBucketCount = 0;\n for (var i = 0; i < _buckets.Length; ++i)\n _buckets[i].Allocate(sizeHintBucket);\n }\n public int Count\n {\n get;\n private set;\n }\n IEnumerator IEnumerable.GetEnumerator()\n {\n return GetEnumerator();\n }\n public void Zero()\n {\n _buckets = null;\n Count = 0;\n }\n public bool Add(T item)\n {\n var hashCode = Comparer.GetHashCode(item) & int.MaxValue;\n var apos = FindEntry(item, hashCode);\n if (apos != -1)\n return false;\n var pos = hashCode % _buckets.Length;\n _buckets[pos].Add(item);\n Count++;\n return true;\n }\n public T[] ToArray()\n {\n var newArray = new T[Count];\n using (var en = GetEnumerator())\n {\n var ptr = 0;\n while (en.MoveNext())\n {\n var value = en.Current;\n if (value == null)\n break;\n newArray[ptr++] = value;\n }\n return newArray;\n }\n }\n private int FindEntry(T item, int hashCode)\n {\n if (Count == 0)\n return -1;\n var Pos = hashCode % _buckets.Length;\n if (_buckets[Pos].Count == 0)\n return -1;\n var cnt = _buckets[Pos].Count;\n if (cnt > HiBucketCount)\n HiBucketCount = cnt;\n if (HiBucketCount >= 100)\n {\n Resize();\n HiBucketCount = 0;\n return FindEntry(item, hashCode);\n }\n for (var i = 0; i < cnt; ++i)\n {\n var v = _buckets[Pos].Values[i];\n if (Comparer.Equals(v, item))\n return Pos;\n }\n return -1;\n }\n private void Resize()\n {\n var cArray = ToArray();\n var newSize = _buckets.Length << 1;\n _buckets = new Bucket[newSize];\n for (var i = 0; i < newSize; ++i)\n _buckets[i].Allocate();\n foreach (var i in cArray)\n _buckets[BucketPosition(i)].Add(i);\n }\n private int BucketPosition(T item)\n {\n var hashCode = Comparer.GetHashCode(item) & int.MaxValue;\n var pos = hashCode % _buckets.Length;\n return pos;\n }\n public bool Contains(T item)\n {\n var hashCode = Comparer.GetHashCode(item) & int.MaxValue;\n return FindEntry(item, hashCode) != -1;\n }\n public IEnumerator<T> GetEnumerator()\n {\n return GetEnum();\n }\n public IEnumerator<T> GetEnum()\n {\n for (var i = 0; i < _buckets.Length; i++)\n for (var j = 0; j < _buckets[i].Count; ++j)\n yield return _buckets[i].Values[j];\n }\n internal struct Bucket\n {\n public int Count;\n public T[] Values;\n public void Add(T item)\n {\n if (Count >= Values.Length)\n Array.Resize(ref Values, Values.Length << 1);\n Values[Count++] = item;\n }\n public void Allocate(int size = 10)\n {\n Values = new T[size];\n }\n }\n}<\/pre>\n","protected":false},"excerpt":{"rendered":"Single Array HashSet Class Uses only a single array for tracking and storage. Updated: July-11,2021<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[2],"tags":[187,58,141],"_links":{"self":[{"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/posts\/454"}],"collection":[{"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/comments?post=454"}],"version-history":[{"count":8,"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/posts\/454\/revisions"}],"predecessor-version":[{"id":497,"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/posts\/454\/revisions\/497"}],"wp:attachment":[{"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/media?parent=454"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/categories?post=454"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/tags?post=454"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}