目录
（1）ConcurrentHashMap 的实现原理是什么？
（2）JDK1.8 中为什么使用内置锁 synchronized替换 可重入锁 ReentrantLock？
（1）ConcurrentHashMap 的 put 方法执行逻辑是什么？
（2）ConcurrentHashMap 的 get 方法执行逻辑是什么？
（3）ConcurrentHashMap 的 get 方法是否要加锁，为什么？
（4）get 方法不需要加锁与 volatile 修饰的哈希桶数组有关吗？
（1）ConcurrentHashMap 不支持 key 或者 value 为 null 的原因？
（3）ConcurrentHashMap 迭代器是强一致性还是弱一致性？
（4）JDK1.7 与 JDK1.8 中ConcurrentHashMap 的区别？
（5）ConcurrentHashMap 和 Hashtable 的效率哪个更高？为什么？
（2）为什么在解决 hash 冲突的时候，不直接用红黑树？而选择先用链表，再转红黑树?
（1）默认加载因子是多少？为什么是 0.75，不是 0.6 或者 0.8 ？
（2）JDK1.8 为什么要 hashcode 异或其右移十六位的值？
时隔三个月，我又回来整理学习笔记了。因为准备期末考试和找实习的事，有点小懈怠了。现在实习已经有两个月了，接下来的时间，我会继续学习，继续整理自己每周的学习内容。
一、ConcurrentHashMap
1、实现原理
（1）ConcurrentHashMap 的实现原理是什么？
ConcurrentHashMap 在 JDK1.7 和 JDK1.8 的实现方式是不同的。
先来看下JDK1.7
JDK1.7 中的 ConcurrentHashMap 是由 Segment 数组结构和 HashEntry 数组结构组成，即 ConcurrentHashMap 把哈希桶数组切分成小数组（Segment ），每个小数组有 n 个 HashEntry 组成。如下图所示，首先将数据分为一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一段数据时，其他段的数据也能被其他线程访问，实现了真正的并发访问。
Segment 是 ConcurrentHashMap 的一个内部类，主要的组成如下：
Segment 继承了 ReentrantLock，所以 Segment 是一种可重入锁，扮演锁的角色。Segment 默认为 16，也就是并发度为 16。
存放元素的 HashEntry，也是一个静态内部类，主要的组成如下：
其中，用 volatile 修饰了 HashEntry 的数据 value 和 下一个节点 next，保证了多线程环境下数据获取时的可见性！
再来看下JDK1.8
在数据结构上， JDK1.8 中的ConcurrentHashMap 选择了与 HashMap 相同的Node数组+链表+红黑树结构；在锁的实现上，抛弃了原有的 Segment 分段锁，采用 CAS + synchronized实现更加细粒度的锁。
将锁的级别控制在了更细粒度的哈希桶数组元素级别，也就是说只需要锁住这个链表头节点（红黑树的根节点），就不会影响其他的哈希桶数组元素的读写，大大提高了并发度。
（2）JDK1.8 中为什么使用内置锁 synchronized替换 可重入锁 ReentrantLock？
- 在 JDK1.6 中，对 synchronized 锁的实现引入了大量的优化，并且 synchronized 有多种锁状态，会从无锁 -> 偏向锁 -> 轻量级锁 -> 重量级锁一步步转换。
- 减少内存开销 。假设使用可重入锁来获得同步支持，那么每个节点都需要通过继承 AQS 来获得同步支持。但并不是每个节点都需要获得同步支持的，只有链表的头节点（红黑树的根节点）需要同步，这无疑带来了巨大内存浪费。
2、存取
（1）ConcurrentHashMap 的 put 方法执行逻辑是什么？
先来看JDK1.7
先定位到相应的 Segment ，然后再进行 put 操作。
源代码如下：
首先会尝试获取锁，如果获取失败肯定就有其他线程存在竞争，则利用 scanAndLockForPut() 自旋获取锁。
- 尝试自旋获取锁。
- 如果重试的次数达到了
MAX_SCAN_RETRIES则改为阻塞锁获取，保证能获取成功。
再来看JDK1.8
大致可以分为以下步骤：
根据 key 计算出 hash 值；
判断是否需要进行初始化；
定位到 Node，拿到首节点 f，判断首节点 f：
- 如果为 null ，则通过 CAS 的方式尝试添加；
- 如果为
f.hash = MOVED = -1，说明其他线程在扩容，参与一起扩容； - 如果都不满足 ，synchronized 锁住 f 节点，判断是链表还是红黑树，遍历插入；
当在链表长度达到 8 的时候，数组扩容或者将链表转换为红黑树。
源代码如下：
（2）ConcurrentHashMap 的 get 方法执行逻辑是什么？
同样，先来看JDK1.7
首先，根据 key 计算出 hash 值定位到具体的 Segment ，再根据 hash 值获取定位 HashEntry 对象，并对 HashEntry 对象进行链表遍历，找到对应元素。
由于 HashEntry 涉及到的共享变量都使用 volatile 修饰，volatile 可以保证内存可见性，所以每次获取时都是最新值。
源代码如下：
再来看JDK1.8
大致可以分为以下步骤：
根据 key 计算出 hash 值，判断数组是否为空；
如果是首节点，就直接返回；
如果是红黑树结构，就从红黑树里面查询；
如果是链表结构，循环遍历判断。
源代码如下：
（3）ConcurrentHashMap 的 get 方法是否要加锁，为什么？
get 方法不需要加锁。因为 Node 的元素 value 和指针 next 是用 volatile 修饰的，在多线程环境下线程A修改节点的 value 或者新增节点的时候是对线程B可见的。
这也是它比其他并发集合比如 Hashtable、用 Collections.synchronizedMap()包装的 HashMap 效率高的原因之一。
（4）get 方法不需要加锁与 volatile 修饰的哈希桶数组有关吗？
没有关系。哈希桶数组table用 volatile 修饰主要是保证在数组扩容的时候保证可见性。
3、其它
（1）ConcurrentHashMap 不支持 key 或者 value 为 null 的原因？
先来说value 为什么不能为 null。因为 ConcurrentHashMap 是用于多线程的 ，如果ConcurrentHashMap.get(key)得到了 null ，这就无法判断，是映射的value是 null ，还是没有找到对应的key而为 null ，就有了二义性。而用于单线程状态的 HashMap 却可以用containsKey(key) 去判断到底是否包含了这个 null 。
至于 ConcurrentHashMap 中的 key 为什么也不能为 null 的问题，源码就是这样写的。如果面试官不满意，就回答因为作者Doug不喜欢 null ，所以在设计之初就不允许了 null 的 key 存在。想要深入了解的小伙伴，可以看这篇文章这道面试题我真不知道面试官想要的回答是什么
（2）ConcurrentHashMap 的并发度是什么？
并发度可以理解为程序运行时能够同时更新 ConccurentHashMap且不产生锁竞争的最大线程数。在JDK1.7中，实际上就是ConcurrentHashMap中的分段锁个数，即Segment[]的数组长度，默认是16，这个值可以在构造函数中设置。
如果自己设置了并发度，ConcurrentHashMap 会使用大于等于该值的最小的2的幂指数作为实际并发度，也就是比如你设置的值是17，那么实际并发度是32。
如果并发度设置的过小，会带来严重的锁竞争问题；如果并发度设置的过大，原本位于同一个Segment内的访问会扩散到不同的Segment中，CPU cache命中率会下降，从而引起程序性能下降。
在JDK1.8中，已经摒弃了Segment的概念，选择了Node数组+链表+红黑树结构，并发度大小依赖于数组的大小。
（3）ConcurrentHashMap 迭代器是强一致性还是弱一致性？
与 HashMap 迭代器是强一致性不同，ConcurrentHashMap 迭代器是弱一致性。
ConcurrentHashMap 的迭代器创建后，就会按照哈希表结构遍历每个元素，但在遍历过程中，内部元素可能会发生变化，如果变化发生在已遍历过的部分，迭代器就不会反映出来，而如果变化发生在未遍历过的部分，迭代器就会发现并反映出来，这就是弱一致性。
这样迭代器线程可以使用原来老的数据，而写线程也可以并发的完成改变，更重要的，这保证了多个线程并发执行的连续性和扩展性，是性能提升的关键。想要深入了解的小伙伴，可以看这篇文章：为什么ConcurrentHashMap是弱一致的
（4）JDK1.7 与 JDK1.8 中ConcurrentHashMap 的区别？
- 数据结构：取消了 Segment 分段锁的数据结构，取而代之的是数组+链表+红黑树的结构。
- 保证线程安全机制：JDK1.7 采用 Segment 的分段锁机制实现线程安全，其中 Segment 继承自 ReentrantLock 。JDK1.8 采用
CAS+synchronized保证线程安全。 - 锁的粒度：JDK1.7 是对需要进行数据操作的 Segment 加锁，JDK1.8 调整为对每个数组元素加锁（Node）。
- 链表转化为红黑树：定位节点的 hash 算法简化会带来弊端，hash 冲突加剧，因此在链表节点数量大于 8（且数据总量大于等于 64）时，会将链表转化为红黑树进行存储。
- 查询时间复杂度：从 JDK1.7的遍历链表O(n)， JDK1.8 变成遍历红黑树O(logN)。
（5）ConcurrentHashMap 和 Hashtable 的效率哪个更高？为什么？
ConcurrentHashMap 的效率要高于 Hashtable，因为 Hashtable 给整个哈希表加了一把大锁从而实现线程安全。而ConcurrentHashMap 的锁粒度更低，在 JDK1.7 中采用分段锁实现线程安全，在 JDK1.8 中采用CAS+synchronized实现线程安全。
（6）具体说一下Hashtable的锁机制
Hashtable 是使用 synchronized来实现线程安全的，给整个哈希表加了一把大锁，多线程访问时候，只要有一个线程访问或操作该对象，那其他线程只能阻塞等待需要的锁被释放，在竞争激烈的多线程场景中性能就会非常差！
（7）多线程下安全的操作 map还有其他方法吗？
还可以使用Collections.synchronizedMap方法，对方法进行加同步锁。
如果传入的是 HashMap 对象，其实也是对 HashMap 做的方法做了一层包装，里面使用对象锁来保证多线程场景下，线程安全，本质也是对 HashMap 进行全表锁。在竞争激烈的多线程环境下性能依然也非常差，不推荐使用！
二、HashMap
1、 存储结构
（1）HashMap的底层数据结构是什么？
在JDK1.7 和JDK1.8 中有所差别：
在JDK1.7 中，由“数组+链表”组成，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的。
在JDK1.8 中，由“数组+链表+红黑树”组成。当链表过长，则会严重影响 HashMap 的性能，红黑树搜索时间复杂度是 O(logn)，而链表是糟糕的 O(n)。因此，JDK1.8 对数据结构做了进一步的优化，引入了红黑树，链表和红黑树在达到一定条件会进行转换：
当链表超过 8 且数据总量超过 64 才会转红黑树。
将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树，以减少搜索时间。
（2）为什么在解决 hash 冲突的时候，不直接用红黑树？而选择先用链表，再转红黑树?
因为红黑树需要进行左旋，右旋，变色这些操作来保持平衡，而单链表不需要。当元素小于 8 个的时候，此时做查询操作，链表结构已经能保证查询性能。当元素大于 8 个的时候， 红黑树搜索时间复杂度是 O(logn)，而链表是 O(n)，此时需要红黑树来加快查询速度，但是新增节点的效率变慢了。
因此，如果一开始就用红黑树结构，元素太少，新增效率又比较慢，无疑这是浪费性能的。
（3）不用红黑树，用二叉查找树可以么?
可以。但是二叉查找树在特殊情况下会变成一条线性结构（这就跟原来使用链表结构一样了，造成很深的问题），遍历查找会非常慢。
（4）为什么链表改为红黑树的阈值是 8?
因为泊松分布，我们来看作者在源码中的注释：
Because TreeNodes are about twice the size of regular nodes, we
use them only when bins contain enough nodes to warrant use
(see TREEIFY_THRESHOLD). And when they become too small (due to
removal or resizing) they are converted back to plain bins. In
usages with well-distributed user hashCodes, tree bins are
rarely used. 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翻译过来大概的意思是：理想情况下使用随机的哈希码，容器中节点分布在 hash 桶中的频率遵循泊松分布，按照泊松分布的计算公式计算出了桶中元素个数和概率的对照表，可以看到链表中元素个数为 8 时的概率已经非常小，再多的就更少了，所以原作者在选择链表元素个数时选择了 8，是根据概率统计而选择的。
2、字段结构
（1）默认加载因子是多少？为什么是 0.75，不是 0.6 或者 0.8 ？
回答这个问题前，我们来先看下HashMap的默认构造函数：
int threshold; // 容纳键值对的最大值
final float loadFactor; // 负载因子
int modCount;
int size; Node[] table的初始化长度length(默认值是16)，Load factor为负载因子(默认值是0.75)，threshold是HashMap所能容纳键值对的最大值。threshold = length * Load factor。也就是说，在数组定义好长度之后，负载因子越大，所能容纳的键值对个数越多。
默认的loadFactor是0.75，0.75是对空间和时间效率的一个平衡选择，一般不要修改，除非在时间和空间比较特殊的情况下 ：
如果内存空间很多而又对时间效率要求很高，可以降低负载因子Load factor的值 。
相反，如果内存空间紧张而对时间效率要求不高，可以增加负载因子loadFactor的值，这个值可以大于1。
我们来追溯下作者在源码中的注释（JDK1.7）：
As a general rule, the default load factor (.75) offers a good tradeoff
between time and space costs. Higher values decrease the space overhead
but increase the lookup cost (reflected in most of the operations of the
HashMap class, including get and put). The expected number of entries in
the map and its load factor should be taken into account when setting its
initial capacity, so as to minimize the number of rehash operations. If
the initial capacity is greater than the maximum number of entries divided
by the load factor, no rehash operations will ever occur.翻译过来大概的意思是：作为一般规则，默认负载因子（0.75）在时间和空间成本上提供了很好的折衷。较高的值会降低空间开销，但提高查找成本（体现在大多数的HashMap类的操作，包括get和put）。设置初始大小时，应该考虑预计的entry数在map及其负载系数，并且尽量减少rehash操作的次数。如果初始容量大于最大条目数除以负载因子，rehash操作将不会发生。
3、索引计算
（1）HashMap 中 key 的存储索引是怎么计算的？
首先根据key的值计算出hashcode的值，然后根据hashcode计算出hash值，最后通过hash&（length-1）计算得到存储的位置。看看源码的实现：
// jdk1.7
方法一：
static int hash(int h) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode(); // 为第一步：取hashCode值
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
方法二：
static int indexFor(int h, int length) { //jdk1.7的源码，jdk1.8没有
//这个方法，但实现原理一样
return h & (length-1); //第三步：取模运算
}
// jdk1.8
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
/*
h = key.hashCode() 为第一步：取hashCode值
h ^ (h >>> 16) 为第二步：高位参与运算
*/
}这里的 Hash 算法本质上就是三步：取key的 hashCode 值、根据 hashcode 计算出hash值、通过取模计算下标。其中，JDK1.7和1.8的不同之处，就在于第二步。我们来看下详细过程，以JDK1.8为例，n为table的长度。
（2）JDK1.8 为什么要 hashcode 异或其右移十六位的值？
因为在JDK 1.7 中扰动了 4 次，计算 hash 值的性能会稍差一点点。 从速度、功效、质量来考虑，JDK1.8 优化了高位运算的算法，通过hashCode()的高16位异或低16位实现：(h = k.hashCode()) ^ (h >>> 16)。这么做可以在数组 table 的 length 比较小的时候，也能保证考虑到高低Bit都参与到Hash的计算中，同时不会有太大的开销。
（3）为什么 hash 值要与length-1相与？
- 把 hash 值对数组长度取模运算，模运算的消耗很大，没有位运算快。
- 当 length 总是 2 的n次方时，h& (length-1) 运算等价于对length取模，也就是 h%length，但是 & 比 % 具有更高的效率。
（4）HashMap数组的长度为什么是 2 的幂次方？
这样做效果上等同于取模，在速度、效率上比直接取模要快得多。除此之外，2 的 N 次幂有助于减少碰撞的几率。如果 length 为2的幂次方，则 length-1 转化为二进制必定是11111……的形式，在与h的二进制与操作效率会非常的快，而且空间不浪费。我们来举个例子，看下图：
当 length =15时，6 和 7 的结果一样，这样表示他们在 table 存储的位置是相同的，也就是产生了碰撞，6、7就会在一个位置形成链表，4和5的结果也是一样，这样就会导致查询速度降低。
如果我们进一步分析，还会发现空间浪费非常大，以 length=15 为例，在 1、3、5、7、9、11、13、15 这八处没有存放数据。因为hash值在与14（即 1110）进行&运算时，得到的结果最后一位永远都是0，即 0001、0011、0101、0111、1001、1011、1101、1111位置处是不可能存储数据的。
（5）补充数组容量计算的小奥秘
HashMap 构造函数允许用户传入的容量不是 2 的 n 次方，因为它可以自动地将传入的容量转换为 2 的 n 次方。会取大于或等于这个数的 且最近的2次幂作为 table 数组的初始容量，使用tableSizeFor(int)方法，如 tableSizeFor(10) = 16（2 的 4 次幂），tableSizeFor(20) = 32（2 的 5 次幂），也就是说 table 数组的长度总是 2 的次幂。JDK1.8 源码如下：
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;
}
/*
解释：位或( | )
int n = cap - 1; 让cap-1再赋值给n的目的是另找到的目标值
大于或等于原值。例如二进制1000，十进制数值为8。如果不对它
减1而直接操作，将得到答案10000，即16。显然不是结果。减1后
二进制为111，再进行操作则会得到原来的数值1000，即8。
*/4、put方法
（1）HashMap 的put方法流程？
简要流程如下：
首先根据 key 的值计算 hash 值，找到该元素在数组中存储的下标；
如果数组是空的，则调用 resize 进行初始化；
如果没有哈希冲突直接放在对应的数组下标里；
如果冲突了，且 key 已经存在，就覆盖掉 value；
如果冲突后，发现该节点是红黑树，就将这个节点挂在树上；
如果冲突后是链表，判断该链表是否大于 8 ，如果大于 8 并且数组容量小于 64，就进行扩容；如果链表节点大于 8 并且数组的容量大于 64，则将这个结构转换为红黑树；否则，链表插入键值对，若 key 存在，就覆盖掉 value。
详细分析，见JDK1.8HashMap 的 put 方法源码:
public V put(K key, V value) {
// 对key的hashCode()做hash
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;
// 步骤1：tab为空则创建
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 步骤2：计算index，并对null做处理
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 步骤3：节点key存在，直接覆盖value
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 步骤4：判断该链为红黑树
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 步骤5：该链为链表
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//链表长度大于8转换为红黑树进行处理
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// key已经存在直接覆盖value
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 步骤6：超过最大容量 就扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
// 第31行treeifyBin方法部分代码
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// static final int MIN_TREEIFY_CAPACITY = 64;
// 如果大于8但是数组容量小于64，就进行扩容
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
}
（2）JDK1.7 和1.8 的put方法区别是什么？
区别在两处：
- 解决哈希冲突时，JDK1.7 只使用链表，JDK1.8 使用链表+红黑树，当满足一定条件，链表会转换为红黑树。
- 链表插入元素时，JDK1.7 使用头插法插入元素，在多线程的环境下有可能导致环形链表的出现，扩容的时候会导致死循环。因此，JDK1.8使用尾插法插入元素，在扩容时会保持链表元素原本的顺序，就不会出现链表成环的问题了，但JDK1.8 的 HashMap 仍然是线程不安全的。
5、扩容机制
（1）HashMap 的扩容方式？
Hashmap 在容量超过负载因子所定义的容量之后，就会扩容。Java 里的数组是无法自动扩容的，方法是将 Hashmap 的大小扩大为原来数组的两倍，并将原来的对象放入新的数组中。
那扩容的具体步骤是什么？让我们看看源码。
先来看下JDK1.7 的代码：
void resize(int newCapacity) { //传入新的容量
//引用扩容前的Entry数组
Entry[] oldTable = table;
int oldCapacity = oldTable.length
//扩容前的数组大小如果已经达到最大(2^30)了
if (oldCapacity == MAXIMUM_CAPACITY) {
//修改阈值为int的最大值(2^31-1)，这样以后就不会扩容了
threshold = Integer.MAX_VALUE;
return;
}
//初始化一个新的Entry数组
Entry[] newTable = new Entry[newCapacity];
//！！将数据转移到新的Entry数组里
transfer(newTable);
//HashMap的table属性引用新的Entry数组
table = newTable;
//修改阈值
threshold = (int)(newCapacity * loadFactor);
}这里就是使用一个容量更大的数组来代替已有的容量小的数组，transfer()方法将原有Entry数组的元素拷贝到新的Entry数组里。
void transfer(Entry[] newTable) {
//src引用了旧的Entry数组
Entry[] src = table;
int newCapacity = newTable.length;
//遍历旧的Entry数组
for (int j = 0; j < src.length; j++) {
//取得旧Entry数组的每个元素
Entry<K,V> e = src[j];
if (e != null) {
//释放旧Entry数组的对象引用（for循环后，
//旧的Entry数组不再引用任何对象）
src[j] = null;
do {
Entry<K,V> next = e.next;
//！！重新计算每个元素在数组中的位置
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i]; //标记[1]
newTable[i] = e; //将元素放在数组上
e = next; //访问下一个Entry链上的元素
} while (e != null);
}
}
}newTable[i] 的引用赋给了 e.next ，也就是使用了单链表的头插入方式，同一位置上新元素总会被放在链表的头部位置；这样先放在一个索引上的元素终会被放到 Entry 链的尾部(如果发生了 hash 冲突的话）。
（2）JDK1.8的优化
JDK1.8做了两处优化：
resize 之后，元素的位置在原来的位置，或者原来的位置 +oldCap (原来哈希表的长度）。不需要像 JDK1.7 的实现那样重新计算hash ，只需要看看原来的 hash 值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引 + oldCap ”。这个设计非常的巧妙，省去了重新计算 hash 值的时间。
如下图所示，n 为 table 的长度，图（a）表示扩容前的 key1 和 key2 两种 key 确定索引位置的示例，图（b）表示扩容后 key1 和key2 两种 key 确定索引位置的示例，其中 hash1 是 key1 对应的哈希与高位运算结果。
元素在重新计算 hash 之后，因为 n 变为 2倍，那么 n-1 的 mask 范围在高位多 1 bit(红色)，因此新的index就会发生这样的变化：
- JDK1.7 中 rehash 的时候，旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置（头插法）。JDK1.8 不会倒置，使用尾插法。
下图为 16扩充为 32 的 resize 示意图：
感兴趣的小伙伴可以看下 JDK1.8 的 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) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 没超过最大值，就扩充为原来的2倍
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);
}
// 计算新的resize上限
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) {
// 把每个bucket都移动到新的buckets中
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 { // 链表优化重hash的代码块
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;
}
// 原索引+oldCap
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 原索引放到bucket里
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 原索引+oldCap放到bucket里
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}6、 其他
（1）还知道哪些hash算法？
Hash函数是指把一个大范围映射到一个小范围，目的往往是为了节省空间，使得数据容易保存。 比较出名的有MurmurHash、MD4、MD5等等。
（2）key 可以为 Null 吗?
可以，key 为 Null 的时候，hash算法最后的值以0来计算，也就是放在数组的第一个位置。
（3）一般用什么作为HashMap的key?
一般用Integer、String 这种不可变类当 HashMap 当 key，而且 String 最为常用。
- 因为字符串是不可变的，所以在它创建的时候 hashcode 就被缓存了，不需要重新计算。这就是 HashMap 中的键往往都使用字符串的原因。
- 因为获取对象的时候要用到 equals() 和 hashCode() 方法，那么键对象正确的重写这两个方法是非常重要的,这些类已经很规范的重写了 hashCode() 以及 equals() 方法。
（4）用可变类当 HashMap 的 key 有什么问题?
hashcode 可能发生改变，导致 put 进去的值，无法 get 出。如下所示
HashMap<List<String>, Object> changeMap = new HashMap<>();
List<String> list = new ArrayList<>();
list.add("hello");
Object objectValue = new Object();
changeMap.put(list, objectValue);
System.out.println(changeMap.get(list));
list.add("hello world");//hashcode发生了改变
System.out.println(changeMap.get(list));输出值如下
java.lang.Object@74a14482
null三、HashMap的线程安全问题
1、多线程下扩容死循环
JDK1.7中的 HashMap 使用头插法插入元素，在多线程的环境下，扩容的时候有可能导致环形链表的出现，形成死循环。因此，JDK1.8使用尾插法插入元素，在扩容时会保持链表元素原本的顺序，不会出现环形链表的问题。
看看多线程情况下， JDK1.7 扩容死循环问题的分析。
新建一个更大尺寸的hash表，然后把数据从老的hash表中迁移到新的hash表中。重点看下transfer方法：
假设HashMap初始化大小为2，hash算法就是用key mod 表的长度，在mod 2以后都冲突在table[1]这里了。负载因子是 1.5 (默认为 0.75 )，由公式 threshold=负载因子 * hash表长度可得，threshold=1.5 * 2 =3，size=3，而 size>=threshold 就要扩容，所以 hash表要 resize 成 4。
未resize前的table如下图：
正常的ReHash，得到的结果如下图所示：
我们来看看多线程下的ReHash，假设现在有两个线程同时进行，线程1和线程2，两个线程都会新建新的数组，下面是resize 的过程。
未resize前的table如下图：
正常的ReHash，得到的结果如下图所示：
我们来看看多线程下的ReHash，假设现在有两个线程同时进行，线程1和线程2，两个线程都会新建新的数组，下面是resize 的过程。
Step1:
假设 线程1 在执行到Entry<K,V> next = e.next;之后，cpu 时间片用完了，被调度挂起，这时线程1的 e 指向 节点A，线程1的 next 指向节点B。
线程2继续执行，
Step2:
线程 1 被调度回来执行。
- 先是执行 newTalbe[i] = e;
- 然后是e = next，导致了e指向了节点B，
- 而下一次循环的next = e.next导致了next指向了节点A。
Step3:
线程1 接着工作。把节点B摘下来，放到newTable[i]的第一个，然后把e和next往下移。
Step4: 出现环形链表
e.next = newTable[i] 导致A.next 指向了 节点B，此时的B.next 已经指向了节点A，出现环形链表。
如果get一个在此链表中不存在的key时，就会出现死循环了。如 get(11)时，就发生了死循环。
分析见get方法的源码：
for循环中的e = e.next永远不会为空，那么，如果get一个在这个链表中不存在的key时，就会出现死循环了。
2、多线程的put可能导致元素的丢失
多线程同时执行 put 操作，如果计算出来的索引位置是相同的，那会造成前一个 key 被后一个 key 覆盖，从而导致元素的丢失。此问题在JDK 1.7和 JDK 1.8 中都存在。
我们来看下JDK 1.8 中 put 方法的部分源码，重点看黄色部分：
我们来演示个例子。
假设线程1和线程2同时执行put，线程1执行put(“1”, “A”)，线程2执行put(“5”, “B”)，hash算法就是用key mod 表的长度，表长度为4，在mod 4 以后都冲突在table[1]这里了。注：下面的例子，只演示了 #1 和#2代码的情况，其他代码也会出现类似情况。
正常情况下，put完成后，table的状态应该是下图中的任意一个。
下面来看看异常情况，两个线程都执行了#1处的if ((p = tab[i = (n - 1) & hash]) == null)这句代码。
此时假设线程1 先执行#2处的tab[i] = newNode(hash, key, value, null);
那么table会变成如下状态：
紧接着线程2 执行tab[i] = newNode(hash, key, value, null);
此时table会变成如下状态:
这样一来，元素A就丢失了。
3、put和get并发时，可能导致get为null
线程1执行put时，因为元素个数超出threshold而导致rehash，线程2此时执行get，有可能导致这个问题。此问题在JDK 1.7和 JDK 1.8 中都存在。
我们来看下JDK 1.8 中 resize 方法的部分源码，重点看黄色部分：
在代码#1位置，用新计算的容量new了一个新的hash表，#2将新创建的空hash表赋值给实例变量table。
注意此时实例变量table是空的，如果此时另一个线程执行get，就会get出null。