HashMap源码阅读

一. 前言：

在准备面试的过程中，发现HashMap源码是很常见的考点，于是进行了仔细的学习。以前都说读源码是快速提高Java水平的好途径，在阅读了HashMap的部分重要源码之后真的是深有体会，于是写下此篇文章做记录。具体内容包括，HashMap的构造方法，put，get方法，以及put&get所需要的hash方法，还有扩容时所需要的resize方法。我们将对这几个方法的源码进行阅读，理解它的逻辑，以及一些巧妙的设计。

二. HashMap原理：

是基于Map接口的实现，存储键值对时，它可以接收null的键值，是非同步的，HashMap存储着Entry(hash, key, value, next)对象。
常用的方法有：
构造方法，可以定义initialCapacity初始容量，factor负载因子。threshold = initialCapacity * factor
put，get，二者需要用到hash方法，也就是散列函数。
resize：放数组容量不足时，元素个数大于threshold时，就要扩容。
HashMap使用数组链表来存储数据（数组的每一项都是一个链表），JDK1.8开始，当链表的长度到达一定程度，就会把该链表转换成红黑树。

三. ① 构造方法：

构造方法一共有4个：

显然，第一个就是没有参数，此时会设置默认的负载因子factor。
对于第二个，实际上就是将float参数设置为默认的负载因子default_factor。
对于第四个，是传入一个Map对象进行初始化。我们重点看第三个构造方法：

前面的都是判断一下边界值，就省略了。
HashMap有几个关键的成员属性：
initialCapacity：初始容量大小（数组大小，但后面会改变）
factor：负载因子
threshold：initialCapacity * factor（到达这个值的时候，哈希数组会扩容）
（初始化之后，后续用size表示哈希数组里的元素个数，当size超过threshold之后，扩容）
然后我们发现一行关键的代码：

1	this.threshold = tableSizeFor(initialCapacity);

点进入看tableSizeFor的函数逻辑：

可以看到这个方法的目的：returns a power of two size for the given target capacity

也就是说，哈希数组的长度，永远是2的幂次方，至于为什么，请看后面的question1.
关于这个算法的逻辑，用下图可以说明：

连续的n |= n >>> 1, 2, 4, 8, 16，通过这样，最多可以让连续32位为1.不管capacity是多少，比如它是1011，减去1之后是1010，第一个不为0的位是第4位，那么这个算法会返回10000.
（这里的关键是或运算，因为第一位是1，1和任何数字进行或运算都为1，因此，n>>>1，会使得n的前2位变为2，然后再执行n>>>2，就是前4位，再执行n>>>4，就是前8位。）如果数字没有那么高位，那么高位全是0，并且n>>>x全部都为0，因而或运算为0，高位没有任何影响，看下图例子：

这个算法，巧妙地通过了位运算，返回了一个不小于capacity 的最小2的幂次方。至于为什么要-1，是防止capacity已经是2的幂次方的情况，比如是10000，如果不减1，那么返回的将会是100000.减去1，使得初始的capacity改为1111（1111和1001，1101等都是一样的）。
以上的情况都是在capacity不为0的情况考虑的，而当capacity为0的时候，无论经过几次运算，都为0，那么最后的capacity将为1（最后有一个n+1的操作），所以也是符合预期结果的。
这样，我们就得到了一个2的幂次方的capacity，即哈希数组的长度（所以比如，当我们传入的capacity为12，最终生成的数组长度会是16.）
结果：
// 如果没有指定initialCapacity, 则不会给threshold赋值, 该值被初始化为0
// 如果指定了initialCapacity, 该值被初始化成不小于initialCapacity的最小的2的次幂

四. ②put方法：

可以看到，put方法其实还有两个参数，但put方法并没有重载方法，所以如果我们需要改变后两个参数，应该使用putVal方法自己修改，但一般不需要，在下文看putVal的方法里我们就知道着两个参数是什么作用了。

1
2
3

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

接下来关键是看putVal的方法实现：（逐行分析，中文注释）

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;	
//如果哈希数组为空，即还没初始化，先resize一次，resize后面再看，这里只需要知道
//会创建一个默认长度的哈希数组即可
    if ((p = tab[i = (n - 1) & hash]) == null)	
        tab[i] = newNode(hash, key, value, null);
