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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
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:--
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
|
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.
