Software Engineer

I am a Software Engineer. I have a Bachelor (Honours) of Science in Information Technology from the University of Sunderland - Class of 2003. I have been developing software since 2001 when I was offered a role at CERN as part of their Technical Student Programme.

By 2016 I had grown really tired of the software industry and by the end of 2019 Apple killed whatever excitement I had left. I am not sure what the next 10 years will bring. What I do know is that my apettite to do work that is impactful has only grown bigger and stronger. Great people make me tick more than anything.

I am also tired.

How to think of... a hash table (Part 1)

     * 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]

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


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.