//如果哈希数组该index没有元素，即没有发生碰撞，直接插入一个newNode即可。
//这里的(n - 1) & hash的原理，查看后面的question2
    else {	//说明已经有元素，发生了碰撞，然后我们就沿着链表/红黑树去插入Node
        Node<K,V> e; K k;
//我们首先会查看第一个元素（在第一个元素时就能确定它是链表还是数组）
        if (p.hash == hash &&	
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
//这里的p是上文的p = tab[i = (n - 1) & hash]，即第一个元素，如果第一个元素跟待插入
//的元素是相同的，即key相同（hash肯定是已经相同的了），然后我们只需要更改p的值
//即可。这里的逻辑是，把p赋值给新创建的Node e，然后跳出整个循环之后，再判断e
//是否位null，如果e为null，那么直接进行value的替换即可，否则，往后看。
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//判断该index项是链表还是红黑树，如果是红黑树再进入putTreeVal，此处略
        else {	
//说明是链表，并且第一个元素也不相等，所以我们就遍历链表，然后插入到链表的最
//后，并且，如果链表长度过长，还会引起链表树化的操作。如果是整个数组的长度过
//大，那么还要对数组进行resize。（PS：这里的元素相等是指key，链表里的key都是互
//不相等的，只是它们发生hash冲突导致都放在数组的同一个index上。所以如果在中间
//发现了相同的key，那么就跟前面一样，其实也是e = p的逻辑，然后在后续直接覆盖
//value即可。
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {		
                    p.next = newNode(hash, key, value, null);
//p.next为null，那么直接将p.next新建一个newNode即可。即已经到达链表的最后。
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
//这是指链表长度大于等于TREEIFY_THRESHOLD的时候，进行树化。默认是8.注意这
//里为什么是>= THREIFY_THRESHOLD，看起来是7个就可以树化，但实际上还是8个
//的。具体的看后面的question4.
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
//如果遇到了相等的key，那么就是覆盖value。注意此时并未到链表的最后，所以这里的
//e不等于null。而上面的(e = p.next) == null，上面逻辑的e会是null。这个e后面马上用到
                    break;
                p = e;
//这里的p = e实际上就是 p = p.next，因为并没有执行for循环里的两个if，如果执行了其
//中一个，都会直接break跳出循环。（个人觉得这个p = e放在for判定语句里可读性更好
            }
        }
        if (e != null) { // existing mapping for key
//这就是前面一直说的e，如果存在相同的key，那么e就不是null，此时直接覆盖value
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
//这就是第三个参数，表示已有相同的key时是否更新。onlyIfAbsent默认是false，所以这
//里的if是一定会触发，即一定会覆盖value。如果手动将onlyIfAbsent改为true，那么就是
//只有当oldValue为null的时候，才能改变key的value，否则都不会改变。
                e.value = value;
            afterNodeAccess(e);	
//这个在HashMap是空方法，在LinkedHashMap的时候才会被重写并使用。
            return oldValue;
//覆盖了value（或者不覆盖），就把oldValue返回，方法结束。因此插入一个相同key的
//元素，实际上是更新该key的value，方法的逻辑在这里已经完成，不会改变HashMap的
//大小
        }
    }	//最外层的if-else循环结束
    ++modCount;
//到达了这里，说明不存在相同的key，所以插入了一个新的key，改变modCount以及
//哈希数组的元素个数size
    if (++size > threshold)
        resize();
//如果改变了之后，哈希数组的元素个数大于threshold，此时发生碰撞的概率较大，因此
//进行resize，即对哈希数组进行扩容，后面会讲到。
    afterNodeInsertion(evict);	//同样是LinkedHashMap的东西，此处为空方法。
    return null;
}

