JDK1.8HashMap源码之成员变量和多种构造函数分析（一）

短命女 2022-11-17 05:29 148阅读 0赞

今天我们进行HashMap 源码开始分析，它是集数组、链表、红黑树的优点于一身的常用数据结构。废话少说，直奔主题。

1、类继承关系：

public class HashMap<K,V> extends AbstractMap<K,V> i
            mplements Map<K,V>, Cloneable, Serializable

如图：

![70][]

2、成员变量：

private static final long serialVersionUID = 362498820763181265L;
    
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;//默认容量大小
    
    /**
     *  
     * int类型是32位整型，占4个字节。
     * Java的原始类型里没有无符号类型。 -->所以首位是符号位 正数为0，负数为1
     * java中存放的是补码，1左移31位的为 16进制的0x80000000代表的是-2147483648–>所以最大只能是30
     *
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;//最大容量为2的30次方
    
    static final float DEFAULT_LOAD_FACTOR = 0.75f;//默认的加载因子
    
    static final int TREEIFY_THRESHOLD = 8;// 当桶(bucket)上的结点数大于这个值时会转成红黑树
    
    static final int UNTREEIFY_THRESHOLD = 6;// 当桶(bucket)上的结点数小于这个值时树转链表
    
    /**
     * 桶中结构转化为红黑树对应的table的最小长度，即：当数组的长度大于64并且桶的长度大于8同时满足时，才会触发由链表变为红黑树
     */
    static final int MIN_TREEIFY_CAPACITY = 64;
    
    final float  loadFactor;//负载因子
    
    int threshold;//阈值
    
    transient int modCount;//结构性变化的次数
    
    transient int size;//当前数据量
    
    transient Set<Map.Entry<K,V>> entrySet;//非重集合
    
    transient Node<K,V>[] table;//table也就是所谓的hash桶，数组类型

3、无参构造函数：负载因子是默认值

public HashMap(){
        this.loadFactor = DEFAULT_LOAD_FACTOR;
    }

4、设置自定义容量的构造函数：

/**
     * 初始化集合时设置固定 容量 返回大于或等于指定参数initialCapacity的最小2的整数次幂
     * @param initialCapacity
     */
    public HashMap(int initialCapacity){
        this(initialCapacity,DEFAULT_LOAD_FACTOR);//自定义容量和默认负载因子
    }

点击 this方法：

public HashMap(int initialCapacity,float loadFactor){
        if(initialCapacity < 0){
            throw new IllegalArgumentException("Illegal initial capacity:" + initialCapacity);
        }
        if(initialCapacity > MAXIMUM_CAPACITY){
            initialCapacity = MAXIMUM_CAPACITY;//如果大于最大容量，就设置为最大容量
        }
        if(loadFactor <= 0 || Float.isNaN(loadFactor)){
            throw new IllegalArgumentException("Illegal load factor:" + loadFactor);
        }
        this.loadFactor = loadFactor;//负载因子赋值
        /**
         *返回大于或等于指定参数initialCapacity的最小2的整数次幂
         */
        this.threshold = tableSizeFor(initialCapacity);//计算阈值
    }

点击 tableSizeFor(initialCapacity) 方法：

/**
     * “|”是叫做位或运算
     * >>>表示无符号右移
     * 为什么cap要减一:这样就可以避免当cap已经是2的整数次幂时,再对cap进行一次求次幂操作,比如:cap=16,
     * 如果没有减一结果就会变成32,而16已经符合HashMap的要求了.
     * 为什么要返回n+1?": 二进制是如何转换为十进制的就明白了,即：
     * @param cap
     * @return
     */
    public static int tableSizeFor(int cap) {
        /**
         * 当 5 < cap < 8 时：n = 7
         * 当 9 < cap < 16 时：n = 15
         * 当 17 < cap < 32 时：n = 31
         * 。。。。。。等等
         * 此时返回  return n + 1 就是 2 的整数幂
         * 验证了：返回值大于或等于指定参数initialCapacity的最小2的整数次幂
         */
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 1) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

5、设置带有初始化集合的构造函数：

public HashMap(Map<? extends K,? extends V> m){
    
        this.loadFactor = DEFAULT_LOAD_FACTOR;//默认的加载因子
    
        putMapEntries(m,false);//初始化数据，核心方法
    }

点击 putMapEntries 方法（很多地方都会调用此方法）：

