HashMap的put方法(笔记)

先看一下HashMap中几个重要的变量

• DEFAULT_INITIAL_CAPACITY : Map默认的容量,1<<4(左移四位,二进制 10000 ,十进制表示16)

• MAXIMUM_CAPACITY : Map的最大的容量, 1<<30 (2^30超大的一个值)

• DEFAULT_LOAD_FACTOR : 负载因子(加载因子),默认是 0.75

• transient Node<K,V>[] table : Node类型的数组,底层最主要的数组

• transient int size; 集合中元素的个数

• int threshold; 临界值、阀值; 他的作用就是当元素的个数超过它时就去扩大集合的容量

• final float loadFactor 这个也是负载因子,源码中真正操作的是这个属性,这里并没有赋值

看源码前先了解一下HashMap的结构图

HasMap结构图.png

构造方法

在 JDK1.7 与 JDK1.8 中两个构造方法是不一样的,

1.7中的空构造函数

在此版本中,调用空构造的时候会进行一些重要的初始化,比如设置默认的容量和负载因子

    public HashMap() {
        //这两个值分别是默认的16和0.75
        //this(16, 0.75)
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
    }
  //由于我是1.8版本的,所以下面这个方法并不是1.7的内容,但是方法是同一个,内容有些差别
    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;
        this.threshold = tableSizeFor(initialCapacity);
    }

1.8中的构造函数

在1.8中的空构造并没有像上面那样调用另一个构造,这里只是初始化了负载因子的值

    public HashMap() {
        //设置0.75
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

先看一下 put() 方法,详细的都写在putVal方法注释了
put 方法中会调用到 hash() 方法,这个方法比之前的要简单一点了,还记得之前要进行好几步的运算就是为了 减少哈希碰撞 简而言之就是为了让算出来的值尽量不一样
现在这个没有之前那么复杂了,主要是因为用到了红黑树处理二进制中大量的冲突,以一种简单的方式进行位运算、异或运算,为得就是减少系统的开销

    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        //总的数组
        Node<K,V>[] tab;
        //数组的第一个元素（链表的第一个元素）
        Node<K,V> p;
        //n 是 数组tab(或者是table)的长度，i 是index,表示数组的下标
        int n, i;
        //将数组 table 赋给 tab
        if ((tab = table) == null || (n = tab.length) == 0){
            //resize()方法重新设置table的长度并返回table对象
            n = (tab = resize()).length;
        }
        //如果数组中 table[(n - 1) & hash] 这个位置上是null ,直接放到数组上,这是链表的第一个元素
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            //说明些index上有数据(链表结构或者是红黑树结构)
            Node<K,V> e; K k;
            //判断hash值是否相等并且key是否相等
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                //将链表中的元素赋给e,(下面会使用put进来的value去覆盖),为的是处理key值相同的情况
                //具体的是否覆盖需要看onlyIfAbsent这个参数,普通的put方法是覆盖的,putIfAbsent方法不覆盖
                e = p;
            else if (p instanceof TreeNode)//判断是否已经是树型结构,TreeNode就是红黑树的模型
                e = ((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;
                }
            }
            //处理key相同的情况
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
              //onlyIfAbsent 判断是否覆盖老的value
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        //这里 threshold 是数组容量的75% 大小,会在第一次put时在resize()方法中进行初始化
        //size 是数组的总容量
        if (++size > threshold){
            //达到数组总大小的75%时会进行扩容
            resize();
        }
        afterNodeInsertion(evict);
        return null;
    }

get()方法的逻辑与put()很相似,这里就不写了,
resize()是对table数组进行扩容,然后将老的数组释放,(赋值null)

final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        //值为 数组总大小 * 0.75
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) {
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            // 以指2的倍数增加(8->16->32->64)
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr == 0) {//第一次put 时会执行到这(JDK1.8)
            //临界值。总大小的75%
            float ft = (float)newCap * loadFactor;
            
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        // 对老数组释放
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    ...省略代码
                }
            }
        }
        return newTab;
    }

完!!!