CS 2420 - Assignment 7 - Hash Table

This week we had to write a hash table, also known as a dictionary. Hash tables are really nice because you can index with more than just integers, and they are faster running times than a regular array or a linked list.

Here is my code:

	namespace Assignment7
	{
	class Hero
	{
	public string Name { get; set; }
	public int Attack { get; set; }
	public override int GetHashCode()
	{
	return (Name.GetHashCode() ^ Attack.GetHashCode());
	}
	public override bool Equals(object obj)
	{
	Hero other = (Hero)obj;
	return Name == other.Name && Attack == other.Attack;
	}
	}
	}

view raw Hero.cs hosted with ❤ by GitHub

	using System;
	using System.Collections.Generic;
	using System.Diagnostics;
	namespace Assignment7
	{
	class MainClass
	{
	public static void Main()
	{
	NumberTable();
	HeroTable();
	}
	public static void NumberTable()
	{
	MyHashTable<int, int> number_table = new MyHashTable<int, int>();
	int[] first_list = new int[] { 5, 8, 19, 39, 13, 99, 40, 38, 84, 66, 75, 1, 45, 92 };
	int[] second_list = new int[] { 6, 9, 20, 43, 14, 100, 41, 37, 85, 67, 76, 2, 46, 3 };
	foreach (int number in first_list)
	number_table.Add(new KeyValuePair<int, int>(number, number));
	foreach (int number in second_list)
	number_table.Add(number, number);
	number_table[55] = 4;
	Console.WriteLine("Values in the Interger Hashtable: {0}\n", string.Join(", ", number_table));
	Console.WriteLine("Keys in the Integer Hashtable: {0}\n", string.Join(", ", number_table.Keys));
	Console.WriteLine("Values in the Integer Hashtable: {0}\n", string.Join(", ", number_table.Values));
	Console.WriteLine("Does the Hashtable contain the Key 101: {0}\n", number_table.ContainsKey(101));
	TestCount(29, number_table.Count, "Element count doesn't match!");
	Console.WriteLine("Elements in the Hashtable: {0}\n", number_table.Count);
	Console.WriteLine("---------------------------------------------------------\n");
	}
	public static void HeroTable()
	{
	MyHashTable<string, int> hero_table = new MyHashTable<string, int>();
	List<Hero> adc_list = new List<Hero>();
	adc_list.Add(new Hero { Name = "Ashe", Attack = 57 });
	adc_list.Add(new Hero { Name = "Jinx", Attack = 58 });
	adc_list.Add(new Hero { Name = "Varus", Attack = 55 });
	adc_list.Add(new Hero { Name = "Vayne", Attack = 56 });
	adc_list.Add(new Hero { Name = "Kalista", Attack = 63 });
	adc_list.Add(new Hero { Name = "Jhin", Attack = 53 });
	adc_list.Add(new Hero { Name = "Caitlyn", Attack = 54 });
	adc_list.Add(new Hero { Name = "Draven", Attack = 56 });
	adc_list.Add(new Hero { Name = "Graves", Attack = 61 });
	adc_list.Add(new Hero { Name = "Lucian", Attack = 57 });
	List<Hero> bruiser_list = new List<Hero>();
	bruiser_list.Add(new Hero { Name = "Garen", Attack = 58 });
	bruiser_list.Add(new Hero { Name = "Fiora", Attack = 60 });
	bruiser_list.Add(new Hero { Name = "Darius", Attack = 56 });
	bruiser_list.Add(new Hero { Name = "Vi", Attack = 56 });
	bruiser_list.Add(new Hero { Name = "Wukong", Attack = 60 });
	bruiser_list.Add(new Hero { Name = "Shyvana", Attack = 61 });
	bruiser_list.Add(new Hero { Name = "Olaf", Attack = 60 });
	bruiser_list.Add(new Hero { Name = "Pantheon", Attack = 56 });
	bruiser_list.Add(new Hero { Name = "Riven", Attack = 56 });
	bruiser_list.Add(new Hero { Name = "Illaoi", Attack = 60 });
	foreach (Hero adc in adc_list)
	{
	hero_table.Add(new KeyValuePair<string, int>(adc.Name, adc.Attack));
	}
	foreach (Hero bruiser in bruiser_list)
	{
	hero_table.Add(bruiser.Name, bruiser.Attack);
	}
	hero_table["Irelia"] = 62;
	Console.WriteLine("Values in the Hero Hashtable: {0}\n", string.Join(", ", hero_table));
	Console.WriteLine("Keys in the Hero Hashtable: {0}\n", string.Join(", ", hero_table.Keys));
	Console.WriteLine("Values in the Hero Hashtable: {0}\n", string.Join(", ", hero_table.Values));
	Console.WriteLine("Does the Hashtable contain the Key 'Ahri': {0}\n", hero_table.ContainsKey("Ahri"));
	TestCount(21, hero_table.Count, "Element count doesn't match!");
	Console.WriteLine("Elements in the Hashtable: {0}\n", hero_table.Count);
	}
	private static void TestCount(int expect, int actual, string error)
	{
	Debug.Assert(expect == actual, error);
	}
	}
	}

