主要静态变量

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
static final float DEFAULT_LOAD_FACTOR = 0.75f;
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;

• DEFAULT_INITIAL_CAPACITY 默认的初始化容量，即16；
• DEFAULT_LOAD_FACTOR 默认的负载因子
• TREEIFY_THRESHOLD 当一个槽(或叫bin、buket)的链表长度到达改阈值时，是将链表转换为红黑树的一个必要条件，注意只是一个必要条件，并不是充分条件，后面马上就会说明原因。
• UNTREEIFY_THRESHOLD 当一个槽数据退化到该阈值时，红黑树将退化成链表；
• MIN_TREEIFY_CAPACITY 当容量小于该值时，即使链表长度到达TREEIFY_THRESHOLD 也不会转换红黑树，而是通过resize()的方式进行扩容。所以别再说当链表长度大于8时就会转换红黑树了，这个条件不具备的情况下是不会转换的，具体代码在treeifyBin()方法中，下面也会讲到。

这里说一个反常识，可能是因为八股文背得多了，大家对HashMap链表转红黑树慢慢的认为是一个很容易发生的情况，但是从源码中我们其实可以看到官方的一些理论数据如下，可见正常情况下一个HashMap中出现红黑树的可能性是非常低的。

* Ideally, under random hashCodes, the frequency of
* nodes in bins follows a Poisson distribution
* (http://en.wikipedia.org/wiki/Poisson_distribution) with a
* parameter of about 0.5 on average for the default resizing
* threshold of 0.75, although with a large variance because of
* resizing granularity. Ignoring variance, the expected
* occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
* factorial(k)). The first values are:
*
* 0:    0.60653066
* 1:    0.30326533
* 2:    0.07581633
* 3:    0.01263606
* 4:    0.00157952
* 5:    0.00015795
* 6:    0.00001316
* 7:    0.00000094
* 8:    0.00000006
* more: less than 1 in ten million

HashMap的构造方法

    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); //这个方法也很有意思，后面会讲
    }
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

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

    public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }

这里值得注意的是，在构造方法中，除最后一个构造方法外，其他构造方法中并没有真的去初始化我们熟悉的链桶结构。

那什么时候初始化的呢？其实是在put()数据时才会触发真正的初始化，这里我理解为一种延迟初始化的策略。

还有一个常见的说法是在能够明确集合大概容量的情况下推荐使用HashMap(int initialCapacity)的方式进行构造，原因主要是这样减少了因为容量增长导致的resize()操作。

这里留个思考题，对于HashMap(int initialCapacity, float loadFactor)这种初始化方法，为什么this.threshold = tableSizeFor(initialCapacity);而不是this.threshold = initialCapacity * loadFactor呢？

关于Hash()

HashMap的hash方法比较有意思，也能引一些代码细节上的思考。

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

为什么需要(h = key.hashCode()) ^ (h >>> 16) 即 将key的hashcode的前16位与后16位进行异或操作。

在说原因之前我们看下这个hash值的使用场景一般是在计算一个key/value应该落在table[]的哪个槽里，会对key进行hash(key)操作，得到一个hash值，而槽的index的计算方式一般是(n - 1) & hash这里n 一般为2的整数次方，所以n-1的二级制一般是都是1，如8-1的二进制是111，16-1=binary:1111，所以(n-1)&hash肯定是小于等于n-1的，所以当hash满足随机性，其计算出来的index也具备随机性。那为何不直接使用hashCode呢？为啥还要多此一举搞一个异或呢？

这是因为通常情况下n的值不会特别大，这种计算方式往往只能与hash的后几位进行运算，这样就可能出现一些高位不同，地位相同的hash值计算出同一个结果，导致冲突概率增加。

所以回过来看一下(h = key.hashCode()) ^ (h >>> 16) 就能够理解一些了，将高位16位与低16位进行异或，让高位的随机性影响到地位，从而达到让冲突的概率更低的效果。

是不是很巧妙。

tableSizeFor(int cap)

这个方法也比较有意思，逼格满满

    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;
    }

作用就是返回大于等于cap的最小的2的整次幂，例如tableSizeFor(16)=16、tableSizeFor(17)=32 、tableSizeFor(15)=16

首先，>>>代表什么呢？

操作符>>>表示无符号右移，也叫逻辑右移，即若该数为正，则高位补0,即2的二进制位10，2>>>1 = 01

大概说一下代码思路吧，

假设我有一个数字n，不管怎样都可以转换成一个32位的二进制，高位补0

试想一下n |= n >>> 1做了什么呢，首先只要n>0 ，最前面一定是个1，高位补0，这个时候n |= n >>> 1至少能保证第一个为1的位置，且第二位也为1，因为1或上任何数都为1。

假设数字n为0000001XXXXXXXX，前面的0表示高位补0，X表示的位置可能为0或1

n>>>1 为00000001XXXXXXX 则n |= n >>> 1 后为00000011XXXXXXX

这样看明显一点
    n      0000001XXXXXXXX
    n>>>1  00000001XXXXXXX 
    |      00000011XXXXXXX 

这个操作后能保证的是第一个为1的位置与其后1个位置肯定都为1，这样就能保证至少有2个1。

然后>>>2 就出现4个1，然后依次4、8、16.最终保证32位全覆盖。
举一个极端的例子：

