Created
August 3, 2018 07:27
-
-
Save mjs3339/1e443f1e9d2476f21c3829cf308a340a to your computer and use it in GitHub Desktop.
C# A Small HashSet for Quick Loading & Lookups
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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