namespace EfficientHashTables
{
public class Efficient64bitHashTable<T>
{
private class element
{
public ulong _key;
public T _value;
};
private element[][] _buckets;
private uint _capacity;
public Efficient64bitHashTable()
{
_capacity = 214373; // some prime number
_buckets = new element[_capacity][];
}
public Efficient64bitHashTable(uint capacity)
{
_capacity = capacity;
_buckets = new element[_capacity][];
}
public uint hash(ulong key)
{
return (uint) (key % _capacity);
}
public void Add(ulong key, T value)
{
uint hsh = hash(key);
element[] e;
if (_buckets[hsh] == null)
_buckets[hsh] = e = new element[1];
else
{
foreach (var elem in _buckets[hsh])
if (elem._key == key)
{
elem._value = value;
return;
}
e = new element[_buckets[hsh].Length + 1];
Array.Copy(_buckets[hsh], 0, e, 1, _buckets[hsh].Length);
_buckets[hsh] = e;
}
e[0] = new element { _key = key, _value = value };
}
public T Get(ulong key)
{
uint hsh = hash(key);
element[] e = _buckets[hsh];
if (e == null) return default(T);
foreach (var f in e)
if (f._key == key)
return f._value;
return default(T);
}
public bool Has(ulong key)
{
uint hsh = hash(key);
element[] e = _buckets[hsh];
if (e == null) return false;
foreach (var f in e)
if (f._key == key)
return true;
return false;
}
public int Count()
{
int r = 0;
foreach (var e in _buckets)
if (e != null)
r += e.Length;
return r;
}
}
public class Efficient32bitHashTableInt
{
private class element
{
public uint _key;
public int _value;
};
private element[][] _buckets;
private uint _capacity;
public Efficient32bitHashTableInt()
{
_capacity = 463; // some prime number
_buckets = new element[_capacity][];
}
public Efficient32bitHashTableInt(uint capacity)
{
_capacity = capacity;
_buckets = new element[_capacity][];
}
public uint hash(uint key)
{
return (uint) (key % _capacity);
}
public void Add(uint key, int value)
{
uint hsh = hash(key);
element[] e;
if (_buckets[hsh] == null)
_buckets[hsh] = e = new element[1];
else
{
foreach (var elem in _buckets[hsh])
if (elem._key == key)
{
elem._value = value;
return;
}
e = new element[_buckets[hsh].Length + 1];
Array.Copy(_buckets[hsh], 0, e, 1, _buckets[hsh].Length);
_buckets[hsh] = e;
}
e[0] = new element { _key = key, _value = value };
}
public void Inc(uint key)
{
uint hsh = hash(key);
if (_buckets[hsh] == null)
{
_buckets[hsh] = new element[1] { new element { _key = key, _value = 1 } };
return;
}
foreach (var elem in _buckets[hsh])
if (elem._key == key)
{
elem._value++;
return;
}
var e = new element[_buckets[hsh].Length + 1];
Array.Copy(_buckets[hsh], 0, e, 1, _buckets[hsh].Length);
_buckets[hsh] = e;
e[0] = new element { _key = key, _value = 1 };
}
public int Get(uint key)
{
uint hsh = hash(key);
element[] e = _buckets[hsh];
if (e == null) return 0;
foreach (var f in e)
if (f._key == key)
return f._value;
return 0;
}
public int Count()
{
int r = 0;
foreach (var e in _buckets)
if (e != null)
r += e.Length;
return r;
}
public uint Max()
{
uint maxKey = 0;
int maxValue = 0;
for (int i = 0; i < _buckets.Length; i++)
if (_buckets[i] != null)
for (int j = 0; j < _buckets[i].Length; j++)
if (_buckets[i][j]._value > maxValue)
{
maxValue = _buckets[i][j]._value;
maxKey = _buckets[i][j]._key;
}
return maxKey;
}
}
}