假设初始是1000000000000000000000000000000
其依次转换过程为：
from 1000000000000000000000000000000 to 1100000000000000000000000000000
from 1100000000000000000000000000000 to 1111000000000000000000000000000
from 1111000000000000000000000000000 to 1111111100000000000000000000000
from 1111111100000000000000000000000 to 1111111111111111000000000000000
from 1111111111111111000000000000000 to 1111111111111111111111111111111

get & getNode

   public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }


    final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) { //通过(n - 1) & hash方式定位到数据槽下标index
            if (first.hash == hash && 
                ((k = first.key) == key || (key != null && key.equals(k))))
                // 如果恰好是第一个节点就直接返回
                return first;
            if ((e = first.next) != null) {
                //判断当前是链表结构还是红黑树结构
                if (first instanceof TreeNode)
                    //使用tree的方法进行查找
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {
                    //遍历链表
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

大致思路就是先通过tab[(n - 1) & hash]定位到数据槽，然后根据数据槽中的first对象进行判断，如果是树节点则调用getTreeNode方法进行查找，否则说明是链表，遍历即可。经常咱们面试的时候会被问到多线程情况下hashMap不安全的表现是啥，说resize()导致死循环的基本都是看帖子的，其实hashMap在多线程的情况下可能出现的问题多了去了。假设在遍历链表的时候，因为多个线程操作导致hashMap进行了resize()操作会发生什么情况？或者在定位到槽之后，取first之前resize()了会导致什么？大家可以发散下思维，可以说出很多不安全导致的后果。

put & putVal

    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; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length; //上文提到的在new HashMap的时候不会真实初始化
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {//尾插法，老版本的hashMap是头插法
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) 
                            treeifyBin(tab, hash);//到达阈值后，判断是否需要进行红黑树转换（也可能是resize())
                        break;
                    }
                    // 若找到相同key，则取出，后面进行值的替换即可
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { //如果存在，则替换原值，并将原值返回
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);//此处为一个扩展点，后续提到
                return oldValue;
            }
        }
        ++modCount;//每次对数据的变动都会导致modeCount变化，这也是我们有时候在边遍历边修改map的时候遇到ConcurrentModificationException的原因
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);//此处为一个扩展点，后续提到
        return null;
    }

归纳几点：

• putVal中会对空的HashMap进行初始化
• 数据采用的是尾插法，老版本的HashMap是头插法
• 插入时会进行长度判断，如果到达阈值会进入treeifyBin()的逻辑
• 当发现有相同key的情况下，直接替换对应Node的value
• 当有相同key的情况下，put方法返回原值，否则为null
• 有两个扩展点，分别是afterNodeAccess(e) 和 afterNodeInsertion(evict); 这个能够再HashMap的基础上扩展出LinkedHashMap的关键。

resize()

final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) {
            if (oldCap >= MAXIMUM_CAPACITY) { //已经最大了，不能再扩容了，把阈值调高防止再次进入resize()
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // 还可以扩容，直接*2
        }
        else if (oldThr > 0) //对于HashMap(int initialCapacity, float loadFactor)这种模式，在这块保证初始化的newCap为2的倍数
            newCap = oldThr;
        else {               //初始化
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr == 0) {
            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) {
            //遍历table的每个槽去初始化
            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的方法进行重塑
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { //链表形式
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            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()逻辑

                        Node<K,V> loHead = null, loTail = null; //低位槽链表的头结点和尾节点
                        Node<K,V> hiHead = null, hiTail = null; //高位槽链表的头结点和尾节点
                        Node<K,V> next;
                        do {
                            next = e.next;
                            if ((e.hash & oldCap) == 0) { //判断是否该节点应该放到高位槽还是低位槽
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            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;// 下面会解释j + oldCap的含义
                        }

首先，来解释下什么是高位槽什么是低位槽。

我们知道resize()是将原table的长度n个长度的数组扩容成n*2 (这里明确一个事实，n一定是2的倍数，大家可以自行去验证这个事实)

我们现在换一个问题，假设一个槽里目前是链表，当table的长度从n变成了n*2会出现什么情况呢？

答案是，链表中所有元素都会被划分到2个槽里，

现在假设table长度为n，扩容后为n*2 假设这个链表所在的槽的下标是k，

我们知道hash的算法是 hash &(n-1) ，那么问题来了，当n*2后再计算的时候结果是什么样呢？

先举个例子，假设n=4 有0、1、2、3三个槽，此时hash为1,5,9,13,17,21都在这个槽里

现在n=n*2 再计算hash发现，1,5,9,13,17,21中1,9,17仍然在槽[1]中，而5,13,21则在槽[5]中，这样我们就有了高位槽和低位槽的说法。

高位槽指的是槽[5]，低位槽是槽[1]，而槽间距是4，刚好等于n。

下面我们从原理分析一下：

首先对于原有n，其hash & (n-1) 本质上是 哈希值x & 11...111 而resize()之后是哈希值x & 111...111

我们对齐看下假设n的二进制表达式010000，则hash & (n-1)扩容前后的表达式为
x & 0000011...111
x & 0000111...111
举个例子
x & 001111
x & 011111
当x的二进制的第二位为0时，这两个表达式计算出的结果肯定是一样的，
而当x二进制的第二位为1时，这两个计算的结果才是不一样的，而且差的其实是010000,即=n

于是我们回来看代码中判断放在低位槽还是高位槽的算法是：

if ((e.hash & oldCap) == 0) 

就很明确了吧。

对新槽的下标也很容易理解了

newTab[j + oldCap] = hiHead;