主要是这么几个步骤：
①如果当前table为空，先进行初始化
②查找插入的键值对是否存在，存在的话，先进行赋值，后续将更新旧的键值对
③不存在，插入链表尾部，如果链表长度大于一个阈值，进行链表转化树的操作
④如果size大于一个阈值，进行扩容
PS：threshold在初始化的时候，值为2的幂次方（在tableForSize那里可以看到），但threshold应该是capacity * factor，当size大于threshold的时候才执行resize。那么会不会因此而导致初始化的时候threshold并不受factor的影响？
（比如我们初始化的时候，capacity传参是10，factor是0.75，在tableForSize里，我们知道threshold会被赋值为不小于10的2的幂次方，即16.然后根据put的逻辑，应当是++size > threshold的时候才扩容，那么初始化的threshold是16，而不是预期的值16 * 0.75 = 12？）
实际上并不是的，上面的threshold实际上就不应该是哈希数组的长度（所以JDK源码在构造方法里，把2的幂次方赋值给threshold确实有迷惑的意思）。在put方法的第一个步骤，即“如果当前table为空，先进行初始化”。那么我们再看一下这一行代码：

1 2	if ((tab = table) == null \|\| (n = tab.length) == 0) n = (tab = resize()).length;

当table为空，那么要先resize，即数组是在这里才进行建立的。在resize里面，是把threshold赋值给了另一个叫newCap的变量（看变量名可知，显然就是新的哈希数组的长度），然后threshold又会被改变为newCap * factor。所以threshold虽然确实是2的幂次方，但确实并不是代表哈希数组的长度，仍然是作为扩容的判断点（虽然是个无聊的问题，但感觉是JDK源码的变量具有迷惑性！）至于resize的源码，继续看。

五. ③get

get方法显然简单很多。首先判断是否存在该key，如果不存在，返回null。
getNode的逻辑体也是比较简单，先查找第一个元素，看key值是否相等。至于为什么需要“always check first node”，显然，因为JDK1.8可能是链表，可能是红黑树，需要进行判断。
如果当第一个first就是相等的，那么就直接返回。如果不在，判断是否是红黑树，如果是，使用另一套逻辑，如果不是，就是简单的链表遍历，对比，e = e.next，应该很好理解，此处略。

六. ④hash

首先给出HashMap计算哈希码的整体步骤：
1.获取key的hashCode
2.对hashCode进行处理（hash方法），主要是高16位不变，而低16位与高16位进行异或操作
3.对capacity进行取模（使用了 hash & (n - 1)进行优化）
在put和get方法中，可以看到都需要对key进行hash运算：

因为hashcode就是为了HashMap而生的，在学习重写equals时为何要重写hashCode的时候我们就已经知道了。那么HashMap里到底如何重写hashCode方法呢，如下：

嗯。。。很简单的异或运算，结合了key和value的hashCode，没什么特别的。结合value同样是减少碰撞。这个就是步骤1.

那么接下来看一下步骤2，HashMap自定义的hash方法：

从逻辑上看，就是hash本身与hash右移16位的结果进行异或。
h >>> 16的结果：高16位全部变成0，原本高16位的处于低16位。
h ^ ( h >>> 16)的结果：
1.高16位不变。因为0与任何数进行异或，返回的都是那个数本身。0 ^ 1 = 1, 0 ^ 0 = 0
2.低16位于原本的高16位进行异或。
步骤3对capacity取模，很好理解，不能超出哈希数组的范围。第二步的意义何在？看question3.

七. ⑤resize

在put的过程中，当size超出了threshold，那么就需要进行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) {		
//oldCap表明，table里原本已经存在key-value
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
//如果oldCap都已经扩容到最大了，那么就直接将threshold设为最大值，只好任你碰撞
            return oldTab;	
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
//没有超出最大值，那么就安心扩容为原来的 2倍。值得注意的是newCap跟newThr都扩
//容为 2倍，仔细看 if 语句的判定。
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
//这个就是我们前面所说的，当初始化的时候，会将threshold仅仅作为一个变量赋值给
//newCap，然后后面又把newCap*factor赋值给threshold
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
//这里就是调用new HashMap( )的情况，一个构造参数也没有的时候，直接赋默认值
    }
    if (newThr == 0) {
//当上面第一个if里面没有执行里面的两个子if语句时，newThr仍然没有变化，即为0.需要在这里再对threshold进行修改。
//（比如上面的： else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
//                 oldCap >= DEFAULT_INITIAL_CAPACITY)，此时newCap可能超出了MAX，那么
//newThr就仍然为0.又或者是 else if (oldThr > 0)  newCap = oldThr;中，即初始化带int参数的时
//候，这里仍然没有对threshold进行赋值。）
 	float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
//这段代码就是普通地判断threshold是否会超出MAX而已
    }
    threshold = newThr;