final void putMapEntries(Map<? extends K,? extends V> m, boolean evict) {
        //m的类型参数是? extends，所以只能使用泛型代码的出口，比如get函数
    
        int s = m.size();
        if(s > 0){//传入map的大小不为0
            if(table == null){// 说明是构造函数来调用的putMapEntries方法！！！，或者构造后还没放过任何元素,即：判断table是否已经初始化
    
                /**
                 * 未初始化时，s为m的实际元素个数,使用这个旧的map的size计算出新的
                 * 先不考虑容量必须为2的幂，那么下面括号里会算出来一个容量，使得size刚好不大于阈值。
                 * 但这样会算出小数来，但作为容量就必须向上取整，所以这里要加 1
                 *
                 */
                float ft = ((float)s / loadFactor) + 1.0f;
                //如果小于最大容量，就进行整数截断；否则就赋值为最大容量
                int t = ((ft < (float) MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY);
                /**
                 * 虽然上面一顿操作，但只有在算出来的容量t > 当前暂存的容量(容量可能会暂放到阈值上的)时，
                 * 才会用 t 计算出新容量，再放到阈值上
                 */
                if(t > threshold){
                    threshold = tableSizeFor(t);//核心方法，上面已经分析过
                }
            }else if(s > threshold)
                /**
                 * 说明table已经初始化过了；判断传入map的size是否大于当前map的threshold，如果是，必须要resize
                 * 这种情况属于预先扩大容量，再put元素.
                 * 而且循环里的putVal可能也会触发resize
                 */
                /**
                 * 因此，该条件判断用于向已经实例化了的map里面添加某个map的所有元素
                 * 而且，如果s > threshold，会触发扩容。
                 * 当尝试调用putAll时，该条件才有可能成立，从目前的构造函数源码看，这句似乎是多余的。
                 *
                 */
                resize();//核心方法，在putVal里重点分析（多处会调用）
            /**
             * 循环把m里面的所有元素存入新的map里面，这里调用的是putVal，这个方法在第二篇文章里面就会讲到
             * 有集合参数初始化时也走这里！！！
             */
            for(Map.Entry<? extends K,? extends V> e : m.entrySet() ){
                K key = e.getKey();
                V value = e.getValue();
                /**
                 * 该方法每次插入新元素之后都会对扩容的必要性做判断，因此上面的扩容判断端在我看来没必要。
                 */
                putVal(hash(key),key,value,false,evict);//核心方法，后面重点分析
            }
        }
    }

6、点击  hash(key)方法：

/**
     * 这段代码叫“扰动函数”。
     * 计算key.hashcode（）并将哈希的高位扩展到低位。按照官方的说法，无符号右移是为了让高位参与运算，提高计算的均衡性。
     *
     *  同时这里可以发现，hashMap的key可以为空，并且如果为空时hash值为0，此数据就会放到数组的第一个位置
     *  （即数组下标为0，如果存在hash冲突，就往下放到链表或红黑树中）
     *
     *  可参阅:  https://www.zhihu.com/question/20733617
     */
    public final int hash(Object key){
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

7、点击putVal 方法：

/**
    * @param hash key的hash值
    * @param key the key
    * @param value the value to put
    * @param onlyIfAbsent 如果为 true, 不改变存在的value
    * @param evict 如果为false，则该表处于创建模式.
    * @return 返回前一个值，如果没有，则为空
    */
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0) // table未初始化或者长度为0，进行扩容，此构造函数一定经过这里！！！
            n = (tab = resize()).length;
        /**
         * 计算index，并对null做处理，此构造函数首次存放数据一定经过这里！！！
         *  (n - 1) & hash 确定元素存放在哪个桶中，如果此桶为空，新生成结点放入此桶中(此时，这个结点是放在数组中)
         *  用&与运算代替%运算，提高运算效率，前提是数组长度n需要时2的n次方，长度的确定由上面代码确定。
         */
        if ((p = tab[i = (n - 1) & hash]) == null)//例如：n为16 ,与运算后i = 4,即tab[4]:tab数组下标为4的索引处值(p)为空.
            tab[i] = newNode(hash, key, value, null);//为tab[4] 赋值（单向链表，并且其next值为null）。
        else {// 桶中已经存在元素，此构造函数存放数据时也可能经过这里（初始化的数据多）！！！
            Node<K,V> e; K k;
            //节点key存在，直接覆盖原始的value，此构造函数通常不会走这里，因为初始化的集合中key一般不会重复。
            if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k)))) // 比较桶中第一个元素(数组中的结点)的hash值相等，key相等
                e = p;// 将第一个元素赋值给e，用e来记录;此时p在前面赋值并且不为null
            else if (p instanceof TreeNode)// hash值不相等，即key不相等，并且已经为红黑树结点（即至少已经发生超过8次hash冲突），此构造函数存放数据时也可能经过这里（初始化的数据多）
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); // 放入红黑树中，下面会重点分析。
            else {//该数据为链表（即已经发生至少6次hash冲突）,此构造函数存放数据时也可能经过这里（初始化的数据多）
                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 // 结点数量达到阈值，转化为红黑树
                            treeifyBin(tab, hash);//变为红黑树，下面会重点分析。
                        break;
                    }
                    // 判断链表中结点的key值与插入的元素的key值是否相等
                    if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                        break;// 相等，跳出循环；否则会一直遍历到链表尾部。此时 e = p.next 已经赋值。
                    p = e;// 用于遍历桶中的链表，与前面的 e = p.next组合，可以遍历链表，即作用就是遍历链表时用的。
                }
            }
            if (e != null) { // existing mapping for key; 表示在桶中找到key值、hash值与插入元素相等的结点,此构造函数通常不会走这里
                V oldValue = e.value; // 记录e的原始value
                if (!onlyIfAbsent || oldValue == null)// onlyIfAbsent为false或者旧值为null
                    e.value = value;//用新值替换旧值
                afterNodeAccess(e);// 访问后回调
                return oldValue; // 返回旧值
            }
        }
        ++modCount; // 结构性修改
        //超过阈值就扩容（首次阈值为12 = 16 * 0.75，即首次超过12（即第12次添加时，满足++size > 12）就扩容；如果map初始化时是通过有参构造函数初始化的，并且设置了初始容量，那阈值就很可能不是12了）
        if (++size > threshold)
            resize();// 实际大小大于阈值则扩容，下面会重点分析。
        afterNodeInsertion(evict);// 插入后回调
        return null;
       
    }

另外，有三个不太重要的方法简单提一下：

// Callbacks to allow LinkedHashMap post-actions  允许LinkedHashMap后动作的回调,即三个方法都是为了继承HashMap的LinkedHashMap类服务的。
    void afterNodeAccess(Node<K,V> p) { }
    void afterNodeInsertion(boolean evict) { }
    void afterNodeRemoval(Node<K,V> p) { }

今天分析到此结束，大家一定要详细查看，下篇分析resize()  方法，其比较复杂，会重点详细分析，敬请期待！

[70]: /images/20221022/9d7797f4bfb84a5c9d04d06126f48bed.png