SHARE
TWEET

Untitled

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