HashMap Revisited(Understanding HashMap)

Description:

Map is a Interface in Collection Framework where HashMap is one of the implementation of Map. Map is a datastrcuture in which we store data in (Key,Value) pair.Map maintains a mapping of Key to Value. There are few basic  functionality which every DataStructure should provide are

1)Insert

2)Delete

3)Search

It is always expected that all the above operation are done in O(1) complexity which is currently not possible using any existing DataStructure. HashMap is very close to achieving it.Searching in HashMap take O(1) unless we do not have collision(2 keys getting mapped to same index in hashtable).If all the keys maps to the same index then Searching in HashMap take as worst as O(n).so the challenge here is to come with a good hash function.

Direct  Address Table:

one ways of storing (Key,Value) pair is to store the pair into table at index same as Key e.g  key  6 gets the 6th index position in table to store its value.If the distribution among the keys is more we will land up wasting lot of valuable memory in terms of table slots.Suppose we have keys like 1,5,3,2,8,9,50.Here because of  key 50 we need to have a table of size 50 or else it would be possible with table of size 10.Let try to avoid this wastage by making use of hashcode() function in Object class to implement HashMap. hashcode() return a unique code associated with every object created depending on the memory location the object is stored.

Lets see Direct Address Table approach to store (Key,Value) pair.

Direct Address Table(figure 1)

In figure 1 we have some set of keys associated with some Value with each Key.In Direct Address Table as we can see key 2 is store at index position 2 in table,similarly key 5 is stored at index 5 in table and so on.If you observer it carefully you will come to know the drawback with this method and that is if the distribution among key is too large we will end up with loosing lot of table index position.

To overcome above problem we need to treat each key before it is stored into any index position table.This exactly is what done in HashMap implementation.

HashTable

In Hashmap we maintain a table called HashTable .Each Key is processed to find a position in the table to store the key and the associated value with it.The processing of Key is called applying Hash function to the key which yields a index into the HashTable.

f(key) -> index(index into HashTable)

f is function which is called as Hash Function and returns a index into the HashTable where the Value with the Key can be stored.

Trivial hash function could be like

int indexintoTable = key.hashcode() % sizeofTable;.

Now its possible that Hash Function return same index position for two different Keys which we call as Collision.So now we have to find a way to either avoid collision or resolve the collision.

Suppose the HashTable size is 10 and there are two or more keys whose hashcode returns value as 51,21,11 which all will return index as 1 into HashTable which is Collision two or more Keys getting same index position into map.

HashMap(Figure 2)

There are Different ways to resolve the collision as its not possible to avoid collision because it depends on the key and the Hash Function.Here we try to resolve collision by a method called Chaining where a Linklist is associated with each index of the table.Two or more keys getting mapped can be linked using Linklist.New (Key,Value) pair is added at the head of the LinkList. Duplicates keys are not allowed into hashmap.If you try to store duplicates keys it will replace the old value associted with the key with the new value.

HashMap Implementation:

Class representing the HashTable

/**
 * 
 * @author Ashish S Poste
 *
 * @param  Key
 * @param  Value
 */
public class Map {

  private K key;
  private V Value;
  private Map next;
  
  public Map(K key,V value,Map next){
   this.key = key;
   this.Value = value;
   this.next = next;
  }
  public K getKey() {
   return key;
  }

  public void setKey(K key) {
   this.key = key;
  }
  public V getValue() {
   return Value;
  }
  public void setValue(V value) {
   Value = value;
  }
  public Map getNext() {
   return next;
  }
  public void setNext(Map next) {
   this.next = next;
  }
  
}

HashMap Implementation Class

/**
 * 
 * @author Ashish S Poste
 *
 * @param  Key
 * @param  Value
 */
public class HashMapCustom {

 private Map[] table = null;
 private int size;
 public HashMapCustom(){
  table =new Map[16];
  size = 16;
 }
 public HashMapCustom(int size){
  table = new Map[size];
  this.size = size;
 }
 
 public V put(K key,V value){
  int hashCode = key.hashCode();
  int indexinTable = hashCode % size;
  Map map = table[indexinTable];
  if(null == map){
   Map tempMap = new Map(key, value, null);
   table[indexinTable] = tempMap;
  }else{
   Map duplicateMap = checkforDuplicateKey(map,key);
   if(duplicateMap != null)
   {
    V val = (V)duplicateMap.getValue();
    duplicateMap.setValue(value);
    return val;
   }else{
    Map tempMap = new Map(key, value, null);
    tempMap.setNext(table[indexinTable]);
    table[indexinTable] = tempMap;
    return null;
   }
  }
  return null;
 }
 private Map checkforDuplicateKey(Map map, K key) {
  Map temp = map;
  while(temp != null){
   if(temp.getKey().equals(key)){
    return temp;
   }else{
    temp = temp.getNext();
   }
  }
  return null;
 }
 public V get(K key){
  int hashCode = key.hashCode();
  int indexinTable = hashCode % size;
  Map tempMap = table[indexinTable];
  if(tempMap == null){
   return null;
  }else{
   while(tempMap != null){
    if(tempMap.getKey() == key){
     return (V) tempMap.getValue();
    }else{
     tempMap = tempMap.getNext();
    }
   }
  }
  return null;
 }
 public Boolean containsKey(K key){
  for(Map tempMap : table){
   while(tempMap != null){
    if(tempMap.getKey().equals(key)){
     return true;
    }else{
     tempMap = tempMap.getNext();
    }
   }
  }
  return false;
 }

}

Note:I will be adding more function to the HashMapCustom in coming Days.Your Suggestion and feedbacks are most welcome.Feel free to comment.

Cheers!!!!!!!!!!!!!!!
Ashish S Poste