SHARE
TWEET

Untitled

a guest May 19th, 2017 45 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.     class HashTable<KeyType, ValueType>
  2.     {
  3.         const int MINSIZE = 89;
  4.         const int MASK = 0x7fffffff;
  5.  
  6.         public HashTable()
  7.         {
  8.             addedElements = 0;
  9.             stepsSinceLastResize = 0;
  10.             chain = AllocArray(MINSIZE);
  11.         }
  12.  
  13.         public int Count
  14.         {
  15.             get { return addedElements; }
  16.         }
  17.  
  18.         public void Remove(KeyType key)
  19.         {
  20.             int hash = key.GetHashCode() & MASK;
  21.             int smallHash = hash % chain.Length;
  22.  
  23.             foreach (var item in chain[smallHash])
  24.             {
  25.                 if (hash == (item.Key.GetHashCode() & MASK))
  26.                 {
  27.                     if (key.Equals(item.Key))
  28.                     {
  29.                         chain[smallHash].Remove(item);
  30.                         addedElements--;
  31.                         TryResize();
  32.                         return;
  33.                     }
  34.                 }
  35.             }
  36.         }
  37.  
  38.         public ValueType Find(KeyType key)
  39.         {
  40.             int hash = key.GetHashCode() & MASK;
  41.             int smallHash = hash % chain.Length;
  42.  
  43.             foreach (var item in chain[smallHash])
  44.             {
  45.                 if (hash == (item.Key.GetHashCode() & MASK))
  46.                 {
  47.                     if (key.Equals(item.Key))
  48.                     {
  49.                         return item.Value;
  50.                     }
  51.                 }
  52.             }
  53.  
  54.             throw new KeyNotFoundException();
  55.         }
  56.  
  57.         public void Add(KeyType key, ValueType value)
  58.         {
  59.             try
  60.             {
  61.                 Find(key);
  62.             }
  63.             catch (KeyNotFoundException)
  64.             {
  65.                 int hash = key.GetHashCode() & MASK;
  66.                 int smallHash = hash % chain.Length;
  67.  
  68.                 KeyValuePair<KeyType, ValueType> node = new KeyValuePair<KeyType, ValueType>(key, value);
  69.  
  70.                 chain[smallHash].AddLast(node);
  71.                 addedElements++;
  72.                 TryResize();
  73.             }
  74.         }
  75.  
  76.         public void Replace(KeyType key, ValueType value)
  77.         {
  78.             int hash = key.GetHashCode() & MASK;
  79.             int smallHash = hash % chain.Length;
  80.  
  81.             foreach (var item in chain[smallHash])
  82.             {
  83.                 if (hash == (item.Key.GetHashCode() & MASK))
  84.                 {
  85.                     if (key.Equals(item.Key))
  86.                     {
  87.                         chain[smallHash].Remove(item);
  88.                         chain[smallHash].AddLast(new KeyValuePair<KeyType, ValueType>(key, value));
  89.                         return;
  90.                     }
  91.                 }
  92.             }
  93.  
  94.             throw new KeyNotFoundException();
  95.         }
  96.  
  97.         public ValueType this[KeyType key]
  98.         {
  99.             get
  100.             {
  101.                 ValueType value;
  102.  
  103.                 try
  104.                 {
  105.                     value = Find(key);
  106.                 }
  107.                 catch
  108.                 {
  109.                     throw;
  110.                 }
  111.  
  112.                 return value;
  113.             }
  114.  
  115.             set
  116.             {
  117.                 try
  118.                 {
  119.                     Replace(key, value);
  120.                 }
  121.                 catch
  122.                 {
  123.                     Add(key, value);
  124.                 }
  125.             }
  126.         }
  127.  
  128.         private LinkedList<KeyValuePair<KeyType, ValueType>>[] AllocArray(int newSize)
  129.         {
  130.             LinkedList<KeyValuePair<KeyType, ValueType>>[] newChain = new LinkedList<KeyValuePair<KeyType, ValueType>>[newSize];
  131.  
  132.             for (int i = 0; i < newChain.Length; i++)
  133.             {
  134.                 newChain[i] = new LinkedList<KeyValuePair<KeyType, ValueType>>();
  135.             }
  136.  
  137.             return newChain;
  138.         }
  139.  
  140.         private void ResizeArray(int newSize)
  141.         {
  142.             LinkedList<KeyValuePair<KeyType, ValueType>>[] newChain = AllocArray(newSize);
  143.             LinkedList<KeyValuePair<KeyType, ValueType>>[] oldChain = chain;
  144.             chain = newChain;
  145.             addedElements = 0;
  146.  
  147.             foreach (var LinkedList in oldChain)
  148.             {
  149.                 foreach (var item in LinkedList)
  150.                 {
  151.                     int hash = item.Key.GetHashCode() & MASK;
  152.                     int smallHash = hash % chain.Length;
  153.  
  154.                     chain[smallHash].AddLast(item);
  155.                     addedElements++;
  156.                 }
  157.             }
  158.  
  159.             stepsSinceLastResize = 0;
  160.         }
  161.  
  162.         private void TryResize()
  163.         {
  164.             stepsSinceLastResize++;
  165.  
  166.             if (stepsSinceLastResize < chain.Length / 3)
  167.             {
  168.                 return;
  169.             }
  170.  
  171.             double ratio = addedElements / (double)chain.Length;
  172.  
  173.             if (ratio > 0.75)
  174.             {
  175.                 int newSize = chain.Length * 2 + 1;
  176.  
  177.                 ResizeArray(newSize);
  178.             }
  179.  
  180.             if (ratio < 0.25 && chain.Length > MINSIZE)
  181.             {
  182.                 int newSize = (chain.Length - 1) / 2;
  183.  
  184.                 ResizeArray(newSize);
  185.             }
  186.         }
  187.  
  188.         private LinkedList<KeyValuePair<KeyType, ValueType>>[] chain;
  189.         private int addedElements;
  190.         private int stepsSinceLastResize;
  191.     };
RAW Paste Data
Top