//我们已经将新数组的各种参数（capacity，threshold等）都设置好了，接下来需要将原
//本的数组元素放入到新的哈希数组中。显然，因为这个操作，使得resize方法是一个极
//其耗费时间的方法，所以在大概知道元素个数的时候，不应该使用默认值16，而是显式
//定义HashMap的初始容量，减少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;
//这里table中存放的只是Node的引用, 将oldTab[j]=null只是清除旧表的引用, 但是真正的
//node节点还在, 只是现在由e指向它。所以这里主要是提醒JVM，这里可以被GC清理了

                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
// 不是红黑树，那么就是链表。因此我们需要把该链表放入新的哈希数组的位置。
//主要是获取整条链表（即使只有 1个元素，结构仍然是链表）。
                    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) {		//第n位为0
// 我们知道hash & (n - 1)就是原本的位置，那么hash & n是什么？原本的哈希值为n - 1
//位，当它扩容之后，它的哈希值位n - 1或者n位，即第n位要么是0，要么是1，而
//hash & n就是能获取第n位的值，在后面我们会解释为什么
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {						//第n位为1
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);		//此处do-while刚好使得循环至少执行1次
                    if (loTail != null) {		//根据0还是1决定赋值哪个
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

关于resize的最后那一部分：
在JDK1.7之前，都是直接再计算一次hash，然后放入新的哈希数组位置（index,bucket）。
但在JDK1.8中，代码得到了改进，看一下官方注释：
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.
大致意思就是说，当超过限制的时候会resize，然而又因为我们使用的是2次幂的扩展(指长度扩为原来2倍)，所以，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。（n - 1位哈希码，变成n - 1位或 n位）
怎么理解呢？例如我们从16扩展为32时，具体的变化如下所示：

因此元素在重新计算hash之后，因为n变为2倍，那么n-1的mask范围在高位多1bit(红色)，因此新的index就会发生这样的变化：

因此，我们在扩充HashMap的时候，不需要重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”。可以看看下图为16扩充为32的resize示意图：

那么，为什么 hash & n就是可以获得第n位的值呢？
首先我们必须知道，n是一个2的幂次方数，它的二进制i形式是00……1000……
易知，0 & x = 0，1 & x = x，而我们就是想要hash值的第n位的x值。
因此，hash & n，刚好就是取到了新的hash值的第n位的x值。
故得出结论: （最后的if，else判断）
如果(e.hash & oldCap) == 0 则该节点在新表的下标位置与旧表一致都为 j
如果 (e.hash & oldCap) == 1则该节点在新表的下标位置 j + oldCap

八. 中间遗留出来的questions：

question1：哈希数组的长度为什么需要是2的幂次方？
ans：因为在映射的时候，需要执行(n - 1) & hash，当n不为2的幂次方的时候，n的个位为1，(n - 1)的个位则为0，又因为0 & x = 0，因此使得最后一位必定是0，即浪费了1个位的空间，碰撞的几率也会增大。而如果n是2的幂次方，那么(n - 1)的个位必定是1，1 & x = x，即根据hash的个位来决定，而不是一定返回0，因此能降低碰撞几率，充分利用每一个位。

question2：（n - 1 ) & hash的原理？
ans：因为n是2的幂次方，因而(n - 1)的值位000……1111（若干个1.(n - 1) & hash，即返回hash的低
⌈log2(n - 1)⌉ （2为底）位的值，即hash & n。如下图：

使用(n - 1) & hash而不使用hash % n的好处：
位运算是计算机最快的运算，因此效率更高。同样因为n是2的幂次方，因而该算法也不会出现超出取模范围的错误。

question3：为什么要将低16位与高16位进行异或操作？
ans：先看一下源码的代码注释：
Computes key.hashCode() and spreads (XORs) higher bits of hash to lower. Because the table uses power-of-two masking, sets of hashes that vary only in bits above the current mask will always collide. (Among known examples are sets of Float keys holding consecutive whole numbers in small tables.) So we apply a transform that spreads the impact of higher bits downward. There is a tradeoff between speed, utility, and quality of bit-spreading. Because many common sets of hashes are already reasonably distributed (so don’t benefit from spreading), and because we use trees to handle large sets of collisions in bins, we just XOR some shifted bits in the cheapest possible way to reduce systematic lossage, as well as to incorporate impact of the highest bits that would otherwise never be used in index calculations because of table bounds.
设计者认为(n - 1) & hash很容易发生碰撞，因为如果不对hash进行其他处理，那么hash起作用的仅仅是⌈log2(n - 1)⌉，比如当n为16的时候，hashCode起作用的仅仅是低4bit的有效位，那么当然容易碰撞了。因此，设计者想了一个顾全大局的方法(综合考虑了速度、作用、质量)，就是把高16bit和低16bit异或了一下。设计者还解释到因为现在大多数的hashCode的分布已经很不错了，就算是发生了碰撞也用O(logn)的tree去做了。仅仅异或一下，既减少了系统的开销，也不会造成的因为高位没有参与下标的计算(table长度比较小时)，从而引起的碰撞。（即通过h ^ (h >>> 16)，间接让高16位也参与计算，从而让键值对分布均匀，降低hash碰撞）

如果还是产生了频繁的碰撞，会发生什么问题呢？作者注释说，他们使用树来处理频繁的碰撞(we use trees to handle large sets of collisions in bins)，在JEP-180中，描述了这个问题：
Improve the performance of java.util.HashMap under high hash-collision conditions by using balanced trees rather than linked lists to store map entries. Implement the same improvement in the LinkedHashMap class.
之前已经提过，在获取HashMap的元素时，基本分两步：
首先根据hashCode()做hash，然后确定bucket的index；
如果bucket的节点的key不是我们需要的，则通过keys.equals()在链中找。
在Java 8之前的实现中是用链表解决冲突的，在产生碰撞的情况下，进行get时，两步的时间复杂度是O(1)+O(n)。因此，当碰撞很厉害的时候n很大，O(n)的速度显然是影响速度的。
因此在Java 8中，利用红黑树替换链表，这样复杂度就变成了O(1)+O(logn)了，这样在n很大的时候，能够比较理想的解决这个问题。

question4：为什么判定条件是”binCount >= TREEIFY_THRESHOLD - 1”，但树化的条件仍然是bitCount >= TREEIFY_THRESHOLD - 1?
ans：这里：binCount >= TREEIFY_THRESHOLD - 1，看起来是大于等于7就会树化，但其实并不是的。因为在刚执行完p.next = newNode(...);此时binCount仍然还没有执行完++。所以仍然是链表中元素的个数大于等于TREEIFY_THRESHOLD（默认是8），才会树化。
举例：当元素个数为1的时候，即只有p，此时binCount为0，然后执行p.next = newNode(...)。if判断失效，然后才执行binCount++（即添加完p.next之后，里面已经有k个元素了，但if判断的时候的binCount值为k - 1，只有到下一轮循环才改成k。
当链表一共有6个元素的时候，此时binCount为6（已经是下一轮循环），执行p.next = newNode,一共有7个元素。if判断（6 < = 7)，所以不会树化，循环结束，binCount为7.然后下一轮循环，添加元素，为8，此时 7 <= 7，为真，树化。
PS：Hash冲突是指不同对象的hashCode通过hash算法后得出了相同定位的下标，这时候采用链地址法，会将此元素插入至此位置链表的最后一位，形成单链表。当存在位置的链表长度大于等于 8 并且当前数组容量超过64时，HashMap会将链表转变为红黑树，这里要说明一点，往往后者的条件会被大多数人忽略，当桶数组容量比较小时，键值对节点 hash 的碰撞率可能会比较高，进而导致链表长度较长。这个时候应该优先扩容，而不是立马树化。毕竟高碰撞率是因为桶数组容量较小引起的，这个是主因。容量小时，优先扩容可以避免一些列的不必要的树化过程。

