Contents
Map is a very powerful data structure used to store key-value pair. It is highly efficient for lookups, retrieving, adding and removing items. Ideally, these operations are supposed to take constant time [O(1)]; however, sorted maps used to have logarithmic time operations [O(log(n))].
Storage
Map internally uses array to store elements. To determine the index of the element stored in the array, hash code of the key and length of the array is used. A hash function is applied on the key to generate the hash code. Hash functions uses different algorithms to generate the hash code. Better the hash function, better(less number of non unique hash codes and collisions) will be the hash code and so better efficiency of the map.
Hash code is an integer. Integers has a maximum capacity of 4 billion distinct figures while the key that could be stored in the map has no limit. Therefore, multiple object, even with different look can have same hash code and thus corresponds to same index in the Array. To cope with this situation, each array item points to a Linked List. Each element in the list encapsulates both Key and Value. Having same hash code of the multiple key is called a Collision. To minimise the collision less number of items used to store in the array than its length. Hence, number of place used to store the items in the array is manipulated by ARRAY_SIZE * LOAD_FACTOR. LOAD_FACTOR is the ratio of actual number of items getting stored in the map to the length of the internal array. Its a positive value and could be at most 1. Lowering the load factor decreases the chances of collision but increases the memory requirement. Based on many experiments done till today 0.75 has been chosen as the ideal factor.
Types of Map
Java core provides a lot of map options based on your application requirement. Following map's detailed implementations can be found on java.sun.com. Many other maps have been implemented by different organisations/individuals. Try to find further details of those maps and their jar from www.findjar.com.
Hashtable
Since java 1.0. Synchronized. Items inserted are random. This is the earliest class which implements Map interface. Unlike other maps Hashtable extends Dictionary and does not accept key or value as null. null value shall throw the NullPointerException. As per Java 5, default value of initial capacity and load factor are 11 and 0.75 respectively.
HashMap
Since java 1.2. Not Synchronized. Items inserted are random. Very similar to Hashtable but null is permitted as key or value. HashMap is faster than Hashtable because, it is not synchronized.
TreeMap
Since java 1.2. Not Synchronized. Items inserted are sorted. TreeMap is most used ordered map with Red Black Tree based implementation of SortedMap Interface. Most of the basic operations have strictly logn time complexity. In case when object encapsulating more than one data type, a comparator(also needs implementation of hashCode, equals and compare methods in the comparator) needs to be used at the creation time of TreeMap.
WeakHashMap
Since java 1.2. Not Synchronized. Items inserted are random. Similar to HashMap with Weak referenced Keys.
LinkedHashMap
Since java 1.4. Not Synchronized. Items inserted are ordered. LinkedHashMap is an ordered key HashMap and is better than TreeMap if sorting is not needed but order needs to be maintained. LinkedHashMap is used to create LRU cache with the help of its constructor LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder).
IdentityHashMap
Since java 1.4. Not Synchronized. Items inserted are random. It does not work on equals method. It equals two keys only when reference of both are same.
EnumMap
Since java 1.5. Not Synchronized. Items inserted are ordered. Map with key as ordered as in the Enum.
ConcurrentHashMap
Since java 1.5. Synchronized. Items inserted are random. Its a big brother of Hashtable. CincurrentHashMap uses multiple locks at bucket level. This makes it much faster compared to Hashtable or any other map wide locked Map.
ConcurrentSkipListMap
Since java 1.6. Synchronized. Items inserted are sorted. Synchronized HashMap based on skip list with logn complexity for operations