HashMap Made Easy

HashMap Implementation strategy:

HashMap uses hash function to map keys for ex names to index/buckets/slots in the array.



Noramally every HashMap implementation assumes more than one key produce same hash values, known as hash collisions. The performance of hashmap ie how faster search works and memory not wasted doesn't depends directly on the no of stored entries n. Actually it depend on the load factor = no of stored entries/ size of array. Average look up cast is constant for load factor 0-.7, beyand this result in more hash collision reducing the search performance. Load factor near to zero indicate lot of memory waste without significant improvement in search.



Java collection framework implementation followes seperate chaining/direct chaining/chaining strategy. Each slot in table/array has a link to linked list that has key value pairs that hashed to same location. For ex in above picture john smith and sandra dee hashed values is same as array index 152. Now entry john Smith will be stored at index 152 and have a link of another entry names sandra(a linked list referred by slot 152).

HashMap Implementation

The following code has similar HashMap implementation as it is in collection package of java. This is very simplified and useful for the people who just want to know how its been implementated in collection framework.


public class MyHashMap {

Entity [] table;
int initialCap = 5;

MyHashMap(){
table = new Entity[initialCap];
}

int hash(Integer index){
return index%initialCap ;
}

Object put(Object key, Object value){
Object toRet= null;
int hash = hash(((Integer)key));
Entity e = table[hash];
table[hash((Integer)key)] = new Entity(hash, key, value, e);
if(e!=null)
toRet = e.value;
return toRet;
}

Object get(Object key){
int hash = hash((Integer)key);
for(Entity e= table[hash]; e!=null; e= e.next ){
if(hash == e.hash && key.equals(e.key)){
return e.value;
}

}
return null;
}

class Entity{

public int hash ;
public Object key;
public Object value;
public Entity next;

Entity(int hash, Object key, Object value, Entity next){
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public boolean equals(Object o){
if(!(o instanceof Entity)) return false;
if((Integer)this.key == (Integer)(((Entity)o).key)) return true;
return false;
}
}

public static void main (String [] args){

MyHashMap map = new MyHashMap();
map.put(1, 2);
map.put(2, 3);
map.put(3, 7);
map.put(4, 1);
map.put(5, 4);
map.put(6, 5);
map.put(7, 6);
System.out.println("got my value :-)"+map.get(1));


}
}

Feel free to experiment. I will appreciate your effort to find some logical error in the code.