Struktur data Java Analisis kod sumber HashMap

HashMap ialah struktur data yang biasa digunakan dalam rangka kerja pengumpulan Java Ia adalah jadual pemetaan berdasarkan jadual cincang Dalam versi JDK1.8, pelaksanaan kaedah dapatkan dan letak HashMap agak berbeza daripada sebelumnya. versi. , mari kita analisa pelaksanaan kod sumbernya langkah demi langkah.

Struktur asas

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

kaedah get

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

Aliran kerja kaedah get adalah seperti berikut:

• Kira kedudukan dalam jadual cincang mengikut kod cincang kunci

• Lintas senarai atau pepohon terpaut pada kedudukan dan cari kunci yang sepadan -value pair

• Jika pasangan kunci-nilai yang sepadan ditemui, nilai yang sepadan dikembalikan jika tidak null dikembalikan

kaedah letak

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

Aliran kerja kaedah put adalah seperti berikut:

• Kira kedudukan dalam jadual cincang berdasarkan nilai hashCode kunci

• Jika kedudukan kosong, masukkan nilai kunci baharu secara terus Untuk

• , jika kedudukan tidak kosong, lewati senarai terpaut atau pokok pada kedudukan untuk mencari sama ada pasangan nilai kunci sepadan

• Jika pasangan nilai kunci sepadan ditemui, gantikan nilai sepadan

• Jika kunci sepadan- pasangan nilai tidak ditemui, masukkan pasangan nilai kunci baharu di hujung senarai terpaut

• Jika panjang senarai terpaut mencapai ambang (lalai ialah 8), tukar senarai dipautkan ke dalam pepohon

• Jika saiz HashMap melebihi ambang selepas sisipan (kapasiti lalai ialah 0.75), kemudian kembangkan HashMap

• Selepas pemasukan selesai, lakukan beberapa operasi susulan yang diperlukan, seperti mengemas kini bilangan pengubahsuaian, dsb.

Secara amnya Dikatakan kaedah dapatkan dan kaedah put HashMap adalah berdasarkan algoritma cincang untuk merealisasikan carian dan sisipan pasangan nilai kunci Kaedah put perlu mempertimbangkan lebih banyak situasi, termasuk menukar senarai terpaut kepada pepohon, mengembangkan kapasiti, dsb.

Mengapakah kapasiti HashMap sentiasa 2 kepada n kuasa?

Di Java, sebab mengapa kapasiti HashMap sentiasa 2 kepada n kuasa adalah untuk meningkatkan prestasi HashMap.

Dalaman HashMap Gunakan tatasusunan untuk menyimpan pasangan nilai kunci Apabila menambah pasangan nilai kunci, HashMap akan mengira kedudukan indeksnya dalam tatasusunan berdasarkan nilai Kod cincang yang dibuat Jika panjang tatasusunan bukan kuasa 2. maka adalah perlu untuk mengira indeks. Lakukan operasi modulo, yang akan menjejaskan prestasi HashMap

Jika panjang tatasusunan ialah 2 kepada kuasa n, maka operasi bit (& operasi) boleh digunakan apabila. mengira indeks, yang lebih pantas daripada operasi modulo Dan , Operasi pengembangan HashMap juga memerlukan panjang untuk menjadi kuasa ke-2, yang boleh memudahkan pengiraan dan meningkatkan prestasi semasa pengembangan. satu lagi kelebihan saiz tatasusunan dengan panjang 2 hingga kuasa ke-n ialah, Ia boleh memastikan bahawa kebarangkalian konflik cincang pada kedudukan yang berbeza dalam tatasusunan adalah agak sekata, yang boleh mengurangkan berlakunya konflik cincang dan meningkatkan kecekapan HashMap.

Atas ialah kandungan terperinci Struktur data Java Analisis kod sumber HashMap. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!