16、0.75、64、8、6 五个参数带你解决HashMap(JDK1.8)在jdk1.8以后，HashMap采用的是数

众所周知，想要学会并理解一个结构，就需要从它的源码进行入手，读源码的过程，是辣么的痛苦，所以！！今天，我将用16、0.75、64、8、6这五个参数带大家玩转HashMap。

首先，先来看这五个参数分别代表什么

//HashMap数组默认长度 16
	static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16
//数组的最大容量
    static final int MAXIMUM_CAPACITY = 1 << 30;
//hashMap的负载因子，默认为0.75
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
//树形化的阈值 为8
    static final int TREEIFY_THRESHOLD = 8;
//解除树形化的阈值 6
    static final int UNTREEIFY_THRESHOLD = 6;
//树形化的另一个条件，就是Map数组的长度阈值为64,当数组长度小于这个值的时候，就算上面
//的树形化阈值达标，链表也不会转化为红黑树，而是优先扩容数组resize()
    static final int MIN_TREEIFY_CAPACITY = 64;
// 数组扩容阈值。
int threshold

为什么会有树形化阈值这么一说呢？在jdk1.8以后，HashMap采用的是数组+链表+红黑树的方式来构造其存储结构，但并不是一开始就有红黑树的结构介入，而是在当数组长度达到64和链表的长度达到8的时候，就会将链表转换为红黑树（红黑树的查询效率更高）的方式进行存储。

对于数组扩容阈值，我们会在构造方法和resize()方法中再见到，到时我们再细说

HashMap的内部结构

 static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

从上面的代码我们不难看出：

1. HashMap的内部数组是Node(节点)的类型，也就是说HashMap中存储的就是一个一个以Key和Value构建成的Entry。
2. 每个Node节点由本身的hash值，key值，value值 和next指针构成

HashMap的构造方法

HashMap的构造方法，主要是分为三个,主要的目的是对对应的参数进行初始化：

1. 没有指定的初始化数组大小和负载因子

构建一个空的HashMap,会有默认的数组大小(16)和默认的负载因子(0.75)

1. 有指定的初始化数组容量，但没指定的负载因子

会传指定的初始化容量和默认的负载因子，通过this（）调用另外的构造方法进行初始化

1. 有指定的初始化容量和负载因子

第二和第三种情况，都是走这一个构造方法进行参数的初始化

static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

tableSizeFor这个方法是用来返回的是第一个大于目标容量的2次幂的大小,所以在指定好容量的时候，就会在构造时将对应的threshold大小计算出来。如果没有指定的话，我们会在resize()方法中见到其计算的方式。

讨论完对应的构造方法以后，我们进行添加元素和扩容的篇章。对应的五个参数，在下面两个方法种也会逐渐的出场...

HashMap.put(K,V)

在看put方法的源码之前，我们不妨先来了解一下bucket（桶）的概念

HashMap中采用hash算法来决定集合中元素的存储位置，每当系统初始化HashMap的时候就会创建一个长度为capacity的数组，这个数组里面可以存储元素的位置被称为桶(bucket)，每个bucket都有对应的索引，可以通过该索引快速定位到元素

public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

所以当每个key和value传进来的时候，都会通过hash计算得到其对应的存储桶的位置。同时，我们也可以看到HashMap中对于key为null值的处理。

对于putVal()方法，我们从4个部分入手，分别是：

1.入参

/**
 * Implements Map.put and related methods.
 *
 * @param hash 上面通过hash计算出来的值(索引值)
 * @param key 传进来的key值，用于对后面key的值的比对
 * @param value 传进来的value值
 * @param onlyIfAbsent 如果为真，代表不改变原来的value值
 * @param evict 如果为false，表处于创建模式。
 * @return previous value, or null if none
 */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
               .....
}

1. 对于处于数组中节点的处理

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
Node<K,V>[] tab; 
//辅助节点，用于表示当前与新节点比对的节点
Node<K,V> p; 
int n, i;
//判断当前数组是否为空，长度是否为0
if ((tab = table) == null || (n = tab.length) == 0)
    //是的话，调用resize()方法进行初始化
    n = (tab = resize()).length;
 //判断经过hash计算后对应索引的位置是否为空，如果为空，那么就新建一个节点存放在数组当中
