Structure des données JavaAnalyse du code source HashMap-javaDidacticiel-php.cn

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

Copier après la connexion

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

Copier après la connexion

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

Copier après la connexion

# 🎜🎜#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
# 🎜🎜#
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.