SHARE
TWEET

Untitled

a guest May 19th, 2017 50 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. namespace HashTable
  2. {
  3.     class HashTable<K, V>
  4.     {
  5.         private const int DEFAULT_CAPACITY = 16;
  6.         private const double loadFactor = 0.75;
  7.         private int CURRENT_CAPACITY;
  8.         private int size;
  9.         public LinkedList<KeyValuePair<K, V>>[] keys;
  10.  
  11.         public HashTable(int capacity)
  12.         {
  13.             keys = new LinkedList<KeyValuePair<K, V>>[capacity];
  14.             this.size = 0;
  15.             CURRENT_CAPACITY = capacity;
  16.         }
  17.  
  18.         public HashTable()
  19.             : this(DEFAULT_CAPACITY)
  20.         {
  21.         }
  22.  
  23.         public LinkedList<K> Keys
  24.         {
  25.             get
  26.             {
  27.                 LinkedList<K> result = new LinkedList<K>();
  28.                 for (int pos = 0; pos < keys.Length; pos++)
  29.                 {
  30.                     if (keys[pos] != null)
  31.                     {
  32.                         foreach (var item in keys[pos])
  33.                         {
  34.                             result.AddLast(item.Key);
  35.                         }
  36.                     }
  37.                 }
  38.                 return result;
  39.             }
  40.         }
  41.  
  42.         public int Count
  43.         {
  44.             get { return size; }
  45.         }
  46.  
  47.         public V this[K argument]
  48.         {
  49.             get { return this.Find(argument); }
  50.  
  51.             set
  52.             {
  53.                 this.Remove(argument);
  54.                 this.Add(argument, value);
  55.             }
  56.         }
  57.        
  58.  
  59.         public void Add(K key, V value)
  60.         {
  61.             KeyValuePair<K, V> newPair = new KeyValuePair<K, V>(key, value);
  62.             int hash = key.GetHashCode() % CURRENT_CAPACITY;
  63.             if (keys[hash] == null)
  64.             {
  65.                 keys[hash] = new LinkedList<KeyValuePair<K, V>>();
  66.             }
  67.             keys[hash].AddLast(newPair);
  68.             size++;
  69.             if (loadFactor <= size / CURRENT_CAPACITY)
  70.             {
  71.                 Resize();
  72.             }
  73.         }
  74.  
  75.         private void Resize()
  76.         {
  77.             CURRENT_CAPACITY *= 2;
  78.             HashTable<K, V> container = new HashTable<K, V>(CURRENT_CAPACITY);
  79.             for (int pos = 0; pos < keys.Length; pos++)
  80.             {
  81.                 if (keys[pos] != null)
  82.                 {
  83.                     foreach (var pair in keys[pos])
  84.                     {
  85.                         container.Add(pair.Key, pair.Value);
  86.                     }
  87.                 }
  88.             }
  89.             this.keys = container.keys;
  90.         }
  91.  
  92.         public V Find(K key)
  93.         {
  94.             int position = key.GetHashCode();
  95.             foreach (var pair in keys[position])
  96.             {
  97.                 if (pair.Key.Equals(key))
  98.                 {
  99.                     return pair.Value;
  100.                 }
  101.             }
  102.             return default(V);
  103.         }
  104.  
  105.         public bool Remove(K key)
  106.         {
  107.             int hash = key.GetHashCode() % CURRENT_CAPACITY;
  108.             if (keys[hash] != null && keys[hash].Remove(new KeyValuePair<K, V>(key, default(V))))
  109.                     {
  110.                         this.size--;
  111.                         return true;
  112.                     }
  113.             return false;
  114.         }
  115.     }
  116. }
RAW Paste Data
Top