Structure des données JavaAnalyse du code source HashMap

HashMap est une structure de données couramment utilisée dans le framework de collection Java. Il s'agit d'une table de mappage basée sur une table de hachage. Dans la version JDK1.8, l'implémentation des méthodes get et put de HashMap est quelque peu différente de celle-ci. versions précédentes. Différent, analysons l'implémentation de son code source étape par étape

Structure de base

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 méthode

    /**
     * 根据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 méthode workflow est comme. suit : #🎜🎜 #

• Calculer la position dans la table de hachage en fonction du hashCode de la clé

• Traverser le liste chaînée ou arbre à la position , recherchez la paire clé-valeur correspondante

• Si la paire clé-valeur correspondante est trouvée, renvoyez la valeur correspondante sinon renvoyez null# ; 🎜🎜#

  # 🎜🎜#

  put method

    /**
     * 向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;
    }

Le flux de travail de la méthode put est le suivant :

# 🎜🎜#Le hachage est calculé en fonction de la valeur hashCode de la clé Position dans le tableau

• Si la position est vide, insérez directement la nouvelle paire clé-valeur # 🎜🎜#

• Si la position n'est pas vide, parcourez la liste chaînée ou l'arbre à la position pour savoir si la paire clé-valeur correspondante existe déjà

• Si la paire clé-valeur correspondante est trouvée, Remplacez ensuite la valeur correspondante

• Si la paire clé-valeur correspondante n'est pas trouvée, insérez la nouvelle paire clé-valeur à la fin de la liste chaînée
  # 🎜🎜#
Si la longueur de la liste chaînée atteint le seuil (la valeur par défaut est 8), convertissez la liste chaînée dans un arbre
Si la taille du HashMap dépasse le seuil après insertion (0,75 de la capacité par défaut), alors développez le HashMap
Une fois l'insertion terminée, effectuez certaines opérations de suivi nécessaires, telles que la mise à jour du nombre de modifications, etc.
En général , la méthode get et la méthode put de HashMap sont basées sur l'algorithme de hachage pour réaliser la recherche et l'insertion de paires clé-valeur. La méthode put doit prendre en compte davantage de situations, y compris la conversion de listes chaînées pour les arbres, l'expansion, etc. 🎜#
• Pourquoi la capacité de HashMap est-elle toujours de 2 à la puissance n ?
  En Java, la raison pour laquelle la capacité de HashMap est toujours de 2 à la puissance n C'est pour améliorer les performances de HashMap.

HashMap utilise en interne un tableau pour stocker les paires clé-valeur. Lorsqu'une paire clé-valeur est ajoutée, HashMap calculera sa position d'index dans le tableau en fonction de la valeur hashCode créée. la longueur du tableau n'est pas la nième puissance de 2, alors une opération modulo est requise lors du calcul de l'index, ce qui affectera les performances de HashMap

Si la longueur du tableau est de 2 à la nième puissance. calculer l'index Vous pouvez utiliser des opérations sur bits (& opérations), qui sont plus rapides que l'opération modulo. De plus, l'opération d'expansion de HashMap nécessite également que la longueur soit la puissance n de 2, ce qui peut simplifier le calcul et améliorer les performances lors de l'expansion. .

# 🎜🎜# De plus, un autre avantage d'une taille de tableau avec une longueur de 2 élevée à la puissance n est qu'elle peut garantir que la probabilité de conflits de hachage à différentes positions du tableau est relativement égale, ce qui peut réduire l'apparition de conflits de hachage et améliorer l'efficacité de HashMap .

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!