Java Learning: The Internals of Map,SortedMap interface

The Internals of Map,SortedMap interface

Posted by Parvinder on July 15, 2012

HashMap,Hashtable, SynchronizedMap,ConcurrentHashMap,TreeMap,SynchronizedSortedMap,ConcurrentSkipListMap

All the above five class implementation is of Map interface.Map object store an key,value pair in the memory(How its store internally in memory ,that is separate discussion,will discuss that later).Both key and value should be object not some primitive type like int,float. Lets start with HashMap and Hashtable.Hashtable is synchronized but HashMap is not synchronized other difference is that in HashMap we can put null as an key or as an value but in Hashtable we can not put null as an key or as an value.

The Below Code example show that in HashMap we can put null as an key or as an value but in Hashtable we can not put null as an key or as an value. Although there is no problem at compile time but it(Hashtable) will throw exception at run time.

package com.devil.space;

import java.util.HashMap;

import java.util.Hashtable;

import java.util.Map;

public class MapExample1 {

    public static void main(String args[]) {

        Map<String, String>hashMap = new HashMap<String, String>();

        hashMap.put(null, null);

        for (String str : hashMap.keySet()) {

            String value = hashMap.get(str);

            System.out.println("HashMap Value:-" + value);

        }

        Map<String, String>hashTable = new Hashtable<String, String>();

        hashTable.put(null, null);

        for (String str : hashTable.keySet()) {

            String value = hashTable.get(str);

            System.out.println("HashTable Value:-" + value);

        }

    }

}

Output will be—

HashMap Value:-null

Exception in thread “main” java.lang.NullPointerException

at java.util.Hashtable.put(Unknown Source)

at MapExample1.main(MapExample1.java:17)

If we are inserting multiple keys as an null in HashMap.Than latest insertion will be considered as an entry in to the HashMap

package com.devil.space;

import java.util.HashMap;

import java.util.Hashtable;

import java.util.Map;

public class MapExample2 {

    public static void main(String args[]) {

        Map<String, String> hashMap = new HashMap<String, String>();

        hashMap.put(null, null);

                hashMap.put(null,"HashValue");

        for (String str : hashMap.keySet()) {

            String value = hashMap.get(str);

            System.out.println("HashMap Value:-" + value);

        }

        Map<String, String>hashTable = new Hashtable<String, String>();

        hashTable.put(null, null);

        for (String str : hashTable.keySet()) {

            String value = hashTable.get(str);

            System.out.println("HashTable Value:-" + value);

        }

    }

}

Output will be—

HashMap Value:-HashValue

Exception in thread “main” java.lang.NullPointerException

at java.util.Hashtable.put(Unknown Source)

at MapExample2.main(MapExample2.java:17)

Hashtable is synchronized i.e methods for getting and putting element are made to 
thread safe by putting ‘synchronized’ keyword before the methods.
 
In HashMap get() and put() are: 

public Value get(Object key) { 
 Value v; 
---implementataion--- 
return v; 
} 
public Value put(Key key, Value value){ 
Value v;
---implementataion---  return v; 
}   
And in Hashtable get() and put() are:   
public synchronized  Value get(Object key){
Value v;
---implementataion---  
return v; 
}   
Public synchronized Value put(Key key, Value value) {
Value v;
---implementataion---  
return v; 
}
Now Lets discuss first  What is the  difference between Synchronization and Concur-
-rency.
Synchronization and Concurrency:Concurrency means number of executing units(like 
thread)are doing their work on the shared code portion(Class,Method)simultaneous-
-ly without outputting wrong result. And Synchronization is the way to achieve 
Concurrency.Use of 'synchronised' keyword and use of locks are some of the
synchronization technique used in Java

Now come Collections.synchronizedMap
(Map<K,V> m) which is wrapper class for HashMap and is same as that of Hashtable
internally having ‘synchronized’ keyword on every method.
Functionally Hashtable and  SynchronizedMap are same.Both are slow,thread safe and
had lot of performance overhead due to synchronization mechanism.Now in between 
HashMap and Hashtable,HashMap should be used always.If in case we need to use 
it in multi- threaded environment, we can use Collections. synchronizedMap(Map
<k,v>m)which gives synchronized  HashMap.Also Hashtable is from JDK1.0 and rest
 of the collection framework(Map,set,list)is from JDK 1.2 and Hashtable is kind 
