Take you through the steps of Java8 HashMap source code analysis

Friends who have used Java may not know much about HashMap. The content of the article is very compact. I hope you will continue to study.

Preface

HashMap and Java8 in Java7 The HashMap in Java7 is mainly composed of an array linked list, while the HashMap in Java8 is composed of an array linked list red-black tree. When the length of the linked list exceeds 8, it will be converted into a red-black tree. , reduce the time complexity of search, thereby improving efficiency. The main analysis here is HashMap in Java8.

Introduction to use

In daily development, when we use HashMap, we have the following two initialization methods:
1. Do not specify the initial value size through new HashMap();
2. Specify the initial value size through new HashMap<>(int initialCapacity).

Initialization

//  数组的默认初始容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//  最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
//  默认负载因子（用来控制阈值和容量，当数组已经存放的容量超过了阈值时，容量会扩大一倍
//  阈值 = 最大容量 * 负载因子）
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//  默认链表的最大长度（当链表的长度超过8时会被转换为红黑树）
static final int TREEIFY_THRESHOLD = 8;
//  使用第一种初始化方式时，默认初始化容量是2的4次
public HashMap() {    
this.loadFactor = DEFAULT_LOAD_FACTOR; 
}
public HashMap(int initialCapacity) {   
     this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
     public HashMap(int initialCapacity, float loadFactor) {   
      //  不能小于0
    if (initialCapacity < 0) 
             throw new IllegalArgumentException("Illegal initial capacity: initialCapacity); 
                //  超过2的30次方，则最大容量为2的30次方
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;  
                  if (loadFactor <= 0 || Float.isNaN(loadFactor))   
                       throw new IllegalArgumentException("Illegal load factor: loadFactor);
                           this.loadFactor = loadFactor;   
                 //  计算阈值（在第一次put值的时候，会在resize()方法中重新计算）
    this.threshold = tableSizeFor(initialCapacity);
}

HashMap#put()

public V put(K key, V value) 
{    return putVal(hash(key), key, value, false, true);
}

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

The hash() method mainly judges the stored key value. If it is null, it returns 0; no If it is null, the result of bitwise XOR between the key's hash value and the hash value unsigned right-shifted by 16 bits is returned (a bit convoluted). It can be seen that the key value of HashMap can be null.

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;   
     //  第一次put值时，会初始化当前数组长度，如果没有指定，则默认为16
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;  
          //  找到在数组中对应的下标，如果该位置没有值，那么直接初始化一个Node放在此位置
             // 由&运算可以确保(n - 1) & hash一定是小于数组容量
        tab[i] = newNode(hash, key, value, null);  
          else {
        Node<K,V> e; K k;        
        //  如果key值已经存在，则取出这个节点
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;       
             //  如果当前key值的节点是红黑树，则调用红黑树的插值算法
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);    
                else {            
                //  如果是链表，则遍历链表，采用尾插的方式
            for (int binCount = 0; ; ++binCount) {               
             if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);        
                   //  如果链表的长度大于等于8，则将链表转换为红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);       
                                 break;
                }               
                 //  如果在链表的节点中存在相同的key，则结束循环
                if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))                    break;
                p = e;
            }
        }        //  如果存在相同的key值，则重新赋值，并且返回旧值
        if (e != null) { 
        // existing mapping for key
            V oldValue = e.value;           
             //  由源码可知onlyIfAbsent默认false 
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);  
          return oldValue;
        }
    }
    ++modCount;   
     //  如果数组已经容纳的长度超过了设定的阈值，则会对该数组进行扩容，每次扩容是之前长度的两倍
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);   
     //  每一个不同的key值第一次put的时候返回null。
    return null;
}

HashMap#resize()

