Java-Datenstruktur-HashMap-Quellcode-Analyse

HashMap ist eine häufig verwendete Datenstruktur im Java-Sammlungsframework. Es handelt sich um eine Zuordnungstabelle, die auf einer Hash-Tabelle basiert. In der JDK1.8-Version unterscheidet sich die Implementierung der Get-Methode und der Put-Methode etwas von der vorherigen Version , wie folgt: Analysieren wir die Quellcode-Implementierung Schritt für Schritt.

Grundstruktur

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
    // ... 
    /**
     * 默认初始容量为16
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    /**
     * 默认负载因子为0.75
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    /**
     * 最大容量:1 << 30(2的30次方)
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;
    /**
     * 存放元素的数组,长度总是2的幂次方
     */
    transient HashMap.Node<K,V>[] table;
    /**
     * 存放键值对的数量
     */
    transient int size;
    /**
     * 扩容操作的阈值
     */
    int threshold;
    /**
     * 负载因子,用于计算阈值
     */
    final float loadFactor;
	// ...   
}

get-Methode

    /**
     * 根据key获取value,如果key不存在则返回null
     *
     * @param key
     * @return
     */
    public V get(Object key) {
        // 获取key对应的Node节点
        HashMap.Node<K, V> e;
        // 调用getNode方法查找key对应的Node节点,并将查找结果赋值给e
        // 如果e为null就返回null否则返回e节点的value
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }
    /**
     * 根据key的哈希值和key查找对应的Node节点
     *
     * @param hash
     * @param key
     * @return
     */
    final HashMap.Node<K, V> getNode(int hash, Object key) {
        // 定义局部变量tab,first,e,n和k
        HashMap.Node<K, V>[] tab;
        HashMap.Node<K, V> first, e;
        int n;
        K k;
        // 如果table数据不为null且长度大于0,且第一个Node节点不为空,则开始查找Node节点
        if ((tab = table) != null && (n = tab.length) > 0 &&
                (first = tab[(n - 1) & hash]) != null) {
            // 如果第一个Node节点的哈希值与传入的hash值相等,且第一个Node节点的key和传入的key相等,则直接返回第一个Node节点
            if (first.hash == hash && // always check first node
                    ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            // 如果第一个Node节点不是要查找的Node节点,则开始遍历链表查找对应的Node节点
            if ((e = first.next) != null) {
                if (first instanceof HashMap.TreeNode)
                    // 如果第一个Node节点是红黑树节点,则调用红黑树节点的getTreeNode方法查找对应的Node节点
                    return ((HashMap.TreeNode<K, V>) first).getTreeNode(hash, key);
                // 如果第一个Node节点不是红黑树节点,则遍历链表查找对应的Node节点
                do {
                    // 如果遍历到的Node节点的hash值与传入的hash值相等,且Node节点的key和传入的key相等,则返回对应的Node节点
                    if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        // 如果在table数组中没有找到对应的Node节点,则返回null
        return null;
    }

get-Methoden-Workflow ist wie folgt:

• Berechnen Sie die Position in der Hash-Tabelle basierend auf dem HashCode des Schlüssels

• Durchlaufen Sie die Position in der verknüpften Liste oder im Baum und suchen Sie das entsprechende Schlüssel-Wert-Paar Der Workflow der

      /**
       * 向HashMap中添加一个key-value键值对
       *
       * @param key
       * @param value
       * @return
       */
      public V put(K key, V value) {
          // 根据key的哈希值和key查找对应的Node节点,并添加到HashMap中
          return putVal(hash(key), key, value, false, true);
      }
      /**
       * 根据key的hash值和key添加一个键值对到HashMap中
       *
       * @param hash
       * @param key
       * @param value
       * @param onlyIfAbsent
       * @param evict
       * @return
       */
      final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                     boolean evict) {
          // 定义局部变量tab,p,n和i
          HashMap.Node<K, V>[] tab;
          HashMap.Node<K, V> p;
          int n, i;
          // 如果table数组为null或者长度为0,则先调用resize()方法初始化table数组
          if ((tab = table) == null || (n = tab.length) == 0)
              n = (tab = resize()).length;
          // 根据计算出来插入位置i插入新的键值对
          if ((p = tab[i = (n - 1) & hash]) == null)
              // 如果插入的位置为null,则直接插入新的键值对
              tab[i] = newNode(hash, key, value, null);
          else {
              HashMap.Node<K, V> e;
              K k;
              // 如果插入的位置不为null,就遍历链表或树查找插入位置
              if (p.hash == hash &&
                      ((k = p.key) == key || (key != null && key.equals(k))))
                  e = p;
              else if (p instanceof HashMap.TreeNode)
                  // 如果插入位置为红黑树节点,则调用putTreeVal方法插入新的键值对
                  e = ((HashMap.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);
                          if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                              // 如果此时链表长度大于等于8,则将链表转化为红黑树
                              treeifyBin(tab, hash);
                          break;
                      }
                      // 如果找到相同key,终止循环
                      if (e.hash == hash &&
                              ((k = e.key) == key || (key != null && key.equals(k))))
                          break;
                      p = e;
                  }
              }
              if (e != null) { // existing mapping for key
                  // 如果存在相同key,则替换对应value
                  V oldValue = e.value;
                  if (!onlyIfAbsent || oldValue == null)
                      e.value = value;
                  afterNodeAccess(e);
                  return oldValue;
              }
          }
          ++modCount;
          if (++size > threshold)
              // 如果插入后的HashMap的大小大于阈值,则调用resize方法扩容HashMap
              resize();
          afterNodeInsertion(evict);
          return null;
      }

put-Methode ist wie folgt:
Berechnen Sie die Position in der Hash-Tabelle basierend auf dem HashCode-Wert des Schlüssels

Wenn die Position leer ist, fügen Sie direkt das neue Schlüssel-Wert-Paar ein

• Wenn die Position nicht leer ist, durchlaufen Sie die Position Überprüfen Sie in der verknüpften Liste oder im Baum, ob das entsprechende Schlüssel-Wert-Paar bereits vorhanden ist

• Wenn das entsprechende Schlüssel-Wert-Paar gefunden wird, ersetzen Sie den entsprechenden Wert

• Wenn das entsprechende Schlüssel-Wert-Paar nicht gefunden wird, ersetzen Sie den neuen Schlüssel durch das neue Schlüssel-Wert-Paar. Wertepaare werden am Ende der verknüpften Liste eingefügt

• Wenn die Länge der verknüpften Liste den Schwellenwert erreicht (Standard ist). 8) Konvertieren Sie die verknüpfte Liste in einen Baum

