Map - sivakrsna/Java-Interview GitHub Wiki

Map

  • A Map is an object that maps keys to values.
  • A map cannot contain duplicate keys: Each key can map to at most one value

General-Purpose Map Implementations

  1. HashMap
  2. TreeMap
  3. LinkedHashMap

HashMap

  • It may have one null key and multiple null values.
  • It maintains no order.
  • It contains only unique elements.
  • Hash table based implementation of the Map interface
  • This implementation provides constant-time performance for the basic operations (get and put)
  • Default initial capacity (16) and the default load factor (0.75).
  • When the number of entries in the hash table exceeds the product of the load factor and the current capacity, the hash table is rehashed (that is, internal data structures are rebuilt) so that the hash table has approximately twice the number of buckets.

The capacity is the number of buckets in the hash table, and the initial capacity is simply the capacity at the time the hash table is created.

The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased.

TreeMap

  • A Red-Black tree based NavigableMap implementation.
  • Maintains ascending order.
  • It contains only unique elements.
  • It cannot have null key but can have multiple null values.
  • The map is sorted according to the natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used.
  • This implementation provides guaranteed log(n) time cost for the containsKey, get, put and remove operations.

LinkedHashMap

  • Maintains insertion order.
  • Duplicate values are not allowed, Contains unique elements only
  • Hash table and linked list implementation of the Map interface

HashMap vs. TreeMap vs. HashTable vs. LinkedHashMap

  • HashMap is implemented as a hash table, and there is no ordering on keys or values.
  • TreeMap is implemented based on red-black tree structure, and it is ordered by the key.
  • LinkedHashMap preserves the insertion order
  • Hashtable is synchronized, in contrast to HashMap.

Special-Purpose Map Implementations

  1. EnumMap
  2. WeakHashMap
  3. IdentityHashMap

EnumMap

  • EnumMap, which is internally implemented as an array, is a high-performance Map implementation for use with enum keys.
  • This implementation combines the richness and safety of the Map interface with a speed approaching that of an array.
  • If you want to map an enum to a value, you should always use an EnumMap in preference to an array.

WeakHashMap

  • WeakHashMap is an implementation of the Map interface that stores only weak references to its keys.
  • Storing only weak references allows a key-value pair to be garbage-collected when its key is no longer referenced outside of the WeakHashMap.
  • This class provides the easiest way to harness the power of weak references.
  • It is useful for implementing "registry-like" data structures, where the utility of an entry vanishes when its key is no longer reachable by any thread.

IdentityHashMap

  • IdentityHashMap is an identity-based Map implementation based on a hash table.
  • This class is useful for topology-preserving object graph transformations, such as serialization or deep-copying. To perform such transformations, you need to maintain an identity-based "node table" that keeps track of which objects have already been seen.
  • Identity-based maps are also used to maintain object-to-meta-information mappings in dynamic debuggers and similar systems.
  • Finally, identity-based maps are useful in thwarting "spoof attacks" that are a result of intentionally perverse equals methods because IdentityHashMap never invokes the equals method on its keys.
  • An added benefit of this implementation is that it is fast.

Concurrent Map Implementations

ConcurrentHashMap

  • ConcurrentHashMap is a highly concurrent, high-performance implementation backed up by a hash table.
  • This implementation never blocks when performing retrievals and allows the client to select the concurrency level for updates.
  • It is intended as a drop-in replacement for Hashtable: in addition to implementing ConcurrentMap, it supports all the legacy methods peculiar to Hashtable.
  • Again, if you don't need the legacy operations, be careful to manipulate it with the ConcurrentMap interface.

ConcurrentHashMap vs HashTable

ConcurrentHashMap uses multiple buckets to store data. This avoids read locks and greatly improves performance over a HashTable. Both are thread safe, but there are obvious performance wins with ConcurrentHashMap.

When you read from a ConcurrentHashMap using get(), there are no locks, contrary to the HashTable for which all operations are simply synchronized. HashTable was released in old versions of Java whereas ConcurrentHashMap is a java 5+ thing.

Hashtable locks the object, while ConcurrentHashMap locks only the bucket