The main function of the resize() method is to initialize the array or perform expansion calculations on the array.

    final Node<K,V>[] resize() {    
       //  备份原始数组
    Node<K,V>[] oldTab = table;    
    //  第一次put值的时候为0
    int oldCap = (oldTab == null) ? 0 : oldTab.length;   
     //  如果没有指定初始值大小，第一次put值的时候阈值为0
    int oldThr = threshold;    int newCap, newThr = 0;   
     //  如果数组不为null且长度不为0，则会
    if (oldCap > 0) {       
     //  如果长度大于等2的30次方，则默认阈值为int的最大值（即2的31次方减1）
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;            
            return oldTab;
        }       
         //  如果将数组长度扩大一倍后的值小于2的30次方并且数组之前的长度大于等于2的4次方，则将阈值扩大
          //  一倍，否则阈值会在下面的if (newThr == 0)中进行赋值
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)     
               //  将阈值扩大一倍
            newThr = oldThr << 1; // double threshold
          }   
     //  如果使用new HashMap(int initialCapacity)初始化，则第一次put值时会进入这里
    else if (oldThr > 0) 
        initial capacity was placed in threshold
        newCap = oldThr;  
          //  如果使用new HashMap()初始化，则第一次put值时会进入这里
    else {             
          zero initial threshold signifies using defaults
        //  默认数组大小是2的4次方
        newCap = DEFAULT_INITIAL_CAPACITY;        
        //  默认负载因子是0.75，即默认阈值为12
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }   
     //  只有以下两种情况会进入到if判断中：
      //  1、在使用new HashMap(int initialCapacity)初始化，并且第一次put值的时候
      //   2、对数组进行扩容且数组的原始长度小于2的4次方的时候
    if (newThr == 0) {       
     //  根据指定的数组大小和负载因子乘积得到阈值
        float ft = (float)newCap * loadFactor;       
      //  如果数组大小和阈值都小于2的20次方，则确定阈值
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                    (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;   
     @SuppressWarnings({"rawtypes","unchecked"})   
      //  用新的数组大小初始化新的数组
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;   
     //  如果是第一次初始化，则直接返回newTab。如果不是则会进行数据的迁移操作
    if (oldTab != null) {  
          //  遍历数组
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;            
            if ((e = oldTab[j]) != null) {         
                   //  将已经被取出的位置置空
                oldTab[j] = null;       
                         //  如果数组该位置只是单个节点，那么直接赋值
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;   
                                 //  如果数组该位置是红黑树
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);    
                                //  如果数组该位置是链表，保证原始的循序进行迁移
                else { 
                      preserve order
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;                        
                        if ((e.hash & oldCap) == 0) {                            
                        if (loTail == null)
                                loHead = e;                            
                                else
                                loTail.next = e;
                            loTail = e;
                        }                        
                        else {                            
                        if (hiTail == null)
                                hiHead = e;                            
                                else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);                    
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }                    
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }    return newTab;
}

As can be seen from the resize() method, the load factor determines the capacity and usage of the array.
The larger the load factor, the higher the filling density of the array, which means it can accommodate more elements. However, since the time complexity of inserting or deleting elements from the array is O(n), the efficiency of the index will become low.
However, the smaller the load factor, the sparser the filling density in the array, which will waste space, but the indexing efficiency is high at this time (space is exchanged for time).

HashMap#get()

Compared with the put method, the get method is particularly simple, because you no longer need to worry about expansion issues, you only need to deal with data acquisition.

public V get(Object key) {
    Node<K,V> e; 
       return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;    //  首先判断数组不为null以及长度大于0并且对应位置节点不为null
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {        //  判断第一个节点是否满足条件
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))            return first;        //  如果节点的下一个节点不为null
        if ((e = first.next) != null) {            //  判断该节点是否为红黑树
            if (first instanceof TreeNode)                return ((TreeNode<K,V>)first).getTreeNode(hash, key);            //  遍历链表，判断是否有满足条件的节点存在
            do {                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))                    return e;
            } while ((e = e.next) != null);
        }
    }    return null;
}

Related recommendations:

HashMap source code analysis

Detailed explanation of Java collection framework HashSet and HashMap Source code analysis (picture)

The above is the detailed content of Take you through the steps of Java8 HashMap source code analysis. For more information, please follow other related articles on the PHP Chinese website!