of obsolete now.Its retained in further JDK version just to support legacy code.

 
Now in multithreaded environment when size of HashMap becomes large,using of 
Collections. synchronizedMap (Map <K,V> m) or Hashtable make our code very slow 
since in both the cases lock is acquired on whole object.So now in this situation 
ConcurrentHashMap comes in resue which was accommodated in JDK1.5 and is part
of concurrent package(java.util.concurrent). ConcurrentHashMap use segmentation
internally, by using segmentation it lock only some portion of the map object 
so that threads waiting for read operation may continue read access(We can see
source code for ConcurrentHashMap on how segmentation works internally).
 
So Things are much clear:
 
HashMap:Use it in single threaded environment. When only one thread is accessing 
our Map object.Here null is allowed as an key or value.
 
HashTable:Never use it in new code. Sometimes it becomes necessary to use it to 
support legacy code, But never use it in new independent code.Here null is not 
allowed as an key or value.

Collection. synchronizedMap (Map <K,V> m):Use it in Multithreaded environment when
there are limited number of threads and want to access code through single lock.
Here null is allowed as an key or value

 
ConcurrentHashMap:Use it in highly concurrent environment when number of concurrent 
access is very high.It permits any number of concurrent reader threads and so is 
highly scalable on highly concurrent environment.Here null is not allowed as an key
or value

Now TreeMap comes in picture.This data structure has different objective in the Map
family.It keeps the data in sorted order with respect to its keys.Means sorting
criteria is driven by their key.It implement SortedMap interfcae(which in turn
extend Map interface)
TreeMap Example:--

package com.devil.space;

import java.util.TreeMap;

public class TreeMapExample1 {

    public static void main(String args[]) {

        TreeMap<String, String> treeMap = new TreeMap<String, String>();

        treeMap.put("Delhi","India");

        treeMap.put("Washington","USA");

        treeMap.put("Beizing","China");

        treeMap.put("Tokyo","Japan");

        treeMap.put("Paris","France");

        for (String str : treeMap.keySet()) {

            String value = treeMap.get(str);

            System.out.println("TreeMap Value:-" + value);

        }

    }

}

Output of the above code is:

TreeMap Value:-China
TreeMap Value:-India
TreeMap Value:-France
TreeMap Value:-Japan
TreeMap Value:-USA

  There are two way to define the sorting order.
 1.Java object which are used as an key in TreeMap should implement Comparable 
 interface and sorting logic should be put in compareTo() method. Generally we
 use String or Integer object(in the above example,String is used as an Key) as
 an key.These object already implement Comparable
 interface.So in that case there is no need to do that.

Example:Map<Person,String>treeMap=new TreeMap<Person,String>();

 Lets Person class is :

public class Person{
public String age;
public String name;
}

Here Person is used as an key so this class should implement Comparable interface.
Otherwise a RunTime Exception will occur when we run the code.

2.Passing an Comparator as an argument to the constructor of Treemap when we create
a new object

Example:

Map<Person,String>treeMap=new TreeMap<Person,String>(AgeComparator)
This will sort the map according to AgeComparator logic(sorting on the basis of
age).

Map<Person,String>treeMap=new TreeMap<Person,String>(NameComparator)

This will sort the map according to AgeComparator logic(sorting on the basis of
Name).More detail about Comparator and Comparable interface are in this post
http://devilspace.org/2012/07/25/sorting-in-javacomparable-and-comparator/

TreeMap is not synchronised and so its not thread safe.We can use 
Sortedmap sortedMap=Collections.SynchronizedSortedMap(new TreeMap())
to achieve thread safety in TreeMap.

Concurrent analog of TreeMap is ConcurrentSkipListMap() which should be used in 
highly concurrent environment.

Performance:
Internally TreeMap use Red-Black Tree(a self balanced binary  search tree)for 
storing data.Its access time(search),insert time is O(log n) as  comparison to
other Map implementation(all the above discussed map which are based on Hashing)
which takes O(1) as look up time+O(k) time for looking in to each bucket(k is 
the number of element in each bucket).Genrally HashMap are faster(unless we 
design a bad hash function).so if we do not require sorting,We should use
Hashmap.

So with all this, we have now got some idea about the Map family.their usage in
different situation.

Java Learning

Thursday, August 20, 2015

The Internals of Map,SortedMap interface

The Internals of Map,SortedMap interface

No comments:

Post a Comment