九. 其他一些常见问题：

1. 什么时候会使用HashMap？他有什么特点？
是基于Map接口的实现，存储键值对时，它可以接收null的键值，是非同步的，HashMap存储着Entry(hash, key, value, next)对象。

2. 你知道HashMap的工作原理吗？
通过hash的方法，通过put和get存储和获取对象。存储对象时，我们将K/V传给put方法时，它调用hashCode计算hash从而得到bucket位置，进一步存储，HashMap会根据当前bucket的占用情况自动调整容量(超过Load Facotr则resize为原来的2倍)。获取对象时，我们将K传给get，它调用hashCode计算hash从而得到bucket位置，并进一步调用equals()方法确定键值对。如果发生碰撞的时候，Hashmap通过链表将产生碰撞冲突的元素组织起来，在Java 8中，如果一个bucket中碰撞冲突的元素超过某个限制(默认是8)，则使用红黑树来替换链表，从而提高速度。HashMap是非线程安全的，在多线程的操作下会存在异常情况，可以使用HashTable或者ConcurrentHashMap进行代替

3. 你知道get和put的原理吗？equals()和hashCode()的都有什么作用？
通过对key的hashCode()进行hashing，并计算下标( n-1 & hash)，从而获得buckets的位置。如果产生碰撞，则利用key.equals()方法去链表或树中去查找对应的节点

