hashMap get put resize方法源码解析

hashMap get put resize方法源码解析

hashMap源码学习

简单介绍一下hashMap，hashMap的顶级父类接口为Map为key-value存贮，在在根据key查找单个元素时时间复杂度为ON（1），但是不能保证元素顺序，即元素存进去和取出来的顺序不一致，在jdk1.7采用数组+链表实现线程不安全，但是在大量存贮元素时可能会出现某种极端情况，链表过长(或元素全部存贮到一条链表上)，查找元素变慢；在jdk1.8时为了解决这个问题，hashMap底层使用了数组+链表+红黑树的方式实现，当链表元素过长时jdk将会把链表转化为红黑树来增加查找速率，但1.8的hashMap仍然不是线程安全的。
为什么jdk1.8采用红黑树而不采用其他的树：
而二叉树在有种极端情况，所有元素全部存储到树的一边上，这样的话树在查找某个元素时就和链表类似，没有体现出树的优势，而二叉树是一种平衡二叉树，树的左右子树高度相差不超过一，超过时通过左旋或右旋调整。
参考https://juejin.cn/post/6844903519632228365#comment
下面我们来看一下具体jdk1.8底层是怎么实现的：
静态变量
静态变量来定制hashMpa中一些规范如：初始容量、扩容阈值等

1.     /**
2.      * The default initial capacity - MUST be a power of two.
3.      * 默认初始容量-必须是2的幂。
4.      * 初始容量
5.      */
6.     static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
8.     /**
9.      * The maximum capacity, used if a higher value is implicitly specified
10.      * by either of the constructors with arguments.
11.      * MUST be a power of two <= 1<<30.
12.      * 如果隐式指定了更高的值，则使用最大容量由带有参数的构造函数之一执行。
13.      * 必须是2的幂<=1<<30。
14.      * HashMap的最大容量
15.      */
16.     static final int MAXIMUM_CAPACITY = 1 << 30;
18.     /**
19.      * The load factor used when none specified in constructor.
20.      * 构造函数中未指定时使用的负载系数
21.      * 容量到达容器的0.75时HashMap将会进行扩容操作
22.      */
23.     static final float DEFAULT_LOAD_FACTOR = 0.75f;
25.     /**
26.      * The bin count threshold for using a tree rather than list for a
27.      * bin.  Bins are converted to trees when adding an element to a
28.      * bin with at least this many nodes. The value must be greater
29.      * than 2 and should be at least 8 to mesh with assumptions in
30.      * tree removal about conversion back to plain bins upon
31.      * shrinkage.
32.      * 对于bin使用树而不是列表的bin计数阈值。将元素添加到具有至少这么多节点的bin时，
33.      * bin将转换为树。该值必须大于2，并且至少应为8，
34.      * 以便与树木移除中关于收缩时转换回普通箱的假设相匹配
35.      *
36.      * 当链表长度超过8时HashMap会将链表转换为红黑树
37.      * HashMap会优先将数组扩容到64时才会进行红黑树的转化
38.      */
39.     static final int TREEIFY_THRESHOLD = 8;
41.     /**
42.      * The bin count threshold for untreeifying a (split) bin during a
43.      * resize operation. Should be less than TREEIFY_THRESHOLD, and at
44.      * most 6 to mesh with shrinkage detection under removal.
45.      * 在调整大小操作过程中取消筛选（拆分）垃圾箱的垃圾箱计数阈值。
46.      * 应小于TREEIFY_THRESHOLD，最多为6，以便在移除时进行收缩检测
47.      *
48.      */
49.     static final int UNTREEIFY_THRESHOLD = 6;
51.     /**
52.      * The smallest table capacity for which bins may be treeified.
53.      * (Otherwise the table is resized if too many nodes in a bin.)
54.      * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
55.      * between resizing and treeification thresholds.
56.          * 可将箱子树化的最小工作台容量。
57.          *（否则，如果bin中的节点过多，将调整表的大小。）
58.          * 应至少为4*TREEIFY_THRESHOLD以避免冲突
59.          * 在调整大小和树化阈值之间。
60.          *
61.          * 当数组长度到达64时且链表长度大于等于8时链表转换为红黑树
62.      */
63.     static final int MIN_TREEIFY_CAPACITY = 64;

