I wrote a hashmap in C# as a self study exercise. I wanted to implement chaining as a collision handling technique. At first I thought I'd simply use GetHashCode as my hashing algorithm, but I quickly found that use the numbers returned by GetHashCode would not always be viable (size of the int causes a out of mem if you want to index and array by the number and numbers can be negative :(). So, I came up with a kludgey method of narrowing the numbers (see MyGetHashCode).
Does anyone have any pointers/tips/criticism for this implementation (of the hash function and in general)? Thanks in advance!
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Microsoft.VisualStudio.TestTools.UnitTesting;
namespace HashMap
{
class Program
{
public class MyKVP<T, K>
{
public T Key { get; set; }
public K Value { get; set; }
public MyKVP(T key, K value)
{
Key = key;
Value = value;
}
}
public class MyHashMap<T, K> : IEnumerable<MyKVP<T,K>>
where T:IComparable
{
private const int map_size = 5000;
private List<MyKVP<T,K>>[] storage;
public MyHashMap()
{
storage = new List<MyKVP<T,K>>[map_size];
}
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
public IEnumerator<MyKVP<T, K>> GetEnumerator()
{
foreach (List<MyKVP<T, K>> kvpList in storage)
{
if (kvpList != null)
{
foreach (MyKVP<T, K> kvp in kvpList)
{
yield return kvp;
}
}
}
}
private int MyGetHashCode(T key)
{
int i = key.GetHashCode();
if (i<0) i=i*-1;
return i / 10000;
}
public void Add(T key, K data)
{
int value = MyGetHashCode(key);
SizeIfNeeded(value);
//is this spot in the hashmap null?
if (storage[value] == null)
{
//create a new chain
storage[value] = new List<MyKVP<T, K>>();
storage[value].Add(new MyKVP<T, K>(key, data));
}
else
{
//is this spot taken?
MyKVP<T, K> myKvp = Find(value, key);
if (myKvp != null) //key exists, throw
{
throw new Exception("This key exists. no soup for you.");
}
//if we didn't throw, then add us
storage[value].Add(new MyKVP<T, K>(key, data));
}
}
private MyKVP<T, K> Find(int value, T key)
{
foreach (MyKVP<T, K> kvp in storage[value])
{
if (kvp.Key.CompareTo(key) == 0)
{
return kvp;
}
}
return null;
}
private void SizeIfNeeded(int value)
{
if (value >= storage.Length)
{
List<MyKVP<T, K>>[] temp = storage;
storage = new List<MyKVP<T, K>>[value+1];
Array.Copy(temp, storage, temp.Length);
}
}
public K this[T key]
{
get
{
int value = MyGetHashCode(key);
if (value > storage.Length) { throw new IndexOutOfRangeException("Key does not exist."); }
MyKVP<T, K> myKvp = Find(value, key);
if (myKvp == null) throw new Exception("key does not exist");
return myKvp.Value;
}
set
{
Add(key, value);
}
}
public void Remove(T key)
{
int value = MyGetHashCode(key);
if (value > storage.Length) { throw new IndexOutOfRangeException("Key does not exist."); }
if (storage[value] == null) { throw new IndexOutOfRangeException("Key does not exist."); }
//loop through each kvp at this hash location
MyKVP<T, K> myKvp = Find(value, key);
if (myKvp != null)
{
storage[value].Remove(myKvp);
}
}
}
static void Main(string[] args)
{
MyHashMap<string, int> myHashMap = new MyHashMap<string, int>();
myHashMap.Add("joe", 1);
myHashMap.Add("mike", 2);
myHashMap.Add("adam", 3);
myHashMap.Add("dad", 4);
Assert.AreEqual(1, myHashMap["joe"]);
Assert.AreEqual(4, myHashMap["dad"]);
Assert.AreEqual(2, myHashMap["mike"]);
Assert.AreEqual(3, myHashMap["adam"]);
myHashMap.Remove("joe");
try
{
if (myHashMap["joe"] == 3) { }; //should throw
}
catch (Exception)
{
try { myHashMap.Add("mike",1); }
catch (Exception) {
foreach (MyKVP<string, int> kvp in myHashMap)
{
Console.WriteLine(kvp.Key + " " + kvp.Value.ToString());
}
return;
}
}
throw new Exception("fail");
}
}
}