HashMap 底层实现、加载因子、容量值及死循环
HashMap 底层实现、加载因子、容量值及死循环
写在前面：2020年面试必备的Java后端进阶面试题总结了一份复习指南在Github上，内容详细，图文并茂，有需要学习的朋友可以Star一下！ GitHub地址：https://github.com/abel-max/Java-Study-Note/tree/master
HashMap 简介
HashMap 是一个基于哈希表实现的无序的 key-value 容器，它键和值允许设置为 null，同时它是线程不安全的。
HashMap 底层实现
- 在 jdk 1.7中 HashMap 是以数组+链表的实现的
- 在 jdk1.8 开始引入红黑树，HashMap 底层变成了数组+链表+红黑树实现
红黑树简介
红黑树是一种特殊的平衡二叉树，它有如下的特征：
- 节点是红色或黑色
- 根节点是黑色的
- 所有叶子都是黑色。（叶子是NULL节点）
- 每个红色节点的两个子节点都是黑色的（从每个叶子到根的所有路径上不能有两个连续的红色节点）
- 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
所以红黑树的时间复杂度为: O(lgn)。
jdk1.8：数组+链表+红黑树
HashMap 的底层首先是一个数组，元素存放的数组索引值就是由该元素的哈希值（key-value 中 key 的哈希值）确定的，这就可能产生一种特殊情况——不同的 key 哈希值相同。
在这样的情况下，于是引入链表，如果 key 的哈希值相同，在数组的该索引中存放一个链表，这个链表就包含了所有 key 的哈希值相同的 value 值，这就解决了哈希冲突的问题。
但是如果发生大量哈希值相同的特殊情况，导致链表很长，就会严重影响 HashMap 的性能，因为链表的查询效率需要遍历所有节点。于是在 jdk1.8 引入了红黑树，当链表的长度大于8，且 HashMap 的容量大于64的时候，就会将链表转化为红黑树。
// jdk1.8
// HashMap#putVal
// binCount 是该链表的长度计数器，当链表长度大于等于8时，执行树化方法
// TREEIFY_THRESHOLD = 8
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
// HashMap#treeifyBin
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// MIN_TREEIFY_CAPACITY=64
// 若 HashMap 的大小小于64，仅扩容，不树化
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}加载因子为什么是0.75
所谓的加载因子，也叫扩容因子或者负载因子，它是用来进行扩容判断的。
假设加载因子是0.5，HashMap 初始化容量是16，当 HashMap 中有 16 * 0。5=8个元素时，HashMap 就会进行扩容操作。
而 HashMap 中加载因子为0.75，是考虑到了性能和容量的平衡。
由加载因子的定义，可以知道它的取值范围是(0, 1]。
- 如果加载因子过小，那么扩容门槛低，扩容频繁，这虽然能使元素存储得更稀疏，有效避免了哈希冲突发生，同时操作性能较高，但是会占用更多的空间。
- 如果加载因子过大，那么扩容门槛高，扩容不频繁，虽然占用的空间降低了，但是这会导致元素存储密集，发生哈希冲突的概率大大提高，从而导致存储元素的数据结构更加复杂（用于解决哈希冲突），最终导致操作性能降低。
- 还有一个因素是为了提升扩容效率。因为 HashMap 的容量（size属性，构造函数中的initialCapacity变量）有一个要求：它一定是2的幂。所以加载因子选择了0.75就可以保证它与容量的乘积为整数。
// 构造函数
public HashMap(int initialCapacity, float loadFactor) {
// ……
this.loadFactor = loadFactor;// 加载因子
this.threshold = tableSizeFor(initialCapacity);
}
/**
* Returns a power of two size for the given target capacity.返回2的幂
* MAXIMUM_CAPACITY = 1 << 30
*/
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;
}HashMap 的容量为什么是2的 n 次幂
HashMap 的默认初始容量是16，而每次扩容是扩容为原来的2倍。这里的16和2倍就保证了 HashMap 的容量是2的 n 次幂，那么这样设计的原因是什么呢？
原因一：与运算高效
与运算 & ，基于二进制数值，同时为1结果为1，否则就是0。如1&1=1,1&0=0,0&0=0。使用与运算的原因就是对于计算机来说，与运算十分高效。
原因二：有利于元素充分散列，减少 Hash 碰撞
在给 HashMap 添加元素的 putVal 函数中，有这样一段代码：
// n为容量，hash为该元素的hash值
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);它会在添加元素时，通过 i = (n - 1) & hash 计算该元素在 HashMap 中的位置。
当 HashMap 的容量为 2 的 n 次幂时，他的二进制值是100000……（n个0），所以n-1的值就是011111……（n个1），这样的话 (n - 1) & hash 的值才能够充分散列。
举个例子，假设容量为16，现在有哈希值为1111，1110，1011，1001四种将被添加，它们与n-1(15的二进制=01111)的哈希值分别为1111、1110、1110、1011，都不相同。而假设容量不为2的n次幂，假设为10，与上述四个哈希值进行与运算的结果分别是：0101、0100、0001、0001。可以看到后两个值发生了碰撞。所以 HashMap 的容量设置为 2 的 n 次幂有利于元素的充分散列。
HashMap初始容量为什么是2的n次幂及扩容为什么是2倍的形式
HashMap 是如何导致死循环的
HashMap 会导致死循环是在 jdk1.7 中，由于扩容时的操作是使用头插法，在多线程的环境下可能产生循环链表，由此导致了死循环。在 jdk1.8 中改为使用尾插法，避免了该死循环的情况。
以下篇章来自博客【占小狼】 原文链接：https://blog.csdn.net/maohoo/article/details/81531925
问题
如果是在单线程下使用HashMap，自然是没有问题的，如果后期由于代码优化，这段逻辑引入了多线程并发执行，在一个未知的时间点，会发现CPU占用100%，居高不下，通过查看堆栈，你会惊讶的发现，线程都Hang在hashMap的get()方法上，服务重启之后，问题消失，过段时间可能又复现了。
这是为什么？
原因分析
在了解来龙去脉之前，我们先看看HashMap的数据结构。
在内部，HashMap使用一个Entry数组保存key、value数据，当一对key、value被加入时，会通过一个hash算法得到数组的下标index，算法很简单，根据key的hash值，对数组的大小取模 hash & (length-1)，并把结果插入数组该位置，如果该位置上已经有元素了，就说明存在hash冲突，这样会在index位置生成链表。
如果存在hash冲突，最惨的情况，就是所有元素都定位到同一个位置，形成一个长长的链表，这样get一个值时，最坏情况需要遍历所有节点，性能变成了O(n)，所以元素的hash值算法和HashMap的初始化大小很重要。
当插入一个新的节点时，如果不存在相同的key，则会判断当前内部元素是否已经达到阈值（默认是数组大小的0.75），如果已经达到阈值，会对数组进行扩容，也会对链表中的元素进行rehash。
源码分析
HashMap的put方法实现：
1、判断key是否已经存在
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
// 如果key已经存在，则替换value，并返回旧值
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
12345678910111213141516171819202122232、检查容量是否达到阈值threshold
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
123456789如果元素个数已经达到阈值，则扩容，并把原来的元素移动过去。
3、扩容实现
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
12345678910111213这里会新建一个更大的数组，并通过transfer方法，移动元素。
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
123456789101112131415移动的逻辑也很清晰，遍历原来table中每个位置的链表，并对每个元素进行重新hash，在新的newTable找到归宿，并插入。
案例分析
假设HashMap初始化大小为4，插入个3节点，不巧的是，这3个节点都hash到同一个位置，如果按照默认的负载因子的话，插入第3个节点就会扩容，为了验证效果，假设负载因子是1.
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
123456789101112131415以上是节点移动的相关逻辑。
HashMap 底层实现、加载因子、容量值及死循环
插入第4个节点时，发生rehash，假设现在有两个线程同时进行，线程1和线程2，两个线程都会新建新的数组
HashMap 底层实现、加载因子、容量值及死循环
假设线程2 在执行到Entry < K,V > next = e.next;之后，cpu时间片用完了，这时变量e指向节点a，变量next指向节点b。线程1继续执行，很不巧，a、b、c节点rehash之后又是在同一个位置7，开始移动节点第一步，移动节点a
HashMap 底层实现、加载因子、容量值及死循环
第二步，移动节点b
HashMap 底层实现、加载因子、容量值及死循环
注意，这里的顺序是反过来的，继续移动节点c
HashMap 底层实现、加载因子、容量值及死循环
这个时候 线程1 的时间片用完，内部的table还没有设置成新的newTable， 线程2 开始执行，这时内部的引用关系如下：
HashMap 底层实现、加载因子、容量值及死循环
这时，在 线程2 中，变量e指向节点a，变量next指向节点b，开始执行循环体的剩余逻辑。
Entry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
12345执行之后的引用关系如下图
HashMap 底层实现、加载因子、容量值及死循环
执行后，变量e指向节点b，因为e不是null，则继续执行循环体，执行后的引用关系
HashMap 底层实现、加载因子、容量值及死循环
变量e又重新指回节点a，只能继续执行循环体，这里仔细分析下：1、执行完Entry < K,V > next = e.next;，目前节点a没有next，所以变量next指向null；2、e.next = newTable[i]; 其中 newTable[i] 指向节点b，那就是把a的next指向了节点b，这样a和b就相互引用了，形成了一个环；3、newTable[i] = e 把节点a放到了数组i位置；4、e = next; 把变量e赋值为null，因为第一步中变量next就是指向null；
所以最终的引用关系是这样的：
HashMap 底层实现、加载因子、容量值及死循环
节点a和b互相引用，形成了一个环，当在数组该位置get寻找对应的key时，就发生了死循环。
另外，如果线程2把newTable设置成到内部的table，节点c的数据就丢了，看来还有数据遗失的问题。
总结所以在并发的情况，发生扩容时，可能会产生循环链表，在执行get的时候，会触发死循环，引起CPU的100%问题，所以一定要避免在并发环境下使用HashMap。
曾经有人把这个问题报给了Sun，不过Sun不认为这是一个bug，因为在HashMap本来就不支持多线程使用，要并发就用ConcurrentHashmap。