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

public final class HashTable 
    {
        private BucketList bucketList;

        private HashTable(BucketList buckets) 
        {
            this.bucketList = buckets;
        }

        public int get(int key) 
        {
            int index = this.bucketList.bucketOf(key);

        return this.bucketList.get(index, key);
        }

        public void put(int key, int value) 
        {
            int index = this.bucketList.bucketOf(key);      

            this.bucketList.put(index, key, value);
        }
    }


    /**
     * Buckets for all
     */
    final class BucketList
    {
        private final Value[] buckets;

        private BucketList(Value[] buckets) 
        {
            this.buckets = buckets;
        }   

        int bucketOf(int key) {
        return key % this.buckets.length
        }

        /**
         * Searches the bucket in the specified index for the value of the given key
         * @param index the bucket that holds the value
         * @param key the key of the value
         * @return the value in the bucket that has the specified key or -1
         * @see #bucketOf(int)
         */
        public int get(int index, int key) 
        {
            for (Value value = this.buckets[index]; value != null; value = value.next) 
            {
                if(value.key == key){
                    return value.value;
                }
            }
        
        return -1;
        }
        
        /**
         * Stores the value for the given key to the specified bucket.
         * If an existing value is already present, store it next to the one 
         *  
         * @param index the index of the bucket
         * @param key the key of the value
         * @param value the value
         */
        public void put(int index, int key, int value) 
        {       
            Value current = this.buckets[index];
            
            this.buckets[index] = new Value(key, value, current);
        }
    }

Start at the beginning with Part 1

Let’s take a step back for a minute and take a look at the array.

[0, 1, 2]

Imagine that each value in the array represents a “bucket”. That is a collection of values (rather than a single one). So each time you put a value in that bucket, it grows.

 9 
 6	7  
 3	4  5
 0  1  2
 ^  ^  ^
[0, 1, 2] //bucket index

Rotating the view 90 degrees to the right will reveal that each bucket really is just an array

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

This will allow us to store more than one value under the same index. Notice how 0 and 3 are both under index 0. Calculating the index of the bucket is not enough any more when querying for the value since there is the possibility of getting more than one.

That is why we need a class to hold the value as well as the actual key associated with it.

	/*
	 * In each bucket basically is a linked list
	 */
	class Value
	{
		private final int key;
		private final int value;
		private Value next;		
	}

Having a reference to the next value in the bucket will allow us to grow and iterate the array without the overhead of maintaining it.

So given the index and the key, we find the bucket and then iterate until we match the key to get the value. Remember that each key is really unique.

	public int get(int index, int key) 
	{
		for (Value value = this.buckets[index]; value != null; value = value.next) 
		{
			if(value.key == key){
				return value.value;
			}
		}
	
	return -1;
	}

In that sense in every put as well as creating a new Value with the key and value we need to assign the current one as the next in the list.

	public void put(int index, int key, int value) 
	{		
		Value current = this.buckets[index];
		
		this.buckets[index] = new Value(key, value, current);
	}

That all works great but our hash table is of fixed and very small length. We need to deal with the fact that our buckets will grow longer and longer in time.

Software Engineer

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