欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

荐 HashMap代码解析-4.4源码内部HashMap.java

程序员文章站 2022-07-03 17:54:39
HashMap 基本接口和功能分析带着问题来阅读此文:1),HashMap内部存储格式是什么样式的?2),HashMap扩容策略是什么?3),HashMap增删改查是如何实现的?4),为什么使用HashMap,优劣势?1,HashMap注释解读注意:以下分析和代码,是基于Android aosp4.4源码中的以下java类(openjdk?),可能跟java-jdk中的部分逻辑看起来不太一样libcore/luni/src/main/java/java/util/HashMap.java官...

HashMap 基本接口和功能分析

带着问题来阅读此文:
1),HashMap内部存储格式是什么样式的?
2),HashMap扩容策略是什么?
3),HashMap增删改查是如何实现的?
4),为什么使用HashMap,优劣势?

1,HashMap注释解读

注意:以下分析和代码,是基于Android aosp4.4源码中的以下java类(openjdk?),可能跟java-jdk中的部分逻辑看起来不太一样
libcore/luni/src/main/java/java/util/HashMap.java

官方注释:

/**
 * HashMap is an implementation of {@link Map}. All optional operations are supported.
 *
 * <p>All elements are permitted as keys or values, including null.
 *
 * <p>Note that the iteration order for HashMap is non-deterministic. If you want
 * deterministic iteration, use {@link LinkedHashMap}.
 *
 * <p>Note: the implementation of {@code HashMap} is not synchronized.
 * If one thread of several threads accessing an instance modifies the map
 * structurally, access to the map needs to be synchronized. A structural
 * modification is an operation that adds or removes an entry. Changes in
 * the value of an entry are not structural changes.
 *
 * <p>The {@code Iterator} created by calling the {@code iterator} method
 * may throw a {@code ConcurrentModificationException} if the map is structurally
 * changed while an iterator is used to iterate over the elements. Only the
 * {@code remove} method that is provided by the iterator allows for removal of
 * elements during iteration. It is not possible to guarantee that this
 * mechanism works in all cases of unsynchronized concurrent modification. It
 * should only be used for debugging purposes.
 *
 * @param <K> the type of keys maintained by this map
 * @param <V> the type of mapped values
 */

翻译:
1,允许所有元素作为键或值,包括null。
2,请注意,HashMap的迭代顺序是不确定的。 如果要进行确定性迭代,请使用{@link LinkedHashMap}。
解读:是无序的,iteration的最后一个,可能不是最后插入的那一个
3,非线程同步的
4,map.entrySet().iterator()可能导致ConcurrentModificationException,需要在使用map增删改查的地方,保证没有多线程调用,或加线程同步锁

2,HashMap构造函数和重要的常量

/**
 * Max capacity for a HashMap. Must be a power of two >= MINIMUM_CAPACITY.
 */
private static final int MAXIMUM_CAPACITY = 1 << 30;
private static final int MINIMUM_CAPACITY = 4;
private static final Entry[] EMPTY_TABLE
        = new HashMapEntry[MINIMUM_CAPACITY >>> 1];

private transient int threshold;
// 构造
public HashMap() {
    table = (HashMapEntry<K, V>[]) EMPTY_TABLE;
    threshold = -1; // Forces first put invocation to replace EMPTY_TABLE
}

// 静态内部类HashMapEntry,链表格式数据结构
static class HashMapEntry<K, V> implements Entry<K, V> {
    final K key;
    V value;
    final int hash;
    HashMapEntry<K, V> next;
}

3,增加和更新数据,HashMap.put方法是HashMap的核心

这里进行了HashMap的插入或替换原有value值,扩容的工作。

