Pastebin is 300% more awesome when you are logged in. Sign Up, it's FREE!
Guest

Untitled

By: a guest on Sep 26th, 2010  |  syntax: C#  |  size: 5.34 KB  |  hits: 608  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. namespace EfficientHashTables
  2. {
  3.     public class Efficient64bitHashTable<T>
  4.     {
  5.         private class element
  6.         {
  7.             public ulong _key;
  8.             public T _value;
  9.         };
  10.         private element[][] _buckets;
  11.         private uint _capacity;
  12.  
  13.         public Efficient64bitHashTable()
  14.         {
  15.             _capacity = 214373;    // some prime number
  16.             _buckets = new element[_capacity][];
  17.         }
  18.         public Efficient64bitHashTable(uint capacity)
  19.         {
  20.             _capacity = capacity;
  21.             _buckets = new element[_capacity][];
  22.         }
  23.  
  24.         public uint hash(ulong key)
  25.         {
  26.             return (uint) (key % _capacity);
  27.         }
  28.  
  29.         public void Add(ulong key, T value)
  30.         {
  31.             uint hsh = hash(key);
  32.             element[] e;
  33.             if (_buckets[hsh] == null)
  34.                 _buckets[hsh] = e = new element[1];
  35.             else
  36.             {
  37.                 foreach (var elem in _buckets[hsh])
  38.                     if (elem._key == key)
  39.                     {
  40.                         elem._value = value;
  41.                         return;
  42.                     }
  43.                 e = new element[_buckets[hsh].Length + 1];
  44.                 Array.Copy(_buckets[hsh], 0, e, 1, _buckets[hsh].Length);
  45.                 _buckets[hsh] = e;
  46.             }
  47.             e[0] = new element { _key = key, _value = value };
  48.         }
  49.  
  50.         public T Get(ulong key)
  51.         {
  52.             uint hsh = hash(key);
  53.             element[] e = _buckets[hsh];
  54.             if (e == null) return default(T);
  55.             foreach (var f in e)
  56.                 if (f._key == key)
  57.                     return f._value;
  58.             return default(T);
  59.         }
  60.  
  61.         public bool Has(ulong key)
  62.         {
  63.             uint hsh = hash(key);
  64.             element[] e = _buckets[hsh];
  65.             if (e == null) return false;
  66.             foreach (var f in e)
  67.                 if (f._key == key)
  68.                     return true;
  69.             return false;
  70.         }
  71.  
  72.         public int Count()
  73.         {
  74.             int r = 0;
  75.             foreach (var e in _buckets)
  76.                 if (e != null)
  77.                     r += e.Length;
  78.             return r;
  79.         }
  80.     }
  81.  
  82.     public class Efficient32bitHashTableInt
  83.     {
  84.         private class element
  85.         {
  86.             public uint _key;
  87.             public int _value;
  88.         };
  89.         private element[][] _buckets;
  90.         private uint _capacity;
  91.  
  92.         public Efficient32bitHashTableInt()
  93.         {
  94.             _capacity = 463;    // some prime number
  95.             _buckets = new element[_capacity][];
  96.         }
  97.         public Efficient32bitHashTableInt(uint capacity)
  98.         {
  99.             _capacity = capacity;
  100.             _buckets = new element[_capacity][];
  101.         }
  102.  
  103.         public uint hash(uint key)
  104.         {
  105.             return (uint) (key % _capacity);
  106.         }
  107.  
  108.         public void Add(uint key, int value)
  109.         {
  110.             uint hsh = hash(key);
  111.             element[] e;
  112.             if (_buckets[hsh] == null)
  113.                 _buckets[hsh] = e = new element[1];
  114.             else
  115.             {
  116.                 foreach (var elem in _buckets[hsh])
  117.                     if (elem._key == key)
  118.                     {
  119.                         elem._value = value;
  120.                         return;
  121.                     }
  122.                 e = new element[_buckets[hsh].Length + 1];
  123.                 Array.Copy(_buckets[hsh], 0, e, 1, _buckets[hsh].Length);
  124.                 _buckets[hsh] = e;
  125.             }
  126.             e[0] = new element { _key = key, _value = value };
  127.         }
  128.  
  129.         public void Inc(uint key)
  130.         {
  131.             uint hsh = hash(key);
  132.             if (_buckets[hsh] == null)
  133.             {
  134.                 _buckets[hsh] = new element[1] { new element { _key = key, _value = 1 } };
  135.                 return;
  136.             }
  137.  
  138.             foreach (var elem in _buckets[hsh])
  139.                 if (elem._key == key)
  140.                 {
  141.                     elem._value++;
  142.                     return;
  143.                 }
  144.  
  145.             var e = new element[_buckets[hsh].Length + 1];
  146.             Array.Copy(_buckets[hsh], 0, e, 1, _buckets[hsh].Length);
  147.             _buckets[hsh] = e;
  148.             e[0] = new element { _key = key, _value = 1 };
  149.         }
  150.  
  151.         public int Get(uint key)
  152.         {
  153.             uint hsh = hash(key);
  154.             element[] e = _buckets[hsh];
  155.             if (e == null) return 0;
  156.             foreach (var f in e)
  157.                 if (f._key == key)
  158.                     return f._value;
  159.             return 0;
  160.         }
  161.  
  162.         public int Count()
  163.         {
  164.             int r = 0;
  165.             foreach (var e in _buckets)
  166.                 if (e != null)
  167.                     r += e.Length;
  168.             return r;
  169.         }
  170.  
  171.         public uint Max()
  172.         {
  173.             uint maxKey = 0;
  174.             int maxValue = 0;
  175.             for (int i = 0; i < _buckets.Length; i++)
  176.                 if (_buckets[i] != null)
  177.                     for (int j = 0; j < _buckets[i].Length; j++)
  178.                         if (_buckets[i][j]._value > maxValue)
  179.                         {
  180.                             maxValue = _buckets[i][j]._value;
  181.                             maxKey = _buckets[i][j]._key;
  182.                         }
  183.             return maxKey;
  184.         }
  185.     }
  186. }