Skip to content

Instantly share code, notes, and snippets.

@mjs3339
Created August 3, 2018 07:27
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save mjs3339/1e443f1e9d2476f21c3829cf308a340a to your computer and use it in GitHub Desktop.
Save mjs3339/1e443f1e9d2476f21c3829cf308a340a to your computer and use it in GitHub Desktop.
C# A Small HashSet for Quick Loading & Lookups
public class SmallHashSet<T>
{
private int[] _hashBuckets;
private uint _hashCode;
public Data[] Datas;
public SmallHashSet() : this(4096)
{
}
public SmallHashSet(int size)
{
Initialize(size);
}
public int Count {get; private set;}
public bool IsDirty => Count != _hashBuckets.Length;
public bool Add(T item)
{
return Insert(item);
}
public bool Contains(T item)
{
return FindItem(item) != -1;
}
public void Clean()
{
if(Count == 0) return;
var newhashebuckets = new int[Count];
var newdatas = new Data[Count];
Array.Copy(Datas, newdatas, Count);
newhashebuckets.Fill(-1);
for(var i = 0; i < Count; i++)
{
var pos = newdatas[i].hashCode % Count;
var prevpos = newhashebuckets[pos];
newhashebuckets[pos] = i;
if(prevpos != -1)
newdatas[i].next = prevpos;
}
_hashBuckets = newhashebuckets;
Datas = newdatas;
}
private bool Insert(T item)
{
if(FindItem(item) != -1)
return false;
try
{
if(Count >= Datas.Length)
Resize();
}
catch(Exception e)
{
throw new Exception($"Error resizing hash bucket list {e.Message}");
}
var hashPos = _hashCode % (uint) _hashBuckets.Length;
var nextPos = _hashBuckets[hashPos];
_hashBuckets[hashPos] = Count;
Datas[Count].next = nextPos;
Datas[Count].value = item;
Datas[Count].hashCode = _hashCode;
Count++;
return true;
}
public int FindItem(T item)
{
_hashCode = (uint) item.GetHashCode() & int.MaxValue;
for(var position = _hashBuckets[_hashCode % _hashBuckets.Length]; position >= 0; position = Datas[position].next)
if(Datas[position].hashCode == _hashCode && EqualityComparer<T>.Default.Equals(Datas[position].value, item))
return position;
return-1;
}
private void Resize(int newsize = 0)
{
if(newsize == 0)
newsize = (int) (_hashBuckets.Length * 2.5f);
var newhashebuckets = new int[newsize];
var newdatas = new Data[newsize];
Array.Copy(Datas, newdatas, Count);
newhashebuckets.Fill(-1);
for(var i = 0; i < Count; i++)
{
var pos = newdatas[i].hashCode % newsize;
var prevpos = newhashebuckets[pos];
newhashebuckets[pos] = i;
if(prevpos != -1)
newdatas[i].next = prevpos;
}
_hashBuckets = newhashebuckets;
Datas = newdatas;
}
private void Initialize(int size)
{
_hashBuckets = new int[size];
Datas = new Data[size];
Count = 0;
_hashBuckets.Fill(-1);
}
public struct Data
{
public uint hashCode;
public int next;
public T value;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment