In-depth understanding of Map, HashMap, LinkedHashMap, TreeMap, etc

Please indicate the original source, thank you!

HappyFeet blog

1, the Map

A Map is an interface that represents key-value pairs. A Map cannot contain duplicate keys. One key corresponds to a maximum of one value. Some Map implementations allow null values and some do not.

2, a HashMap

Map interface implementation based on hash table. Except that synchronization is not implemented and null values are allowed, HashMap is roughly the same as HashTable, although HashTable is largely obsolete and CurrentHashMap is a better alternative if synchronization is needed.

Let’s look at some of the core code in HashMap

/** * Returns a power of two size for the given target capacity. */
/* tableSize. */ tableSize. */ tableSize. */ tableSize
static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0)?1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
Copy the code

The size of the underlying HashMap hash table is always a multiple of 2, which is an optimization of the efficiency of HashMap: When the length of the underlying array is 2^n, h & (length-1) is equivalent to modulating length, which is much more efficient than modulating it directly.

// Find the node with hash and key as key
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
	If the table is not empty, return null. If the table is not empty, use the hash value to modulo ((n-1) &hash) to get the index */ in the table
    if((tab = table) ! =null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) ! =null) {
        // If there is a value at the subscript, compare the hash and key of the first element at that position
        if (first.hash == hash && // always check first node((k = first.key) == key || (key ! =null && key.equals(k))))
            return first;
        // The following code resolves the hash conflict, but generally it is not possible to use the following code
        if((e = first.next) ! =null) {
	        /* If there are hash conflicts, go back to the bottom. If there are more hash conflicts, use red-black tree to handle hash conflicts, and do red-black tree lookup */
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            // Otherwise it's a simple list lookup
            do {
                if(e.hash == hash && ((k = e.key) == key || (key ! =null && key.equals(k))))
                    return e;
            } while((e = e.next) ! =null);
            // If not found, it does not exist and returns null}}return null;
}
Copy the code

// Store nodes with hash and key in the HashMap
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
	        // If the hash table is empty, initialize it.
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
	        // If the position has no value, place it directly in the changed position
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if(p.hash == hash && ((k = p.key) == key || (key ! =null && key.equals(k))))
                // If the position has a value and the key is the same, assign a reference to p to e
                e = p;
            else if (p instanceof TreeNode)
	            // If the object is a TreeNode, the tree insertion algorithm is executed
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
	                // Otherwise, search through the list until you find the same key or the end of the list
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
	                        // Convert the list to a red-black tree when the number of elements exceeds a threshold
                            treeifyBin(tab, hash);
                        break;
                    }
                    if(e.hash == hash && ((k = e.key) == key || (key ! =null && key.equals(k))))
                        break; p = e; }}if(e ! =null) { // existing mapping for key
	            // If not putIfAbsent, replace the original value and return the original value
                V oldValue = e.value;
                if(! onlyIfAbsent || oldValue ==null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }
Copy the code

Another thing worth noting is the HashMap’s resize method, which is used when initializing and expanding capacity. When the capacity of the HashMap is expanded, the capacity of the HashMap will be doubled. At the same time, the hash values of all the original elements need to be recalculated and their positions will also change accordingly, which is quite performance-consuming. If the Map size is known in advance, You can subtract the resize overhead by creating a size-appropriate Map at the outset.

As you can see from the code above, HashMap is based on hash tables and uses a zip method to resolve hash conflicts. So the underlying data structure of a HashMap is “array + list”, where the elements are arrays of lists. Static final int TREEIFY_THRESHOLD = 8; Is converted to a red-black tree, so if there are too many hash collisions, the elements of the array will be red-black trees.

Diagram of resolving hash conflicts by zipper method:

3, LinkedHashMap

LinkedHashMap has all the features of HashMap. It maintains one more bidirectional list than HashMap, so it can iterate from the head or the tail in the order of insertion. It is ordered, but because it maintains one more bidirectional list than HashMap, It has more memory and less performance than HashMap, but if you need to consider the order in which elements are inserted, LinkedHashMap is a good choice.

4, SortedMap

SortedMap is an ordered Map interface that sorts by nature or by the incoming comparator. SortedMap provides subMap(K fromKey, K toKey), Additional methods, such as headMap(K toKey), tailMap(K fromKey), are used to get values related to element order.

5, TreeMap

Unlike HashMap, TreeMap is a red-black tree with its containsKey, GET, PUT, and remove methods in log(n) time. And it is arranged in the natural (or specified) order of keys, unlike LinkedHashMap, which ensures that elements are arranged in the order they were inserted.

Finally, summarize the differences between HashMap, LinkedHashMap, and TreeMap by referring to an image from StackOverflow:

References:

(1) Difference between HashMap, LinkedHashMap and TreeMap

(2) JDK 1.8 documentation