A hash table (or hash map) is a data structure that represents a collection of key-value pairs. This allows client code to refer to elements stored in the hash table by name instead of just by integer index. More generally, this description applies to what’s called an associative array (named because keys are associated with values). A hash table in particular is a means by which an associative array can be made very efficient, using some clever tricks.
A hash table’s structure looks something like this:
On the left, we see an array of pointers to lists (more generally ‘buckets,’ because we could use another data structure here). When we add a new item to the hash table, we put its key through a hash function. The hash function returns the integer index of the bucket into which we place the item. When we want to look up the value associated with a key, or determine whether that key exists, we take the hash again, then search the bucket and see if we can’t find the item with the appropriate key.
All that hashing and bucketing sounds complicated, but it saves quite a bit of time. Looking up an item in a naive associative array would mean starting at the beginning and going through every key until we found the one we were after. With a hash table, we only have to search as many items as are in our key’s bucket.
Now, this should make the hash table faster, but if we choose our hash function poorly, we can still end up with something very slow. For instance, if our hash function disregards the input and returns 7, we’ll have a working hash table in which all the keys are stored in bucket 7, and we’re back to the performance of the naive associative array. A good hash function should distribute items evenly across the buckets, but a pathological choice of keys can still result in slow behavior.
We also have to make sure that the hash function chooses only those integers we have available as indices. An easy way to do that is by reducing the result of an arbitrary hash function modulo n, where n is number of buckets. If our number of buckets is a power of 2, we can also just use the least significant bits of the result of the hash to achieve the same result more quickly.
Ideally, we never have two items stored in the same bucket. When an item is added to an occupied bucket, we call this a ‘hash collision.’ If our hash table stores a fixed set of items, we can find a hash function which gives us no collisions, for a very fast lookup. If we have to store unknown, arbitrary values, we try to choose a function which results in relatively few collisions.
As the number of items stored in the table grows, the odds of a hash collision increase surprisingly fast (see the birthday paradox). We can mitigate this by expanding the array of available indices as the hash table fills. Expanding the array is an expensive operation, because we have to re-hash the contents of the table – we may either re-hash everything at once, or maintain the table as it was while simultaneously allocating another, larger hash table and determining when and how to move the old entries to the new. My example will not expand the hash table.
Here’s the code:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 |
using System.Collections.Generic; using System; namespace KaiserDataStructures { public class KHashTable<K, V> { private KLinkedList<KeyVal>[] listArray; public KHashTable(int size) { this.listArray = new KLinkedList<KeyVal>[size]; for (int i = 0; i < size; i++) { this.listArray[i] = new KLinkedList<KeyVal>(); } } private int Hash(K key) { return (Math.Abs(key.GetHashCode() % this.listArray.Length)); } public void Add(K key, V value) { KeyVal item = new KeyVal(key, value); int index = this.Hash(key); this.listArray[index].Insert(item); } public KeyVal Find(K key) { int index = this.Hash(key); KLinkedList<KeyVal> list = this.listArray[index]; KLinkedList<KeyVal>.KNode item = list.First; while (item != null) { //System.Collections.Generic.EqualityComparer<T> //allows us to perform comparisons on generics without operater overloading. //I tried to use ==, but the compiler can't tell that //K and K are the same type, so it throws an error if(EqualityComparer<K>.Default.Equals(key, item.Data.Key)) { return item.Data; } item = item.Next; } return null; } public KeyVal Remove(K key) { int index = this.Hash(key); KLinkedList<KeyVal> list = this.listArray[index]; KLinkedList<KeyVal>.KNode item = list.First; while (item != null) { if (EqualityComparer<K>.Default.Equals(key, item.Data.Key)) { return list.Delete(item).Data; } item = item.Next; } return null; } public override string ToString() { string s = ""; foreach (KLinkedList<KeyVal> list in this.listArray) { s += "{"; foreach (KeyVal item in list) { s += "(" + item + "), "; } s += "}\r\n"; } return s; } public class KeyVal { private K key; private V value; public KeyVal(K key, V value) { this.key = key; this.value = value; } public K Key { get { return this.key; } set { this.key = value; } } public V Value { get { return this.value; } set { this.value = value; } } public override string ToString() { return (key + ", " + value); } } } } |
I also added a method to delete elements from the linked list by value, and return the deleted item. The existing Delete() method got a return value, too, just for parity:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
public KNode Delete() { KNode temp = First; First = First.Next; return temp; } public KNode Delete(KNode toDelete) { if (this.First == toDelete) { KNode temp = this.First; this.First = null; return temp; } KNode node = this.First; KNode next = this.First.Next; while (node != null) { if (next == toDelete) { node.Next = next.Next; return next; } node = node.Next; if (next != null) { next = next.Next; } } return null; } |
And the client code to test it:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
static void testHashTable() { KHashTable<string, string> myTable = new KHashTable<string, string>(5); Console.WriteLine("Created a <string, string> hash table with 5 buckets."); myTable.Add("George Washington", "Politician"); myTable.Add("Bruce Campbell", "Actor"); myTable.Add("Stephen King", "Writer"); myTable.Add("Kaiser Leib", "Programmer"); myTable.Add("Fido", "Dog"); Console.WriteLine("Added 5 <string, string> pairs"); Console.WriteLine("The hash table now contains:"); Console.WriteLine(myTable); KHashTable<string, string>.KeyVal fido = myTable.Find("Fido"); if (fido != null) { Console.WriteLine("The table has an entry whose key is \"Fido\", with the value " + fido.Value); } else { Console.WriteLine("Fido is not in the table, something is wrong."); } KHashTable<string, string>.KeyVal removeGeorge = myTable.Remove("George Washington"); if (removeGeorge != null) { Console.WriteLine("Successfully removed the key \"George Washington\", the value of which was " + removeGeorge.Value); } else { Console.WriteLine("Could not remove George Washington, something is wrong."); } KHashTable<string, string>.KeyVal walter = myTable.Find("Walter White"); if (walter != null) { Console.WriteLine("The table contains an entry whose key is \"Walter White\". Something is wrong."); } else { Console.WriteLine("The table contains no entry for \"Walter White\"."); } KHashTable<string, string>.KeyVal kaiser = myTable.Remove("Kaiser Leib"); if (kaiser != null) { Console.WriteLine("Successfully removed the key \"Kaiser Leib\", the value of which was " + kaiser.Value); } else { Console.WriteLine("Could not remove \"Kaiser Leib\""); } Console.WriteLine("The hash table now contains:"); Console.WriteLine(myTable); int wait = Console.Read(); } |
Which gives the expected output:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
Created a <string, string> hash table with 5 buckets. Added 5 <string, string> pairs The hash table now contains: {(Bruce Campbell, Actor), } {(George Washington, Politician), } {} {(Fido, Dog), (Kaiser Leib, Programmer), (Stephen King, Writer), } {} The table has an entry whose key is "Fido", with the value Dog Successfully removed the key "George Washington", the value of which was Politic ian The table contains no entry for "Walter White". Successfully removed the key "Kaiser Leib", the value of which was Programmer The hash table now contains: {(Bruce Campbell, Actor), } {} {} {(Fido, Dog), (Stephen King, Writer), } {} |