fork download
copy 
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;
  5. using System.Collections;
  6.  
  7. namespace _04_MyHashTable
  8. {
  9.     class CustomHashTable<K, V> : IEnumerable<KeyValuePair<K, V>>
  10.     {
  11.         private const int defaultCapacity = 16;
  12.  
  13.         private LinkedList<KeyValuePair<K, V>>[] table;
  14.         private int count;
  15.         private int currentCapacity;
  16.  
  17.         public CustomHashTable()
  18.             : this(defaultCapacity)
  19.         { }
  20.         public CustomHashTable(int capacity)
  21.         {
  22.             this.currentCapacity = capacity;
  23.             this.table = new LinkedList<KeyValuePair<K, V>>[capacity];
  24.             this.count = 0;
  25.         }
  26.  
  27.         public int Count
  28.         {
  29.             get { return this.count; }
  30.         }
  31.         public int CurrentCapacity
  32.         {
  33.             get { return this.currentCapacity; }
  34.         }
  35.         public V this[K key]
  36.         {
  37.             get 
  38.             {
  39.                 return this.Find(key);
  40.             }
  41.             set
  42.             {
  43.                 if (this.FindKey(key))
  44.                 {
  45.                     this.Remove(key);
  46.                     this.Add(key, value);
  47.                 }
  48.                 else
  49.                 {
  50.                     this.Add(key, value);
  51.                 }
  52.             }
  53.         }
  54.         public List<K> Keys
  55.         {
  56.             get 
  57.             {
  58.                 List<K> result = new List<K>();
  59.                 foreach (LinkedList<KeyValuePair<K, V>> chain in this.table)
  60.                 {
  61.                     if (chain != null)
  62.                     {
  63.                         foreach (KeyValuePair<K, V> pair in chain)
  64.                         {
  65.                             result.Add(pair.Key);
  66.                         }
  67.                     }
  68.                 }
  69.                 return result;
  70.             }
  71.         }
  72.  
  73.         private void AutoGrow()
  74.         {
  75.             int newCapacity = 2 * this.table.Length;
  76.             LinkedList<KeyValuePair<K, V>>[] oldTable = this.table;
  77.             this.currentCapacity = newCapacity;
  78.             this.table = new LinkedList<KeyValuePair<K, V>>[newCapacity];
  79.             foreach (LinkedList<KeyValuePair<K, V>> oldChain in oldTable)
  80.             {
  81.                 if (oldChain != null)
  82.                 {
  83.                     foreach (KeyValuePair<K, V> pair in oldChain)
  84.                     {
  85.                         int index = this.CalcIndex(pair.Key);
  86.                         if (this.table[index] == null)
  87.                         {
  88.                             this.table[index] = new LinkedList<KeyValuePair<K, V>>();
  89.                             this.table[index].AddFirst(pair);
  90.                         }
  91.                         else
  92.                         {
  93.                             this.table[index].AddLast(pair);
  94.                         }
  95.                     }
  96.                 }
  97.             }
  98.         }
  99.         private int CalcIndex(K key)
  100.         {
  101.             int index = key.GetHashCode();
  102.             index = Math.Abs(index % this.table.Length);
  103.             return index;
  104.         }
  105.         private bool FindKey(K key)
  106.         {
  107.             int index = this.CalcIndex(key);
  108.             if (this.table[index] != null)
  109.             {
  110.                 foreach (KeyValuePair<K, V> pair in table[index])
  111.                 {
  112.                     if (pair.Key.Equals(key))
  113.                     {
  114.                         return true;
  115.                     }
  116.                 }
  117.                 return false;
  118.             }
  119.             else
  120.             {
  121.                 return false;
  122.             }
  123.         }
  124.  
  125.         public void Add(K key, V value)
  126.         {
  127.             KeyValuePair<K, V> pair = new KeyValuePair<K, V>(key, value);            
  128.             if (this.count + 1 > this.currentCapacity * 0.75)
  129.             {
  130.                 this.AutoGrow();
  131.             }
  132.             int index = this.CalcIndex(key);
  133.             if (this.table[index] == null)
  134.             {
  135.                 this.table[index] = new LinkedList<KeyValuePair<K, V>>();
  136.                 this.table[index].AddFirst(pair);
  137.             }
  138.             else
  139.             {
  140.                 this.table[index].AddLast(pair);
  141.             }
  142.             this.count++;
  143.         }
  144.         public void Remove(K key)
  145.         {
  146.             int index = this.CalcIndex(key);
  147.             KeyValuePair<K, V> toRemove = new KeyValuePair<K, V>();
  148.             if (this.table[index] != null)
  149.             {                
  150.                 foreach (KeyValuePair<K, V> pair in table[index])
  151.                 {
  152.                     if (pair.Key.Equals(key))
  153.                     {
  154.                         toRemove = pair;
  155.                     }
  156.                 }
  157.             }
  158.             this.table[index].Remove(toRemove);
  159.             this.count--;
  160.         }
  161.         public V Find(K key)
  162.         {
  163.             int index = this.CalcIndex(key);
  164.             if (this.table[index] != null)
  165.             {
  166.                 foreach (KeyValuePair<K, V> pair in table[index])
  167.                 {
  168.                     if (pair.Key.Equals(key))
  169.                     {
  170.                         return pair.Value;
  171.                     }
  172.                 }
  173.                 throw new KeyNotFoundException(string.Format("There is NO element with key = {0}", key));
  174.             }
  175.             else
  176.             {
  177.                 throw new KeyNotFoundException(string.Format("There is NO element with key = {0}", key));
  178.             }           
  179.         }
  180.         public void Clear()
  181.         {
  182.             this.currentCapacity = defaultCapacity;
  183.             this.table = new LinkedList<KeyValuePair<K, V>>[defaultCapacity];
  184.             this.count = 0;
  185.         }
  186.  
  187.         IEnumerator IEnumerable.GetEnumerator()
  188.         {
  189.             return ((IEnumerable<KeyValuePair<K, V>>)this).GetEnumerator();
  190.         }
  191.         IEnumerator<KeyValuePair<K, V>> IEnumerable<KeyValuePair<K, V>>.GetEnumerator()
  192.         {
  193.             foreach (LinkedList<KeyValuePair<K, V>> chain in this.table)
  194.             {
  195.                 if (chain != null)
  196.                 {
  197.                     foreach (KeyValuePair<K, V> pair in chain)
  198.                     {
  199.                         yield return pair;
  200.                     }
  201.                 }
  202.             }    
  203.         }
  204.     }
  205. }
  206.  
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/GKtIb
language:
C# (gmcs 5.20.1)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!