if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);
else {
 //如果索引位不为空
    //分为三种处理方式：
        //1.key值相同，取代
    Node<K,V> e; K k;
    if (p.hash == hash &&
        ((k = p.key) == key || (key != null && key.equals(k))))
        e = p;
        //2.当前节点存放的是红黑树
    else if (p instanceof TreeNode)
        e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        //3.遍历链表节点，发生hash碰撞，采用拉链法解决
   else {
   ....
   }

1. 对于处于链表中节点的处理

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
               .....
 //3.遍历链表节点，发生hash碰撞，采用拉链法解决              
else {
        //遍历链表
        for (int binCount = 0; ; ++binCount) {
              //如果当前的节点的next指针为空，那么直接将当前节点的next指针指向对应的节点
              //再将新增的节点置为空
            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的值相同，则跳出循环
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                break;
            //相当于 p=p.next；
            p = e;
        }
    }
    //循环结束，判断新增节点是否为空 
    //1. 不为空，代表存在key值相同的状况，对值进行取代
    //2.为空，代表已经加到数组或者链表中或者红黑树中去了
    if (e != null) { // existing mapping for key
        V oldValue = e.value;
        if (!onlyIfAbsent || oldValue == null)
            e.value = value;
        afterNodeAccess(e);
        return oldValue;
    }
}
// fail-fast机制（待我学成归来在阐述..）
++modCount;
//判断添加完成的长度是否大于数组阈值，是的话进行数组的扩容....
if (++size > threshold)
    resize();
afterNodeInsertion(evict);
return null;

补充一下链表转为红黑树的判断

final void treeifyBin(Node<K,V>[] tab, int hash) {
        int n, index; Node<K,V> e;
     //如果当前数组容量太小(小于64)，放弃转换，扩充数组
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize();
            //转为红黑树
        else if ((e = tab[index = (n - 1) & hash]) != null) {
            .....
        }
    } 

到这里，相信大家也都对HashMap有所了解了，但对putVal()方法唯一存在的疑惑可能就是resize()方法这个扩容到底是怎样的勒，包括调用put方法，如果数组为空，也是调用resize()方法初始化。那么接下来，我们再走进resize()方法

HashMap.resize()

resize()方法，我认为可以分为两个阶段：

1. 确认新数组的长度

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    //如果旧数组长度>0
    if (oldCap > 0) {
        //超过了最大的容量，则将当前容量设置为最大值并直接返回
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        //如果旧数组长度*2以后小于最大容量并且旧数组长度>=默认的数组长度
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
                 //数组扩容阈值扩容为两倍
            newThr = oldThr << 1; // double threshold
    }
    //如果旧阈值大于0，也就是上面提到的构造方法中二、三种情况，那么新的容量就会等于阈值
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
        //如果旧阈值为0，对应无参构造方法
    else {
        //那么数组就会是默认长度（16），阈值为16*0.75=12
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    //可能是上面newThr = oldThr << 1 最高位被移除了，变为0
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    //将阈值赋值给threshold
    threshold = newThr;
    .....

1. 进行旧数据的迁移

final Node<K,V>[] resize() {
    ....
    @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;
                   //并且没有链表
                if (e.next == null)
                    //将当前节点放置新数组节点位置
                    newTab[e.hash & (newCap - 1)] = e;
                    //如果是红黑树节点，那就执行红黑树的重新计算
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    //存在链表，遍历链表
                else { // preserve order
                    //低位链表
                    Node<K,V> loHead = null, loTail = null;
                    //高位链表
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        //通过这个位置判断节点存放的位置，如果e.hash&oldCap ==0，那就在新数组的原索引位置
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        //如果e.hash&oldCap!=0，那就在新数组的旧容量+原索引位置
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    //处理尾节点，防止成环
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                     //处理尾节点，防止成环
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

resize()方法小结：通过对于旧数组长度和旧阈值的判断，来获取新的数组长度和阈值，在执行扩容后的rehash的计算，通过源码可知，会是一个数组索引下，一条链表会变为两条链表，两条链表的索引相差一个旧数组长度。

下一篇，待我学成归来我们拿下concurrentHashMap！！下周见