Implementing Hash Map using chaining

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 ]

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/HashMap.

Source Code to implement a HashMap

package test.sachi.dsnalgos.hashmap;

public class HashMap<K extends Integer,V extends String> {

private Entry<K,V>[] bucket;

private int INITIAL_CAPACITY=10;

public HashMap()

{

init();

}

private void init() 

{

bucket=new Entry[INITIAL_CAPACITY];

}

private int hash(K key){

        return key % 10; 

    }

public void add(K key, V value){

int hash=hash(key);

if(bucket[hash]==null){

Entry<K,V> head=new Entry<K,V>(null,null,null);

Entry<K,V> newEntryNode=new Entry<K,V>(key,value,null);

head.next=newEntryNode;

bucket[hash]=head;

}else{

Entry<K,V> temp=bucket[hash];

while(temp.next !=null){

temp=temp.next;

}

Entry<K,V> newEntryNode=new Entry<K,V>(key,value,null);

temp.next=newEntryNode;

}

}

public V get(K key){

int hash=hash(key);

if(bucket[hash]==null){

return null;

}else{

Entry<K,V> temp=bucket[hash];

while(temp!=null){

temp=temp.next;

if(temp.key.equals(key)){

return (V) temp.value;

}

}

}

return null;

}

static class Entry<K,V>

{

K key;

V value;

Entry<K,V> next;

public Entry(K key,V value,Entry<K,V> next){

this.key=key;

this.value=value;

this.next=next;

}

}

}