/*
     * For now, think of a hash table as something like that 
     */
    public interface HashTable
    {
        /**
         * Retrieves the value from the hash table given the key
         * 
         * @param key the key used to put the value
         * @return the associated value as specified in {@link #put(int, int)}
         */
        public int get(int key);

        /**
         * Stores the specified value under the given key.
         * Any value stored previously on the same key is overriden.
         * 
         * @param key the key to associate the value with
         * @param value the value
         */
        public void put(int key, int value) 
    }

The hash table seems to be the dominator of data structures as it is being used to solve a variety of CompSci problems such as caching. On a day to day basis we can use it when there is a need to make a choice or to operate on a Set (though hidden). Now, rarely there is a need to implement a hash table from scratch but having a deep understanding of how a hash table works can greatly help us make the most out of it when the time comes.

The basic idea is that you have an array to store values. Given that an array has an index that you can use to store and retrieve a value, it all works.

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

What happens though if you want to use your own key that you can query on? So you have a hashtable of size 3 and you want to put the value of 0 under the key 0.

	HashTable hashtable = new HashTable(3);
	hashtable.put(0, 0);

Now given that the underlying structure is an array, the hashtable needs to figure out which index to use in the array to put the value in. Since the array is of size 3 the possible indexes are 0 to 2.

[0, 1, 2]
|---3---|

A simple way to get a number within that range is to mod the key with the length of the hashtable. So in this case

0 % 3 = 0 // key  % length = index

So the hashtable uses index 0 to store the value.

	public void put(int key, int value) 
	{		
		int index = key % this.size;
		this.values[index] = value;
	}

The next time you ask for the value stored under the key 0

	hashtable.get(0);

the hashtable calculates the index again and gives you the value stored

	public int get(int key) 
	{
		int index = key % this.size;

	return this.values[index];
	}

It all works great until you have a key which gives you the same index.

	hashtable.put(0, 0); // 0 % 3 = 0
	hashtable.put(1, 1);
	hashtable.put(2, 2);
	hashtable.put(3, 3); // 3 % 3 = 0

That’s when you have a collision which you need to deal with.