复制代码

get相关方法和属性

1.         //初始无参构造
2.         //Constructs an empty HashMap with the default initial capacity (16) and the default load factor (0.75).
3.         //使用默认初始容量（16）和默认负载因子（0.75）构建一个空的HashMap
4.     public HashMap() {
5.         this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
6.     }
10.     /**
11.      * Constructs an empty <tt>HashMap</tt> with the specified initial
12.      * capacity and the default load factor (0.75).
13.      *
14.      * @param  initialCapacity the initial capacity.
15.      * @throws IllegalArgumentException if the initial capacity is negative.
16.      */
17.         //使用指定的初始容量和默认负载因子（0.75）构造空HashMap。
18.         //参数: initialCapacity–初始容量。
19.         //抛出: IllegalArgumentException–如果初始容量为负数
20.         //构造一个含有初始容量的HashMap
21.     public HashMap(int initialCapacity) {
22.         this(initialCapacity, DEFAULT_LOAD_FACTOR);
23.     }
26.     /**
27.      * Constructs an empty <tt>HashMap</tt> with the specified initial
28.      * capacity and load factor.
29.      *
30.      * @param  initialCapacity the initial capacity 初始化容量
31.      * @param  loadFactor      the load factor      负载因子
32.      * @throws IllegalArgumentException if the initial capacity is negative
33.      *         or the load factor is nonpositive
34.      */
35.         //使用外部传入的HashMap的初始化容量和负载因子
36.     public HashMap(int initialCapacity, float loadFactor) {
37.         if (initialCapacity < 0) //判断外部传入的初始化容量是否小于0，小于0则抛出异常
38.             throw new IllegalArgumentException("Illegal initial capacity: " +
39.                                                initialCapacity);
40.         if (initialCapacity > MAXIMUM_CAPACITY) //判断初始化容量是否超过最大容量
41.             initialCapacity = MAXIMUM_CAPACITY; //如果大于最大容量则使用最大容量
42.         if (loadFactor <= 0 || Float.isNaN(loadFactor)) //判断负载因子是否小于0或者不是数字
43.             throw new IllegalArgumentException("Illegal load factor: " +
44.                                                loadFactor); //抛出异常
45.         this.loadFactor = loadFactor;                                 //负载因子赋值
46.         this.threshold = tableSizeFor(initialCapacity); //将初始化容量先赋给容器界限
47.     }
48.        
49.         //Returns a power of two size for the given target capacity.
50.         //返回给定目标容量的两次幂。
51.         //得到一个大于获等于他的2的幂并返回
52.         static final int tableSizeFor(int cap) {
53.         // >>>为无符号右移 将数字转换为二进制向右移动 高位补0
54.         // |为或运算，两个数转化为二进制，有1则为1，全0则为0
55.         // |= 与+=类似 a|=b 等价于 a=a|b
56.         
57.         //防止传进来的数本身就是2^n,如果不减一则传出的值为2^n+1
58.         int n = cap - 1;
59.         //右移一位并与自己进行或运算，则原来是1则变成11。
60.         //例如传进来数为100001001，右移一位得到0110000100，与自己进行或运算得到110001101
61.         //一位1变成两位1，所以下面各右移1、2、4、8、16位
62.         n |= n >>> 1;
63.         n |= n >>> 2;
64.         n |= n >>> 4;
65.         n |= n >>> 8;
66.         n |= n >>> 16;
67.         return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
68.     }
69.        

复制代码