view raw MainClass.cs hosted with ❤ by GitHub

	using System;
	using System.Collections;
	using System.Collections.Generic;
	namespace Assignment7
	{
	class MyHashTable<TKey, TValue> : IDictionary<TKey, TValue>
	{
	LinkedList<KeyValuePair<TKey, TValue>>[] BaseArray;
	private int ElementCount = 0;
	public MyHashTable()
	{
	BaseArray = new LinkedList<KeyValuePair<TKey, TValue>>[5];
	}
	public TValue this[TKey key]
	{
	get
	{
	int bucket = GetHash(key);
	if (BaseArray[bucket] == null)
	throw new KeyNotFoundException();
	foreach (KeyValuePair<TKey, TValue> pair in BaseArray[bucket])
	if (pair.Key.Equals(key))
	return pair.Value;
	throw new KeyNotFoundException();
	}
	set
	{
	Insert(key, value, false);
	}
	}
	public int Count
	{
	get
	{
	return ElementCount;
	}
	}
	public bool IsReadOnly
	{
	get
	{
	return false;
	}
	}
	public ICollection<TKey> Keys
	{
	get
	{
	List<TKey> list = new List<TKey>(Count);
	for (int bucket = 0; bucket < BaseArray.Length; bucket++)
	if (BaseArray[bucket] != null)
	foreach (KeyValuePair<TKey, TValue> pair in BaseArray[bucket])
	list.Add(pair.Key);
	return list;
	}
	}
	public ICollection<TValue> Values
	{
	get
	{
	List<TValue> list = new List<TValue>(Count);
	for (int bucket = 0; bucket < BaseArray.Length; bucket++)
	if (BaseArray[bucket] != null)
	foreach (KeyValuePair<TKey, TValue> pair in BaseArray[bucket])
	list.Add(pair.Value);
	return list;
	}
	}
	public void Add(KeyValuePair<TKey, TValue> item)
	{
	Insert(item.Key, item.Value, true);
	}
	public void Add(TKey key, TValue value)
	{
	Insert(key, value, true);
	}
	private void Insert(TKey key, TValue value, bool add)
	{
	if (GetRatio() > .75)
	Resize();
	int bucket = GetHash(key);
	if (BaseArray[bucket] == null)
	{
	BaseArray[bucket] = new LinkedList<KeyValuePair<TKey, TValue>>();
	BaseArray[bucket].AddFirst(new KeyValuePair<TKey, TValue>(key, value));
	ElementCount++;
	return;
	}
	LinkedList<KeyValuePair<TKey, TValue>> list = BaseArray[bucket];
	for (LinkedListNode<KeyValuePair<TKey, TValue>> pair = list.First; pair != null; pair = pair.Next)
	{
	if (pair.Value.Key.Equals(key) && add)
	{
	throw new ArgumentException("An item with the same key has already been added.");
	}
	else if (pair.Value.Key.Equals(key) && !add)
	{
	list.Remove(pair);
	list.AddLast(new KeyValuePair<TKey, TValue>(key, value));
	return;
	}
	}
	BaseArray[bucket].AddLast(new KeyValuePair<TKey, TValue>(key, value));
	ElementCount++;
	}
	public int GetNextPrime()
	{
	bool skipped = false;
	for (int i = BaseArray.Length + 2; i < 1000; i += 2)
	{
	bool prime = IsPrime(i);
	if (prime == true && skipped == true)
	return i;
	else if (prime && !skipped)
	skipped = true;
	}
	return (2 * BaseArray.Length) + 1;
	}
	public bool IsPrime(int candidate)
	{
	if ((candidate & 1) == 0)
	if (candidate == 2)
	return true;
	else
	return false;
	for (int i = 3; (i * i) <= candidate; i += 2)
	if ((candidate % i) == 0)
	return false;
	return candidate != 1;
	}
	private void Resize()
	{
	LinkedList<KeyValuePair<TKey, TValue>>[] old_array = BaseArray;
	LinkedList<KeyValuePair<TKey, TValue>>[] new_array = new LinkedList<KeyValuePair<TKey, TValue>>[GetNextPrime()];
	BaseArray = new_array;
	ElementCount = 0;
	for (int index = 0; index < old_array.Length; index++)
	if (old_array[index] != null)
	foreach (KeyValuePair<TKey, TValue> pair in old_array[index])
	Add(pair);
	}
	public void Clear()
	{
	BaseArray = new LinkedList<KeyValuePair<TKey, TValue>>[5];
	ElementCount = 0;
	}
	public bool Contains(KeyValuePair<TKey, TValue> item)
	{
	for (int index = 0; index < BaseArray.Length; index++)
	if (BaseArray[index] != null)
	{
	LinkedList<KeyValuePair<TKey, TValue>> list = BaseArray[index];
	foreach (KeyValuePair<TKey, TValue> pair in list)
	if (pair.Key.Equals(item.Key) && pair.Value.Equals(item.Value))
	return true;
	}
	return false;
	}
	public bool ContainsKey(TKey key)
	{
	var temp = Keys;
	foreach (TKey entry in temp)
	if (entry.Equals(key))
	return true;
	return false;
	}
	public void CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex)
	{
	// Not needed.
	throw new NotImplementedException();
	}
	public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
	{
	for (int index = 0; index < BaseArray.Length; index++)
	if (BaseArray[index] != null)
	{
	LinkedList<KeyValuePair<TKey, TValue>> list = BaseArray[index];
	foreach (KeyValuePair<TKey, TValue> pair in list)
	yield return pair;
	}
	}
	public bool Remove(KeyValuePair<TKey, TValue> item)
	{
	for (int index = 0; index < BaseArray.Length; index++)
	foreach (KeyValuePair<TKey, TValue> pair in BaseArray[index])
	if (pair.Equals(item)) //(pair.Value.Equals(item))
	{
	BaseArray[index].Remove(item);
	return true;
	}
	return false;
	}
	public bool Remove(TKey key)
	{
	int index = GetHash(key);
	if (BaseArray[index] == null)
	return false;
	foreach (KeyValuePair<TKey, TValue> pair in BaseArray[index])
	if (pair.Key.Equals(key))
	{
	BaseArray[index].Remove(pair);
	return true;
	}
	return false;
	}
	public bool TryGetValue(TKey key, out TValue value)
	{
	int bucket = GetHash(key);
	if (BaseArray[bucket] == null)
	{
	value = default(TValue);
	return false;
	}
	foreach (KeyValuePair<TKey, TValue> pair in BaseArray[bucket])
	if (pair.Key.Equals(key))
	{
	value = pair.Value;
	return true;
	}
	value = default(TValue);
	return false;
	}
	IEnumerator IEnumerable.GetEnumerator()
	{
	return GetEnumerator();
	}
	private bool InList(LinkedList<KeyValuePair<TKey, TValue>> list, TKey key)
	{
	foreach (KeyValuePair<TKey, TValue> pair in list)
	if (pair.Key.Equals(key))
	return true;
	return false;
	}
	private int GetHash(TKey key)
	{
	int hash = Math.Abs(key.GetHashCode());
	return hash % BaseArray.Length;
	}
	private double GetRatio()
	{
	double ratio = (double)ElementCount / (double)BaseArray.Length;
	return ratio;
	}
	}
	}

view raw MyHashTable.cs hosted with ❤ by GitHub

That's all for now, thanks for reading!