@Override public V put(K key, V value) {
    if (key == null) {
        // 专门为key为null的数据,准备了一个内部对象entryForNullKey
        // 可能是null的hash值没办法计算
        return putValueForNullKey(value);
    }

    // 获取key对应的hash int值, 通过secondaryHash计算的数值,不唯一
    int hash = secondaryHash(key);
    // HashMapEntry为链表格式数据结构, table为数组类型:HashMapEntry[]
    // 数组中每个item是HashMapEntry链表
    HashMapEntry<K, V>[] tab = table;
    // hash值与当前数组大小-1  取按位与,获取到的数据的值
    // 这个数值,会落在0  到 tab.length - 1的某一位上,应该是为了均匀分布到
    // 注意length大小为2的n次方,length-1时,即二进制形式高位变为0,其余位变为1
    // 这里计算的index的值,取的是hash的低length-1位的二进制数值
    // 注意这个地方的计算方式,在doubleCapacity()扩容逻辑里需要了解
    int index = hash & (tab.length - 1);
    // 获取table数组 index位置上的对象HashMapEntry, 遍历当前位置的链表深度
    // 查找是否有相同key的HashMapEntry,如果存在此对象,替换value值即可。
    // 疑问,为什么只从这一个index里查找,扩容后,应该落不到这个index里吧?
    // 等扩容后,会落在新的index里,待会儿需要确认下扩容是不是重新计算了index值
    for (HashMapEntry<K, V> e = tab[index]; e != null; e = e.next) {
        // 判断到e.hash != hash 时,就不再判断equals,短路后面的判断逻辑,提高效率?
        // 两个不同的key,通过secondaryHash计算出来的数值一样,所以需要&&运算
        if (e.hash == hash && key.equals(e.key)) {
            // 找到了相同的key,替换value即可!插入数据完成。
            preModify(e);
            V oldValue = e.value;
            e.value = value;
            return oldValue;
        }
    }
    // 到这里,说明没有找到已存储的对象
    // No entry for (non-null) key is present; create one
    // 虽然不支持线程同步,但是这里还是尽可能用此方式来检查线程同步问题。
    modCount++;
    // size++即当前数据总数+1, 然后检查是否需要扩容
    // 为什么要扩容?可能是为了减少链表的深度,加快查询效率
    if (size++ > threshold) {
        // 扩容,下面进行详解,猜测是对threshold赋值,对table数组扩容,并且对之前的数据进行复制。
        tab = doubleCapacity();
        // 重新根据当前数组的length,计算下标index。
        // 注意,如果不重新计算index,用之前的size计算出的index会有问题!
        // 下次put相同的key时,找的index下标可能不一致,导致脏数据存在!
        index = hash & (tab.length - 1);
    }
    // 将数据加入数组下标index对应的链表中。
    addNewEntry(key, value, hash, index);
    // 没找到对应的数据,所以返回null.插入数据完成。
    return null;
}

addNewEntry方法j简介:

    // 初始化一个新的HashMapEntry对象
    // 并将此对象的next指向table[index],然后将table[index]指向此对象
    void addNewEntry(K key, V value, int hash, int index) {
        table[index] = new HashMapEntry<K, V>(key, value, hash, table[index]);
    }

    //HashMaoENtry构造方法
    HashMapEntry(K key, V value, int hash, HashMapEntry<K, V> next) {
        this.key = key;
        this.value = value;
        this.hash = hash;
        // 此对象变成了链表的头,并将next指向链表之前的头
        this.next = next;
    }

secondaryHash数值计算的疑问:
1),不同的key是否通过此方法计算后,得出相同的数值,根据链表的存储结构猜测是这样的
2),同一个key值,在不同的size时,hash数值跟size-1进行逻辑与&运算后,如何保证落在同一个链表里?应该是扩容时,重新计算了index。

    // Doug Lea's supplemental secondaryHash function (non-inlined).
    // Replace with Collections.secondaryHash when the VM is fast enough (http://b/8290590).
    static int secondaryHash(Object key) {
        int hash = key.hashCode();
        hash ^= (hash >>> 20) ^ (hash >>> 12);
        hash ^= (hash >>> 7) ^ (hash >>> 4);
        return hash;
    }

