Use Maps when you want to retrieve a value by a key
Maps can use linked objects or arrays as their underlying data structure. Sometimes a combination of arrays and linked objects is used. Internally a method can allocate a key to a certain index of an array. However if that index is already occupied it is possible to build a linked chain moving off that index. Spring Cleaning can remove the linked chains and make the array bigger.
Has methods like:
V get(Object key);
V put(K key, V value);
V remove(Object key);
Set<K> keySet();
Collection<V> values();
Set<Map.Entry<K, V>> entrySet();
Use HashMap when:
you are in a single threaded unsynchronized environment (If not either use Collections.synchronizedMap( Map map ) or better still use ConcurrentHashMap)
you wish to be able to retrieve values efficiently by providing a key
you wish to be able to store nulls (Hashtable does not store nulls)
you do not care about the order that you add elements to the map. Order is not reflected in the iterator or keySet() or entrySet() methods (LinkedHashMap does maintain order)
the keys you are storing have equals() and hashcode() implemented properly
Performance:
O(1) get / put operations (Constant Time) (Faster than LinkedHashMap)
iteration over values requires time proportional to the capacity of the map (Note LinkedHashMap is faster - it requires time propertional to the size of the map)
Characteristics:
You can synchronize the map using: Collections.synchronizedMap( Map map ). However it will be perform worse than ConcurrentHashMap
The iterators returned are fail-fast which means that if the map is structurally modified at any time after the iterator is created, in any way except through the iterator's own remove method, the iterator will throw a ConcurrentModificationException
Use LinkedHashMap when:
you are in a single threaded unsynchronized environment (If not either use Collections.synchronizedMap( Map map ) or better still use ConcurrentHashMap)
You wish to remember the order of the elements you placed in the map. Both the iterator, keySet() and entrySet() order the elements by the order they were placed in the map. (If you dont care about insertion order use HashMap instead as it is a little bit more faster)
Performance:
O(1) get / put operations (Constant Time) (Slower than HashMap as expense of maintaining double linked list)
Iteration over values requires time proportional to the size of the map (Note that HashMap is worse it requires time proportional to the capacity of the map)
Characteristics:
You can synchronize the map using: Collections.synchronizedMap( Map map ). However it will be perform worse than ConcurrentHashMap
The iterators returned are fail-fast which means that if the map is structurally modified at any time after the iterator is created, in any way except through the iterator's own remove method, the iterator will throw a ConcurrentModificationException
Use TreeMap when:
You are in a single threaded unsynchronized environment (If you require synchronized environment use Collections.synchronizedMap( Map map ) or better still use ConcurrentSkipListMap)
You wish the order of the elements returned in keySet or iterator to be based on the natural order of the keys (requires object to implement Comparable) or you are passing a Comparator into the constructor which determines the ordering)
Performance:
O(log n) put/get operations (Logarithmic time)
Characteristics:
You can synchronize the map using: Collections.synchronizedMap( Map map ). However it will be perform worse than ConcurrentHashMap
The iterators returned are fail-fast which means that if the map is structurally modified at any time after the iterator is created, in any way except through the iterator's own remove method, the iterator will throw a ConcurrentModificationException
Use ConcurrentHashMap when:
You are in a multi threaded environment (if not use HashMap or LinkedHashMap)
You do not require the values to be sorted by insertion order (If you do care about insertion order use LinkedHashMap)
you do not require the values to be sorted by the natural order of keys or by the order defined by a comparator passed into the constructor (If you do care use ConcurrentSkipListMap)
Performance:
get / put O(1)
size() O(n)
Characteristics:
Iterators and Enumerations return reflect the state of the map at the time the iterator / enumeration was created They do not throw ConcurrentModificationException. However, one one thread can use an iterators at a time.
Does not allow nulls
Constructor has concurrencyLevel which partitions different areas of the map so that they can work independently of each other without blocking each other. concurrencyLevel specifies how many concurrent threads the map can support efficiently.
Constructor has initialCapacity which specifies the size of the map.
loadFactor specifies the percentage of initialCapacity after which an automatic resizing operation will need to kick in to increase the capacity (e.g 0.75)
Uses CAS non blocking operations to maximise performance when puts, removes are not occuring in the same partition as a get.
For detailed details of this ConcurrentHashMap see:
Use EnumMap when:
you are in a single threaded environment (If you require synchronized environment use Collections.synchronizedMap( Map map )
you need faster performance than HashMap and are using an Enum as a key
Performance:
O(1) get / put operations (Constant Time) (Likely but not guaranteed to be faster than HashMap)
Characteristics:
Iterators returned by the collection views are weakly consistent : they will not throw ConcurrentModificationException and they may or may not show the effects of any modifications to the map that occur while the iteration is in progress.
Use ConcurrentSkipListMap when:
you are in a multi threaded environment (If in single threaded environment use TreeMap)
you require keys to be sorted by their natural ordering or by a comparator passed in via the constructor
Performance:
O (log n) put/get operations (Logarithmic time) (Slower than ConcurrentHashMap)
Characteristics:
Iterators and Enumerations return reflect the state of the map at the time the iterator / enumeration was created They do not throw ConcurrentModificationException. However, only one thread can use an iterators at a time.
bulk operations are not atomic
Use IdentityHashMap when:
you are in a single threaded environment (If you require synchronized environment use Collections.synchronizedMap( Map map )
a key is only the same when it is referentially the same (a == b). It does not use the equals() method unlike other map implementations
Performance:
O(1) get / put operations (Constant Time)
Characteristics:
You can synchronize the map using: Collections.synchronizedMap( Map map ). However it will be perform worse than ConcurrentHashMap
The iterators returned are fail-fast which means that if the map is structurally modified at any time after the iterator is created, in any way except through the iterator's own remove method, the iterator will throw a ConcurrentModificationException
Use WeakHashMap when:
You need to add keys that when not referenced by any other objects, drop out of the WeakHashMap along with the corresponding value, allowing the key to be garbage collected.
Performance:
O(1) get / put operations (Constant Time) (Faster than LinkedHashMap)
teration over values requires time proportional to the capacity of the map (Note LinkedHashMap is faster - it requires time propertional to the size of the map)
Characteristics:
Internally the WeakHashMap wraps the key provided in a WeakReference. WeakReference has a constructor which takes in the key provided and a ReferenceQueue. The WeakReference has a get() method which returns the provided key.
The get() method of the internal WeakReference wrapping the key returns null when the key has no other objects referencing it and has been garbage collected. The empty WeakReference is automatically added to the ReferenceQueue.
Back: Data Structures
Page Author: JD