SHARE
TWEET

Untitled

a guest May 19th, 2017 48 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;
  5. using System.Collections;
  6.  
  7. namespace HashTablesAndSets
  8. {
  9.     public class Test
  10.     {
  11.         static void Main()
  12.         {
  13.             HashTable<char, int> ht = new HashTable<char, int>();
  14.             ht['a'] = 1;
  15.             ht['b'] = 2;
  16.             ht['d'] = 3;
  17.             ht['f'] = 4;
  18.             ht['n'] = 5;
  19.             foreach (var i in ht)
  20.             {
  21.                 Console.WriteLine(ht[i.key]+" ");
  22.             }
  23.            
  24.  
  25.         }
  26.     }
  27.  
  28.     partial class HashTable<TKey, TValue> : IEnumerable<Pair<TKey, TValue>>
  29.     {
  30.         int capacity;
  31.         int count = 0;
  32.         LinkedList<Pair<TKey, TValue>>[] entries;
  33.  
  34.         public HashTable()
  35.         {
  36.             capacity = 16;
  37.             entries = new LinkedList<Pair<TKey, TValue>>[capacity];
  38.             for (int i = 0; i < entries.Length; i++)
  39.             {
  40.                 entries[i] = new LinkedList<Pair<TKey, TValue>>();
  41.             }
  42.         }
  43.  
  44.         IEnumerator<Pair<TKey, TValue>> IEnumerable<Pair<TKey, TValue>>.GetEnumerator()
  45.         {
  46.             return new HashTable<TKey, TValue>.Enumerator(this);
  47.         }
  48.  
  49.         IEnumerator IEnumerable.GetEnumerator()
  50.         {
  51.             return new HashTable<TKey, TValue>.Enumerator(this);
  52.         }
  53.  
  54.         public void Add(TKey key, TValue value)
  55.         {
  56.             int index = key.GetHashCode() % capacity;
  57.             Pair<TKey, TValue> localPair = entries[index].FirstOrDefault(x => x.key.Equals(key));
  58.  
  59.             if (localPair == null)
  60.             {
  61.                 entries[index].AddLast(
  62.                     new LinkedListNode<Pair<TKey, TValue>>(
  63.                         new Pair<TKey, TValue>(key, value)));
  64.                 count++;
  65.                 TryResize();
  66.             }
  67.             else
  68.             {
  69.                 throw new ArgumentException("An item with the same key has already been added.");
  70.             }
  71.         }
  72.  
  73.         public void ChangeValue(TKey key, TValue value)
  74.         {
  75.             int index = key.GetHashCode() % capacity;
  76.             LinkedListNode<Pair<TKey, TValue>> iterator = entries[index].First;
  77.             while (iterator != null && !iterator.Value.key.Equals(key))
  78.             {
  79.                 iterator = iterator.Next;
  80.             }
  81.  
  82.             if (iterator == null)
  83.             {
  84.                 entries[index].AddLast(
  85.                     new LinkedListNode<Pair<TKey, TValue>>(
  86.                         new Pair<TKey, TValue>(key, value)));
  87.                 count++;
  88.                 TryResize();
  89.             }
  90.             else
  91.             {
  92.                 iterator.Value.value = value;
  93.             }
  94.         }
  95.  
  96.         private void TryResize()
  97.         {
  98.             if (count > capacity * 0.75)
  99.             {
  100.                 capacity = capacity * 2;
  101.                 count = 0;
  102.                 var oldEntries = entries;
  103.                 entries = new LinkedList<Pair<TKey, TValue>>[capacity];
  104.                 for (int i = 0; i < entries.Length; i++)
  105.                 {
  106.                     entries[i] = new LinkedList<Pair<TKey, TValue>>();
  107.                 }
  108.                 for (int i = 0; i < oldEntries.Length; i++)
  109.                 {
  110.                     foreach (var j in oldEntries[i])
  111.                     {
  112.                         Add(j.key, j.value);
  113.                     }
  114.                 }
  115.             }
  116.         }
  117.  
  118.         public void Remove(TKey key)
  119.         {
  120.             int index = key.GetHashCode() % capacity;
  121.             LinkedListNode<Pair<TKey, TValue>> iterator = entries[index].First;
  122.             while (iterator != null && !iterator.Value.key.Equals(key))
  123.             {
  124.                 iterator = iterator.Next;
  125.             }
  126.             if (iterator == null)
  127.             {
  128.                 throw new ArgumentException("An item with this key does not exist.");
  129.             }
  130.             else
  131.             {
  132.                 entries[index].Remove(iterator);
  133.                 count--;
  134.             }
  135.         }
  136.  
  137.         public int Count
  138.         {
  139.             get
  140.             {
  141.                 return count;
  142.             }
  143.         }
  144.  
  145.         public void Clear()
  146.         {
  147.             for (int i = 0; i < entries.Length; i++)
  148.             {
  149.                 entries[i].Clear();
  150.             }
  151.             count = 0;
  152.         }
  153.  
  154.         public TValue Find(TKey key)
  155.         {
  156.             int index = key.GetHashCode() % capacity;
  157.             LinkedListNode<Pair<TKey, TValue>> iterator = entries[index].First;
  158.             while (iterator != null && !iterator.Value.key.Equals(key))
  159.             {
  160.                 iterator = iterator.Next;
  161.             }
  162.             if (iterator == null)
  163.             {
  164.                 throw new ArgumentException("Key does not exist.");
  165.             }
  166.             else
  167.             {
  168.                 return iterator.Value.value;
  169.             }
  170.         }
  171.         public TValue this[TKey key]
  172.         {
  173.             get
  174.             {
  175.                 return Find(key);
  176.             }
  177.             set
  178.             {
  179.                 ChangeValue(key, value);
  180.             }
  181.         }
  182.     }
  183. }
RAW Paste Data
Want to get better at C#?
Learn to code C# in 2017
Pastebin PRO Summer Special!
Get 40% OFF on Pastebin PRO accounts!
Top