Vous guide à travers les étapes de l'analyse du code source Java8 HashMap

Les amis qui ont utilisé Java ne connaissent peut-être pas grand-chose sur HashMap. J'espère que vous vous en tiendrez à l'étude

Avant-propos

HashMap et Java8. Java7 Le HashMap en Java7 est principalement composé d'un tableau + liste chaînée, tandis que le HashMap en Java8 est composé d'un tableau + liste chaînée + arbre rouge-noir. Lorsque la longueur de la liste chaînée dépasse 8, elle sera convertie en rouge-noir. les arbres réduisent la complexité temporelle de la recherche et améliorent l’efficacité. L'analyse principale ici est HashMap en Java8.

Introduction à l'utilisation

Dans le développement quotidien, lorsque nous utilisons HashMap, nous avons les deux méthodes d'initialisation suivantes :
1. Ne spécifiez pas la taille de la valeur initiale via new HashMap();
2. Spécifiez la taille de la valeur initiale via new HashMapa8093152e673feb7aba1828c43532094(int initialCapacity).

Initialisation

//  数组的默认初始容量
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);
}

La méthode hash() sert principalement à juger la valeur de la clé stockée si c'est le cas. S'il est nul, il renvoie 0 ; s'il n'est pas nul, il renvoie le résultat du XOR au niveau du bit entre la valeur de hachage de la clé et la valeur de hachage non signée décalée à droite de 16 bits (un peu alambiqué). On peut voir que la valeur clé de HashMap peut être nulle.

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()

La fonction principale de la méthode resize() est d'initialiser le tableau ou d'effectuer des calculs d'expansion sur le tableau.

    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;
}

Comme le montre la méthode resize(), le facteur de charge détermine la capacité et l'utilisation de la baie.
Plus le facteur de charge est grand, plus la densité de remplissage du tableau est élevée, ce qui signifie qu'il peut accueillir plus d'éléments. Cependant, puisque la complexité temporelle de l'insertion ou de la suppression d'éléments du tableau est O(n), l'efficacité de l'index deviendra faible.
Cependant, plus le facteur de charge est petit, plus la densité de remplissage dans le tableau est faible, ce qui gaspillera de l'espace, mais l'efficacité de l'indexation est élevée (l'espace est échangé contre du temps).

HashMap#get()

Par rapport à la méthode put, la méthode get est particulièrement simple, car vous n'avez plus à vous soucier des problèmes d'expansion, il vous suffit de vous occuper de l'acquisition de données.

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;
}

Recommandations associées :

Analyse du code source HashMap

Explication détaillée de Java cadre de collecte Analyse du code source HashSet et HashMap (photo)

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!