put添加相关方法和属性
[code]    /**     * Associates the specified value with the specified key in this map.     * If the map previously contained a mapping for the key, the old     * value is replaced.     *     * @param key key with which the specified value is to be associated     * @param value value to be associated with the specified key     * @return the previous value associated with key, or     *         null if there was no mapping for key.     *         (A null return can also indicate that the map     *         previously associated null with key.)     */        //将指定值与此映射中的指定键相关联。如果映射之前包含键的映射，则替换旧值。         //参数: key–与指定值关联的键 value–与指定键关联的值         //返回值: 与键关联的前一个值，如果没有键的映射，则为null。（null返回还可以指示映射先前将null与键关联。）    public V put(K key, V value) {        return putVal(hash(key), key, value, false, true);    }    /**     * Implements Map.put and related methods.     *     * @param hash hash for key     * @param key the key     * @param value the value to put     * @param onlyIfAbsent if true, don't change existing value     * @param evict if false, the table is in creation mode.     * @return previous value, or null if none     */        //实施映射。put和相关方法。         //参数: hash–密钥的哈希 key–钥匙 value–要放置的值 onlyIfAbsent–如果为true，则不更改现有值 evict-如果为false，则表处于创建模式。         //返回值: 上一个值，如果没有则为null    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,                   boolean evict) {        Node[] tab; Node p; int n, i;        //检查HashMap中是否为空,为空则使用resize初始化，并给n赋值        if ((tab = table) == null || (n = tab.length) == 0)            n = (tab = resize()).length;        //检查数组下标处是否为空，是则直接赋值（(n - 1) & hash 为下标）        if ((p = tab[i = (n - 1) & hash]) == null)            tab = newNode(hash, key, value, null);        else {            Node e; K k;            //检查数组下标处key是否与新值重复，是则e的值为 key            if (p.hash == hash &&                ((k = p.key) == key || (key != null && key.equals(k))))                e = p;            //检查是否是红黑树，是则使用红黑树插入，否则链表插入            else if (p instanceof TreeNode)                //红黑树不了解                e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);            else {                // 循环遍历链表，如果找到相同key则替换，没有找到则插入到链表最后并检查是否超过8，是则将链表转化为红黑树                for (int binCount = 0; ; ++binCount) {                    // 检查p是否为最后一个元素，此时结束循环e为 null                    if ((e = p.next) == null) {                        //新元素尾插到末尾                        p.next = newNode(hash, key, value, null);                        //检查链表长度是否超过八，是则转化为红黑树，                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st                            //构造树的具体方法                            treeifyBin(tab, hash);                        break;                    }                    // 检查元素是否与新元素相同，是则退出循环，此时结束循环e值为 key                    if (e.hash == hash &&                        ((k = e.key) == key || (key != null && key.equals(k))))                        break;                    p = e;                }            }            // 这句话的意思其实是判断上面的循环走完了吗？如果走完链表则e应该是null，如果e不为空则表示新值还没有被替换，再这里替换            if (e != null) { // existing mapping for key                // 将e的值赋给oldValue做中转                V oldValue = e.value;                       // 判断条件是 是否改变现有值 新值是否为null                if (!onlyIfAbsent || oldValue == null)                    e.value = value;                afterNodeAccess(e);                // 返回替换前的值                return oldValue;            }        }        ++modCount;        // 判断是否到达扩容界限 threshold = 容量 * 负载因子（默认0.75）        if (++size > threshold)            // 扩容            resize();        afterNodeInsertion(evict);        return null;    }    /**     * Initializes or doubles table size.  If null, allocates in     * accord with initial capacity target held in field threshold.     * Otherwise, because we are using power-of-two expansion, the     * elements from each bin must either stay at same index, or move     * with a power of two offset in the new table.     *     * @return the table     */        //初始化或加倍表大小。如果为空，则根据字段阈值中保持的初始容量目标进行分配。        //因为我们使用的是二次幂展开，所以每个bin中的元素必须保持在同一索引中，或者在新表中以二次幂偏移量移动。        //返回值: table        //HashMpa的扩容方法        final Node[] resize() {                Node[] oldTab = table;        // 判断HahsMap是否为空给oldCap（旧容量）赋值        int oldCap = (oldTab == null) ? 0 : oldTab.length;        // 旧的容量界限        int oldThr = threshold;        // 新的容量和新的容量界限        int newCap, newThr = 0;        // 判断是否HashMap第一次初始化        if (oldCap > 0) {            // 判断旧容量是否大于等于最大，是则提升界限，并将容器直接返回            if (oldCap >= MAXIMUM_CAPACITY) {                // 将界限提升到2的31次方 - 1                 threshold = Integer.MAX_VALUE;                // 返回原容器                return oldTab;            }            //判断旧容量扩大2倍后是否超过最大容量，判断旧容量界限是否大于等于初始容量（保证不是第一次初始化容器）            //