• Wenn die Größe der HashMap nach dem Einfügen den Schwellenwert (0,75 der Standardkapazität) überschreitet, erweitern Sie die HashMap

• Nachdem das Einfügen abgeschlossen ist, führen Sie einige notwendige Schritte aus B. das Aktualisieren der Anzahl der Änderungen usw.

• Im Allgemeinen basieren die Get-Methode und die Put-Methode von HashMap auf dem Hash-Algorithmus, um die Suche nach Schlüssel-Wert-Paaren und das Einfügen zu erreichen. Die Put-Methode muss dies tun Berücksichtigen Sie weitere Situationen, einschließlich der Konvertierung einer verknüpften Liste in einen Baum, der Erweiterung usw.

Warum ist die Kapazität von HashMap immer die n-te Potenz von 2? In Java beträgt die Kapazität von HashMap immer 2. Der Grund für die n-te Potenz ist Um die Leistung von HashMap zu verbessern, verwendet HashMap intern ein Array zum Speichern von Schlüssel-Wert-Paaren. Wenn ein Schlüssel-Wert-Paar hinzugefügt wird, berechnet HashMap seine Indexposition im Array basierend auf der Länge von Das Array ist nicht die n-te Potenz von 2, dann ist bei der Berechnung des Index eine Modulo-Operation erforderlich, die sich auf die Leistung von HashMap auswirkt.

• Wenn die Länge des Arrays nicht die n-te Potenz von 2 ist, sind Bitoperationen (& Darüber hinaus erfordert die Erweiterungsoperation von HashMap auch eine Länge der n-ten Potenz von 2, was die Berechnung vereinfachen und die Leistung während der Erweiterung verbessern kann zur n-ten Potenz Ein weiterer Vorteil der Array-Größe besteht darin, dass sichergestellt werden kann, dass die Wahrscheinlichkeit von Hash-Konflikten an verschiedenen Positionen im Array relativ gleichmäßig ist, was das Auftreten von Hash-Konflikten reduzieren und die Effizienz von HashMap verbessern kann.

Das obige ist der detaillierte Inhalt vonJava-Datenstruktur-HashMap-Quellcode-Analyse. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!