4. 你知道hash的实现吗？为什么要这样实现？
在Java 1.8的实现中，是通过hashCode()的高16位异或低16位实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度、功效、质量来考虑的，这么做可以在bucket的n比较小的时候，也能保证考虑到高低bit都参与到hash的计算中，同时不会有太大的开销。

5. 如果HashMap的大小超过了负载因子(load factor)定义的容量，怎么办？
如果超过了负载因子(默认0.75)，则会重新resize一个原来长度两倍的HashMap，并且重新调用hash方法。

6. JDK1.8之前，HashMap在并发的情况下会出现问题，比如同时put的时候甚至会引起死循环，导致CPU使用率100%，为什么？
因为JDK1.8之前的resize方法是需要rehash的，导致在旧链表迁移到新链表的时候，如果在新链表的数组索引相同，会导致链表元素倒置，在JDK1.8中不需要rehash，直接根据新增的1bit是0还是1，决定是在原本位置还是增加capacity的位置，不会倒置。
而JDK1.8之前的transfer，以JDK1.7为例，当两个线程同时resize的时候，由于链表倒置，有可能出现循环链表的情况，导致无限循环，耗尽CPU算力。具体看这里：https://tech.meituan.com/2016/06/24/java-hashmap.html
HashMap是非线程安全的，在多线程的操作下会存在异常情况，比如类似于数据库的更新丢失（两个线程同时put，可能会导致其中一个put失效）。可以使用Hashtable或者ConcurrentHashMap进行代替。（Hashtable的效率太低，不推荐使用）
PS：回到本题的主干：存放数据时发现正在扩容会怎么样。
对于JDK1.7，应该就是同时resize，导致死循环。对于JDK1.8，则不会出现死循环。（1.7是头插法，导致会倒置，形成循环链表。而1.8增加了tail指针，使用尾插法，时间复杂度仍然是O(1)，但不会倒置，因而不会出现死循环。）。1.8中hashmap的确不会因为多线程put导致死循环，但是依然有其他的弊端，比如数据丢失等等。因此多线程情况下还是建议使用concurrenthashmap。

参考网站：
https://segmentfault.com/a/1190000015812438
http://yikun.github.io/2015/04/01/Java-HashMap%E5%B7%A5%E4%BD%9C%E5%8E%9F%E7%90%86%E5%8F%8A%E5%AE%9E%E7%8E%B0/
https://juejin.im/post/5a7719456fb9a0633e51ae14
https://juejin.im/post/5c7f69dff265da2dea054fdc
https://blog.csdn.net/fan2012huan/article/details/51097331
https://blog.csdn.net/zhuqiuhui/article/details/51849692