Führen Sie Sie durch die Schritte der Java8 HashMap-Quellcode-Analyse-javaLernprogramm-php.cn

Freunde, die Java verwendet haben, wissen möglicherweise nicht viel über HashMap. Ich hoffe, Sie bleiben bei der Studie

HashMap und Java8 Java7 Die HashMap in Java7 besteht hauptsächlich aus Array + verknüpfter Liste, während die HashMap in Java8 aus Array + verknüpfter Liste + rot-schwarzem Baum besteht. Wenn die Länge der verknüpften Liste 8 überschreitet, wird sie in Rot-Schwarz konvertiert Baum reduziert die zeitliche Komplexität der Suche und verbessert die Effizienz. Die Hauptanalyse hier ist HashMap in Java8.

Einführung in die Verwendung

Wenn wir in der täglichen Entwicklung HashMap verwenden, haben wir die folgenden zwei Initialisierungsmethoden:

1. Geben Sie die Anfangswertgröße nicht über new HashMap() an;

2. Geben Sie die Anfangswertgröße über new HashMap<>(int initialCapacity) an.

Initialisierung

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

Nach dem Login kopieren

HashMap#put()

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

Nach dem Login kopieren

rrree

hash()-Methode dient hauptsächlich der Beurteilung des gespeicherten Schlüsselwerts. Wenn er null ist, gibt er 0 zurück Wenn es null ist, wird das Ergebnis der bitweisen XOR-Verknüpfung zwischen dem Hash-Wert des Schlüssels und dem Hash-Wert ohne Vorzeichen, der um 16 Bit nach rechts verschoben ist, zurückgegeben (etwas gefaltet). Es ist ersichtlich, dass der Schlüsselwert von HashMap null sein kann. Die Hauptfunktion der Methode

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

Nach dem Login kopieren

HashMap#resize()

resize() besteht darin, das Array zu initialisieren oder Erweiterungsberechnungen für das Array durchzuführen.

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

Nach dem Login kopieren

Wie aus der resize()-Methode ersichtlich ist, bestimmt der Lastfaktor die Kapazität und Nutzung des Arrays.

Je größer der Lastfaktor, desto höher ist die Fülldichte des Arrays, was bedeutet, dass es mehr Elemente aufnehmen kann. Da jedoch die zeitliche Komplexität des Einfügens oder Löschens von Elementen aus dem Array O(n) beträgt, wird die Effizienz des Index gering.

Je kleiner jedoch der Lastfaktor, desto geringer ist die Fülldichte im Array, wodurch Platz verschwendet wird, aber die Indizierungseffizienz hoch ist (Platz wird gegen Zeit getauscht).

HashMap#get()

Im Vergleich zur Put-Methode ist die Get-Methode besonders einfach, da Sie sich nicht mehr um Erweiterungsprobleme kümmern müssen, sondern sich nur noch um die Datenerfassung kümmern müssen.

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

Nach dem Login kopieren

Verwandte Empfehlungen:

HashMap-Quellcode-Analyse

Detaillierte Erläuterung des Java Collection Frameworks HashSet- und HashMap-Quellcode-Analyse (Bild)

Das obige ist der detaillierte Inhalt vonFühren Sie Sie durch die Schritte der Java8 HashMap-Quellcode-Analyse. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!