扩容方法,做了以下工作:
1,重新申请更大的数组
2,赋值新的threshold临界值
3,将旧数据复制到新数组

    private HashMapEntry<K, V>[] doubleCapacity() {
        HashMapEntry<K, V>[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            // 如果超过了最大值,则不进行扩容,若有新的数据,则链表深度进行增加
            return oldTable;
        }
        int newCapacity = oldCapacity * 2;//两倍扩容
        // new 出来一个新的数组,并给threshold赋值
        // threshold是newCapacity*3/4,是指达到3/4容量就进行扩容吗??
        HashMapEntry<K, V>[] newTable = makeTable(newCapacity);
        if (size == 0) {
            // 当前没有数据插入,返回新数组即可,当构造方法传入HashMap集合时,可能触发此逻辑
            return newTable;
        }
        // 下面应该是重新计算hash值对应的index,以及拷贝原来数据吧??
        for (int j = 0; j < oldCapacity; j++) {
            /*
             * Rehash the bucket using the minimum number of field writes.
             * This is the most subtle and delicate code in the class.
             * 翻译:使用最少的字段写入次数重新哈希存储桶。
             * 这是类里最微妙的代码,确实是!第一二三遍看不懂~~~
             */
            HashMapEntry<K, V> e = oldTable[j];
            if (e == null) {
                continue;
            }
            // 这是啥!跟之前index = hash & (tab.length - 1)看起来有点像!难道是亲兄弟??
            // tab.length=2的n次方,即100000……
            // index与highBit的差别:
            // index舍弃了第length高位1,取的剩余length-1位的值
            // highBit只取第length高位的值,剩余的舍弃。这哥俩真是两个极端!
            int highBit = e.hash & oldCapacity;
            HashMapEntry<K, V> broken = null;
            // 下面一行代码,应该就是数据拷贝的地方,这里的下标为什么这样计算j | highBit?
            // 跟前面put函数里计算下标的结果一样吗?
            // 如果不一样的话,会出现插入已存在的key值时,找不到正确index和链表的错误啊?
            // 进行以下方程式确认算法是否一致:
            // j=hash&(oldCapacity-1) ,
            // j | highBit=(hash & (oldCapacity-1)) | (e.hash & oldCapacity)
            // 注意oldCapacity为2的n次方,oldCapacity-1,在二进制时,是高位变为0,其余位变为1
            //            = (hash最高位为0,保留低位)) | (hash保留高位的数值,其余位数为0);
            //            = hash & oldCapacity二进制位数这样多的1;
            //            = hash &(oldCapacity*2-1);
            //            = hash & (newCapacity-1); 
            // 因此此处oldCapacity是2的n次方,所以此等式是成立的
            // 所以此处的运算跟put函数里计算下标的结果是一样的!
            // 此处费了这么大劲儿的好处是什么?比着后面的这个计算方式,少了-1的运算吗???
            // 没有明白!比后面的好到哪里去了?改天写个test试下效率!hash & (newCapacity -1)
            newTable[j | highBit] = e;
            // 以下逻辑未理清
            for (HashMapEntry<K, V> n = e.next; n != null; e = n, n = n.next) {
                int nextHighBit = n.hash & oldCapacity;
                if (nextHighBit != highBit) {
                    if (broken == null)
                        newTable[j | nextHighBit] = n;
                    else
                        broken.next = n;
                    broken = e;
                    highBit = nextHighBit;
                }
            }
            if (broken != null)
                broken.next = null;
        }
        // 至此扩容结果
        return newTable;
    }

4,删除逻辑,看完上面的逻辑,这里就比较简单了

    public V remove(Object key) {
        if (key == null) {
            return removeNullKey();
        }
        //计算secondaryHash
        int hash = secondaryHash(key);
        HashMapEntry<K, V>[] tab = table;
        //计算存储的下标位置
        int index = hash & (tab.length - 1);
        // 查找链表是否存在,若存在,进行删除操作。
        for (HashMapEntry<K, V> e = tab[index], prev = null;
             e != null; prev = e, e = e.next) {
            if (e.hash == hash && key.equals(e.key)) {
                if (prev == null) {
                    tab[index] = e.next;
                } else {
                    prev.next = e.next;
                }
                modCount++;
                size--;
                postRemove(e);
                // 删除结束
                return e.value;
            }
        }
        // 没有找到此key对应的数据,删除失败
        return null;
    }

5,查,跟删除逻辑类似

    public V get(Object key) {
        if (key == null) {
            HashMapEntry<K, V> e = entryForNullKey;
            return e == null ? null : e.value;
        }

        // Doug Lea's supplemental secondaryHash function (inlined).
        // Replace with Collections.secondaryHash when the VM is fast enough (http://b/8290590).
        // 这里为什么不用secondaryHash方法,而是把方法里的逻辑摘出来写到这里?为了提高查询效率?
        int hash = key.hashCode();
        hash ^= (hash >>> 20) ^ (hash >>> 12);
        hash ^= (hash >>> 7) ^ (hash >>> 4);

        HashMapEntry<K, V>[] tab = table;
        for (HashMapEntry<K, V> e = tab[hash & (tab.length - 1)];
             e != null; e = e.next) {
            K eKey = e.key;
            if (eKey == key || (e.hash == hash && key.equals(eKey))) {
                return e.value;
            }
        }
        return null;
    }

读完以上逻辑,回答开篇的问题:
1),HashMap内部存储格式是什么样式的?
答:HashMapEntry[]数组的形式,每个数组里的item-HashMapEntry,是链表的数据结构
2),HashMap扩容策略是什么?
答:size达到当前数组大小的3/4时开始扩容,每次扩容2倍大小
3),HashMap增删改查是如何实现的?
如以上代码示例。
4),为什么使用HashMap,优劣势?
增:插入效率一般,比数组慢很多,比链表快
删:比数组快很多,跟链表一致
改:跟数组和链表都一致
查:在数据落到数组上的位置比较均匀的条件下,比链表快很多
若数据都落在同一个index时,hashmap退化为链表。
应该是比没有排序的数组效率也快很多。
总结后发现,HashMap是插入效率一般,但是查找效率极高的数据结构。

本文地址:https://blog.csdn.net/Railshiqian/article/details/107348836