Daily Archives: January 31, 2016

Working and Difference of HashMap ,HashTable,SynchronizedMap, ConcurrentHashMap,TreeMap,SynchronizedSortedMap and ConcurrentSkipListMap

All the above five class implementation are of Map interface.Map object store an key,value pair in the memory.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;

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;

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 tothread 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;

}

 

Synchronization and Concurrency: 

Concurrency means number of executing units(like thread)are doing their work on the shared code portion(Class,Method)simultaneously without outputting wrong result. And Synchronization is the way to achieve Concurrency. Proper usage of synchronisation make sure data integrity and sanity in a multithreaded environment (which is concurrent environment). Use of ‘synchronised’ keyword and use of locks are some of the synchronization technique used in Java.

Now Collections.synchronizedMap: 

Collections.synchronizedMap(Map<K,V> m)is wrapper class for HashMap and is almost same as that of HashTable. It has‘synchronized’ keyword internally 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 for single thread environment .If in case we need to use it in multi- threaded environment, we should 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 data structure 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 rescue which was accommodated in JDK1.5 and is part of concurrent package(java.util.concurrent). ConcurrentHashMap use segmentationInternally, by using segmentation it lock only some portion of the map object and rest of the portion can be processed by different thread on different segments of the Map (We can see source code for ConcurrentHashMap on how segmentation works internally).

So below is the whole summary:

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.

Collections. synchronizedMap (Map <K,V> m):Use it in Multithreaded environment whenthere 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 multiple writer thread on different segment of map and so is highly scalable on highly concurrent environment. Here null is not allowed as an key or value

TreeMap :TreeMap 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 interface(which in turn extend Map interface).

TreeMap Example:-


package com.devil;

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 ways 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 ofName).More detail about Comparator and Comparable interface are in this posthttps://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).Generally HashMap are faster(unless we design a bad hash function).so if we do not require sorting, We should useHashMap.   So with all this, we have now got basic idea about the Map family, their usage in different situation.