Implementing hash function and using it into Own implemented HashMap

First what is a hash function?

A hash function is a function which maps keys to indices of an array.
So if k is the key and we have an array of size 10, then h(k) will be some integer value ranging between 0 to 9. So this means the hash function h maps the universe u of keys into the slots of array T[ 0 . . . n-1 ]

Below is the array of size 10.

Now in the above solution there is some issue, what will happen when two keys have the same hash value. i.e.  In other words collision.

To avoid the above situation the easy technique is to do the chaining. Now our data structure will look like as below:

So now the array indices will be maintaining a linked list. Now if we have some key whose h(key) is coming as 1, then we first iterate over the linked list maintained at 1 indices and then add this data at last in the linked list.

Above Data structure is called HashTable.

Now let’s Start implementing a simple hash function i.e. h(k) which will return us the indices into some range.

Public int hash(K key){
     return k mod m; // here k is the key and m is the size of our array or buckets.
}

Now let’s start implementing own hash map.

Now what will be our array of buckets?

Let’s take class Entry which will act as bucket. So array of bucket will be Entry[].
But every bucket is holding the reference of linked list. So our class Entry will be
like:

class Entry<K, T> {
		K key;
		T data;
		Entry next;
}

Here K is the key and T is the data i.e. key value pair.

Now every indices of bucket will maintain a head pointer which will point to the next node in the linked list.

Now let’s say we will be adding our first node, so we first check what will be the hash and then try to get bucket[hash] i.e. the head pointer. If it comes as null then this means that at this indices this is our first time that we are adding a node. If we get the head pointer then this means we have already added some node then we first need to traverse the linked list to last, so that we can add our node.

So our method will look like:

public void add(K key, T data){
		// hash will lie between 0 to 4
		int hash = hash(key);
		if(bucket[hash] == null){
			Entry head = new Entry(null, null, null);
			Entry newEntryNode = new Entry(key, data, null);
			head.next = newEntryNode;
			bucket[hash] = head;
		}else{
			Entry temp = bucket[hash];
			while(temp.next != null)
				temp = temp.next;
			Entry newEntryNode = new Entry(key, data, null);
			temp.next = newEntryNode;
		}
	}

In the same manner we can write the code for getting value of a node for a given key.

public T get(K key){
		int hash = hash(key);
		if(bucket[hash] == null){
			return null;
		}else{
			Entry temp = bucket[hash];
			while(temp.next != null){
				temp = temp.next;
				if(temp.key.equals(key))
					return (T) temp.data;
			}
			return null;
		}
	}

Below is the complete code of HashMap.

package com.algo.hash.hashmap;

public class HashDataType<K extends Integer, T extends Integer> {

	private Entry[] bucket;
	private int INITIAL_CAPACITY = 5;

	public HashDataType(){
		init();
	}

	private void init(){
		bucket = new Entry[INITIAL_CAPACITY];
	}

	public void add(K key, T data){
		// hash will lie between 0 to 4
		int hash = hash(key);
		if(bucket[hash] == null){
			Entry head = new Entry(null, null, null);
			Entry newEntryNode = new Entry(key, data, null);
			head.next = newEntryNode;
			bucket[hash] = head;
		}else{
			Entry temp = bucket[hash];
			while(temp.next != null)
				temp = temp.next;
			Entry newEntryNode = new Entry(key, data, null);
			temp.next = newEntryNode;
		}
	}

	public T get(K key){
		int hash = hash(key);
		if(bucket[hash] == null){
			return null;
		}else{
			Entry temp = bucket[hash];
			while(temp.next != null){
				temp = temp.next;
				if(temp.key.equals(key))
					return (T) temp.data;
			}
			return null;
		}
	}

	private int hash(K key){
		return key % 5;
	}

	static class Entry<K, T> {
		K key;
		T data;
		Entry next;

		public Entry(K key, T data, Entry next){
			this.key = key;
			this.data = data;
			this.next = next;
		}
	}

}

Now it’s time to test the same:

package com.algo.hash.hashmap;

public class RunHashDataType {

	public static void main(String[] args) {
		HashDataType<Integer, Integer> dataType = new HashDataType<Integer, Integer>();
		dataType.add(1, 12);
		dataType.add(2, 13);

		System.out.println(dataType.get(1));
		System.out.println(dataType.get(2));
	}
}

Below is the Output:

12
13

Note: Here we are not checking that two keys are same or not, This is just the basic implementation. We can further add things to make it a good implementation.

Leave a Reply