Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement