project	Thread safety	Whether null key values are supported	Usage scenarios
HashTable	is	Does not support	Java hash implementation is not recommended because of high synchronization overhead
HashMap	no	support	Put is preferred in most scenarios, and get time complexity is constant
TreeMap	no	Does not support	Sequential access map based on red-black tree, passing in comparators to determine the order, get,put,remove operation time complexity log(n)

Map class hierarchy

HashTable was an early hash implementation of Java that implemented the Dictionary interface.

TreeMap determines the order of elements based on the comparator;

The LinkedHashMap is traversed in the order of insertion. The following code is an example of automatic release of an infrequently used resource.

package org.example.mianshi; import java.util.LinkedHashMap; import java.util.Map; Public class App {public static void main(String[] args) {LinkedHashMap<String,String> linkedHashMap = new LinkedHashMap<String,String>(){ @Override protected boolean removeEldestEntry(Map.Entry<String, String> eldest) { return size()>3; }}; linkedHashMap.put("a","aaa"); linkedHashMap.put("b","bbb"); linkedHashMap.put("c","ccc"); linkedHashMap.forEach((k,v)->System.out.println(k+" = " + v)); System.out.println(linkedHashMap.get("a")); System.out.println(linkedHashMap.get("b")); System.out.println(linkedHashMap.get("c")); linkedHashMap.forEach((k,v)->System.out.println(k+" = " + v)); linkedHashMap.put("d","ddd"); System.out.println("========="); linkedHashMap.forEach((k,v)->System.out.println(k+" = " + v)); }}Copy the code

HashMap source code analysis

An array is called a bucket, and a list of the individual elements of the array is called a bin.

The key source for the PUT operation is as follows:

final V putVal(int hash, K key, V value, boolean onlyIfAbent,boolean evit) { Node<K,V>[] tab; Node<K,V> p; int , i; if ((tab = table) == null || (n = tab.length) = 0) n = (tab = resize()).length; if ((p = tab[i = (n - 1) & hash]) == ull) tab[i] = newNode(hash, key, value, nll); else { // ... if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for first treeifyBin(tab, hash); / /... }}Copy the code

Calculate the hash value of a hashMap:

static final int hash(Object kye) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>>16;
}Copy the code

Expansion logic

final Node<K,V>[] resize() { // ... else if ((newCap = oldCap << 1) < MAXIMUM_CAPACIY && oldCap >= DEFAULT_INITIAL_CAPAITY) newThr = oldThr << 1; // double there // ... else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; else { // zero initial threshold signifies using defaultsfults newCap = DEFAULT_INITIAL_CAPAITY; NewThr = (int)(DEFAULT_LOAD_ATOR* DEFAULT_INITIAL_CAPACITY; } if (newThr ==0) { float ft = (float)newCap * loadFator; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold = neThr; Node<K,V>[] newTab = (Node<K,V>[])new Node[newap]; Table = n; // Move to a new array structureCopy the code

The tree,

final void treeifyBin(Node<K,V>[] tab, int hash) { int n, index; Node<K,V> e; if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize(); else if ((e = tab[index = (n - 1) & hash]) ! = null) {// Tree change logic}}Copy the code

summary

From the thread safety first, whether to allow null keys, the use of scenarios speak HashTable, HashMap, the difference between a TreeMap. Then, it extends to the class level of Map and analyzes the data structure, hash value calculation, expansion and tree of hashMap that interviewers like to ask.

Original is not easy, reprint please indicate the source, let us exchange, common progress, welcome communication.