Map In Java - Java Collections

Map is a key-value data structure in Java and other languages, it uses an array to save the key-value data, by hashing the key to an integer, then map to array index.

There will be a chance that mulilple different keys have same hash code, this called hash collision. If number of collision keys less than 8, then it uses a linked list to save all the key-value pairs with same hash, if more 8, it will convert the linked list into a red-black tree.

The following diagram shows the hierachy of the Maps in Java.

You can zoom in to have a better view of the diagram.

The following table shows the Maps characters in Java.

Map	Thread Safe	Characteristic
HashTable	Y	1. Doesn't support null Key and Value 2. Every operation are synchronized 3. Slow Performance
HashMap	N	1. Support null key and Value 2. Not thread safe 3. Better performance than HashTable Put and Get operation constant time \(O(1)\) 4. `equals` and `hashcode` If `equals` return true, `hashcode` must return true. If override `hashcode`, then must override `equals` hashCode needs to be consistent, and the hash value returned by the state change must still be consistent. Symmetric, reflective, transitive, etc. properties of `equals`. 5. Doesn't keep order of the elements 6. Load Factor and Capacity The default load factor is `0.75`, and the default capacity is `16,` and max capacity is `1 << 30`. If size() > *threshold=loadFactorcapacity**, then double the capacity.
WeakHashMap	N	1. WeakHashMap saves the key with WeakReference. An entry in a WeakHashMap will automatically be removed when its key is no longer in ordinary use. 2. When methods `getTable`, `size`, `resize` are called, it will call method `expungeStaleEntries`, to get the entry which has been discarded by the GC from the `ReferenceQueue`, the set the value to null, to allow GC to discard the value objects.
LinkedListMap	N	1. Extends HashMap 2. The visit order is the insert order, it use a double linked list to keep the order 3. We can override removeEldestEntry method to implement a resource sensitive Map by removing the eldest Key-Value
ConcurrentHashMap	Y	Before Java 8: 1. It locks via ReentrantLock per Segment, Segment inherits from ReentrantLock When put a key-value into the Map, it hashes the key, and find the Segment, then put that key-value into that segment. As it only locks the segment which the key belongs, and other segements are not locked, so it improves the performance 2. The number of segments is determined by the concurrencyLevel, whose default value is 16 3. When increase the capacity, it's done per segment Java 8 and Afterwards: 1. Its internal structure is similar to HashMap 2. It still has segment, but only for compatibility 3. Due to not use segment, it uses lazy-load, which has a better init performance 4. Use CAS to performa lock-free operation in specific scenarios 5. Use low-level methods such as Unsafe and LongAdder to optimize extreme cases
TreeMap	N	1. Red-Black tree Map 2. Get, Put and Remove take time \(O(log(n))\) 3. It supports keeping the element order by the order of the Key, and supports customize the Comparator
ConcurrentSkipListMap	Y	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 class implements a concurrent variant of SkipLists providing expected average \(log(n)\) time cost for the containsKey, get, put and remove operations and their variants. Insertion, removal, update, and access operations safely execute concurrently by multiple threads.
EnumMap	N	1. A specialized Map implementation for use with enum type keys. All of the keys in an enum map must come from a single enum type that is specified, explicitly or implicitly, when the map is created. Enum maps are represented internally as arrays. This representation is extremely compact and efficient. 2. Enum maps are maintained in the natural order of their keys (the order in which the enum constants are declared). This is reflected in the iterators returned by the collections views (keySet(), entrySet(), and values()). 3. Its table size it fixed, and equals to the number of values defined in the Enum
IdentityHashMap	N	1. In an IdentityHashMap, two keys k1 and k2 are considered equal if and only if (k1==k2). 2. In normal Map implementations (like HashMap) two keys k1 and k2 are considered equal if and only if (k1==null ? k2==null : k1.equals(k2))