1.前言
最近一直准备面试，但是HashMap源码一直是面试过不去的坎，所以最近抽时间走了一遍源码。所以有了这篇博客，希望对面试者或者正在使用HashMap的开发人员有一定的帮助
2.准备
因为HashMap中涉及几个概念，所以在分析源码时候，我们先熟悉一下这几个概念。
数组：
数组在堆中是一块连续的存储空间，遍历快，时间复杂度为O(1) ；增删慢，时间复杂度为O(n) ；
链表：
链表和数组刚好相反，不需要连续的存储空间，具有遍历慢，增删块的特点。遍历查找时间复杂度O(n),增删时间复杂度O(1)；
红黑树：
二叉树是每个结点最多有两个子树的树结构，对其进行插入，查找，删除等操作，平均复杂度均为O(logn)
运符号：
1.&位与运算符:只有两个操作数都是true，结果才是true。
例如：01001&10001=00001
2.^位异或运算：两个数转为二进制，然后从高位开始比较，如果相同则为0,不相同则为1。
例如：15^2=1111 ^0010=1101=13
3.<< 左移运算符:num << 1,相当于num乘以2
例如：0001<<1=0010;
4.>> 右移运算符 :右移运算符，num >> 1,相当于num除以2
例如：0010>>1=0001
5.>>> : 无符号右移，忽略符号位，空位都以0补齐
例如：001110>>>2=000111
6.~位非运算符：如果位为0，结果是1，如果位为1，结果是0.
例如：~00011=11100
3.解析源码
HashMap在jdk1.8之前是一个数组加链表的结构，这种结构的特点是能有效的避免Hash碰撞，当没有Hash碰撞的时候，查询速度很快，复杂度和数组一样为O(1),如果发生Hash碰撞过多，会造成链表很长，此时查询效率严重降低，所以在jdk1.8引入了红黑树。当一个hash值上的链表长度大于8时，该节点的数据就不再以链表形式存在，而是转换为红黑树。红黑树时间复杂度为O(logn)。大体结构是这样的。
HashMap结构.png
3.1 HashMap成员变量的含义：
/**
* 主干数组默认初始化容量16, 二进制00010000，
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* 最大容量 2的30次方
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 默认负载因子是0.75
*
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* 链表节点转换红黑树节点的阈值,大于8链表转化为红黑树
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* 红黑树节点转换链表节点的阈值, 小于6个节点转
*/
static final int UNTREEIFY_THRESHOLD = 6;
/**
* 转红黑树时, HashMap的最小容量为64
*/
static final int MIN_TREEIFY_CAPACITY = 64;
/**
* The next size value at which to resize (capacity * load factor).
* 扩充临界值=主干数组容量*负载因子
*/
int threshold;
/**
* The load factor for the hash table.
*负载因子 ，代表了table的填充度有多少，
* @serial
*/
final float loadFactor;
以上具体就是我们需要知道的HashMap中成员属性的含义，接下来我们可能很多地方都要使用他们了。
3.2 HashMap主干是数组Node的源码
HashMap主干是数组，数组元素其实就是HashMap的静态内部类Node，接下来我们看Node的源码
/**
* Basic hash bin node, used for most entries. (See below for
* TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
* 链表节点, 继承自Entry
*/
static class Node<K, V> implements Map.Entry<K, V> {
final int hash;
final K key;
V value;
Node<K, V> next;//存储指向下一个Entry的引用，单链表结构
Node(int hash, K key, V value, Node<K, V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() {
return key;
}
public final V getValue() {
return value;
}
public final String toString() {
return key + "=" + value;
}
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?, ?> e = (Map.Entry<?, ?>) o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
3.3 HashMap构造函数
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
}
public HashMap(int initialCapacity, float loadFactor) {
// 初始化容量小于0抛出异常
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
// 初始化容量大于MAXIMUM_CAPACITY，抛出异常
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
// 初始化负载因子必须大于0
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
/**
* 将传入的cap返回比它大切最接近的它的2的次幂值，比如：9返回16，8返回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;
}
3.4 HashMap的put方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* 计算key的hash值
*/
static final int hash(Object key) {
int h;
/**
* 1.先拿到key的hashCode值;
* 2.将key的hashCode值与其无符号右移16位的值取^运算
*/
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
/**
* Implements Map.put and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K, V>[] tab;
Node<K, V> p;
int n, i;
// 判断table是否为空，如果是空的就创建一个table，并获取他的长度
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//如果计算出来的索引位置之前没有放过数据，就直接放入， &与运算符 1001&1000=1000
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
// 进入这里说明索引位置已经放入过数据了
Node<K, V> e;
K k;
// 判断put的数据和之前的数据是否重复
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);
// 如果不是红黑树，就遍历每个节点，判断链表长度是否大于等于8，如果大于等于就转换为红黑树
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
// 判断索引每个元素的key是否可要插入的key相同，如果相同就直接覆盖，遍历结束。
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 如果e不是null，说明没有迭代到最后就跳出了循环，说明链表中有相同的key，因此只需要将value覆盖，并将oldValue返回即可
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 如果当前大小大于门限，门限原本是初始容量的0.75
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
下面简单说一下添加键值对put(K key, V value)的过程：
1.判断当前桶是否为空，空的就需要初始化（在resize方法 中会判断是否进行初始化）。
2.根据key的hashcode值和数组长度定位出所在的桶。如果桶是空的，说明当前位置没有存入过数据，则新增一个Node对象写入当前位置。
3.如果桶不为空，则比较桶中key的hashCode和值和put进去的key的hashcode和值是否相等(可以理解为桶中只有一个元素且这个元素的key和put进去的key的hashCode值相等且本身值也相等)，相等则替换掉当前桶中元素。
4.判断桶中是否是红黑树，如果是红黑树，则按照红黑树的方式写入数据。
5.如果是链表，就需要将当前的key和value封装成一个新的Node写入当前桶的后面，形成链表结构。
6.判断当前链表长度是否达到预设阀值（默认是8），达到则转化为红黑树
7.如果遍历过程中找到key相同时，直接退出遍历，然后将值覆盖
8.最后判断是否需要扩容。
3.5 HashMap的扩容机制：resize()
构造hash表时，如果不指明初始大小，默认大小为16（即Node数组大小16），如果Node[]数组中的元素达到（填充比*Node.length）重新调整HashMap大小 变为原来2倍大小,扩容很耗时。
final Node<K, V>[] resize() {
Node<K, V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 旧的扩充临界值
int oldThr = threshold;
// 新表newCap和新的扩充临界值newThr
int newCap, newThr = 0;
// 判断旧表的长度不为空
if (oldCap > 0) {
// 旧表大于最大容量返回就旧表
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
// 把新表的长度设置为旧表长度的两倍，newCap=2*oldCap
} 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);
}
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
table = newTab;
// 把原表中数据移动到新表中
if (oldTab != null) {
// 遍历原来的旧表数据
for (int j = 0; j < oldCap; ++j) {
Node<K, V> e;
// 判断node是都为空，将j的节点保存到e，然后把oldTab[j]置空，便于垃圾回收
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
// node上无链表直接替换
if (e.next == null)
/**
* 扩容前的元素地址为 (oldCap - 1) & e.hash,扩容后(newCap - 1)&e.hash
* 所以这里的新的地址只有两种可能，一是地址不变， 二是变为 老位置+oldCap
*/
newTab[e.hash & (newCap - 1)] = e;
// node上红黑树
else if (e instanceof TreeNode)
((TreeNode<K, V>) e).split(this, newTab, j, oldCap);
else { // preserve order
// loHead是用来保存新链表上的头元素的，loTail是用来保存尾元素的
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;
}
以上便是HashMap的扩容，相信大家看注释也能看明白，注释已经标示的很清晰了。接下我们看一下面试关于HashMap常见的几个问题
4.HashMap常见问题
4.1 HashMap内部数组长度为什么是2的幂次？
其实大体说有两点好处：
1.使用&能加快哈希计算。
2.减少哈希冲突。
我们都知道为了找到 key 的位置在哈希表的哪个槽里面，需要计算 hash(key) % length。但是% 计算比 & 慢很多。& 的计算结果等于 % 的结果需要把 length 减 1。所以使用hash&(length-1)。
减少哈希冲突的原因是length为2的幂指数时候，length-1必为奇数，奇数最后一位是1，这样便保证了hash&(length-1)最后一位可能是0或者1，这样&运算后的结果可能为偶数也可能是奇数，这样便保证散列的均匀性。举个例子
length=8,length-1=7,转化二进制0111，若此时有一个key的hash值是5，二进制也就是0101，那么0111&0101=0101 奇数位置 。另外一个key的hash值是6，二进制为0110，则0111&0110=0110偶数位置。所以，length取2的幂指数能较大的减少hash值的碰撞，使元素在哈希表中散布均匀。
4.2 HashMap的死循环问题
我们常说的HashMap造成死循环问题其实说的是jdk1.8之前版本，jdk1.8以及以后版本已经对其进行了优化。不会出现死循环 问题，只有可能出现数据丢失的情况，因为1.8版本中，会将原来的链表结构保存在节点e中，然后依次遍历e,根据hash&n是否等于0,分成两条支链，保存在新数组中。jdk1.7版本中，由于JDK1.7使用的是头插法（新的会插到链表头部），当一个线程resize完成，另一个线程未resize完成，连表会指向resize之后的链表，另一个线程的e.nxet()指向了前一个，导致了死循环。扩容过程中会新数组会和原来的数组有指针引用关系，所以将引起死循环问题。1.8版本中出现数据丢失主要原因其实是多线程下操作同一对象时，对象内部属性的不一致性导致的。分析方式跟为什么单例要使用双重锁check类似。
jdk1.7中造成死循环或者数据丢失，根源在与transfer函数
1 void transfer(Entry[] newTable, boolean rehash) {
2 int newCapacity = newTable.length;
3 for (Entry<K,V> e : table) {
4 while(null != e) {
5 Entry<K,V> next = e.next;
6 if (rehash) {
7 e.hash = null == e.key ? 0 : hash(e.key);
8 }
9 int i = indexFor(e.hash, newCapacity);
10 e.next = newTable[i];
11 newTable[i] = e;
12 e = next;
13 }
14 }
15 }
该函数的主要作用是将原来的数据移到newTable中，关键就是10到12行代码。使用头插法，就是链表的顺序会翻转，这也是造成死循环的关键点。
假设一个未resize的数据结构，初始化容量为4，负载因子0.8,原有机构
原始HashMap数据结构.png
当加入新元素时候，如果在单线程下，执行到最后的结果是
单线程扩容后HashMap的结构.png
然后我们比较一下在多线程情况下扩容方式，假设线程A和线程B同时进行put操作。线程A执行到transfer函数的第十一行: newTable[i] = e 挂起 ,此时线程A的运行结果是：
线程A挂起时HashMap结构.png
线程A挂起后，线程B正常执行，并且完成扩容操作。如下图
线程B扩容后HashMap结构.png
这里值得注意的是，由于线程B已经执行完了，根据Java内存模型。现在newTable和table中的Entry都是主内存中的最新值：11.next=3，3.next=null。
此时A获取时间碎片，开始执行,A线程内存中的值是：e=3, next=11,newTable[3]=null,代码执行如下
newTable[3]=e ; // newTable[3]=3
e=next; // e=11
因为主内存中11.next=3，此时的HashMap结构图
然后继续往下循环走
e=11
Entry<K,V> next = e.next; // next=3【主内存中取值】
e.next = newTable[3];// e.next=3【从主存中取值】
newTable[3]=e ;//newTable[3]=11
e=next;//e=3
此次循环结束后：11.next=3,结果如下：
接着我们继续循环
e=3
Entry<K,V> next = e.next; // next=null【主内存中取值】
e.next = newTable[3];// e.next=11【从主存中取值】
newTable[3]=e ;//newTable[3]=3
e=next;//e=null
此次循环完：3.next=11,出现了环形链表，并且此时e=null，循环已经结束。
线程A结束循环后HashMap死循环结构.png
在后续操作中只要涉及轮询hashmap的数据结构，就会在这里发生死循环，造成cpu 100%。
接下来说一下扩容造成的数据丢失。注意一下假设此时链表我3->7->11,结构如下：
原始HashMap结构.png
接着线程A和线程B进行put操作，同样挂起线程A时HashMap结构
线程A挂起时HashMap数据结构.png
此时线程B获取cpu时间，开始扩容完成
线程B扩容完成后HashMap数据结构.png
此时主内存值：
7.next=null;11.next=3;3.next=null
此时线程A获取cpu时间，线程A中HashMap数据结构为:
e=3 , next=7 , newTable[7]=0;
执行以下代码：
e=3；
newTable[i] = e; //newTabe[3]=3
e = next; // e=7
接着我们继续循环
e=7；
next=e.next ; //因为7.next=null ,所以next=null
newTable[i] = e; //newTabe[7]=7
e = next; // e=null 循环结束
此时HashMap数据结构是
将7放到newTable[7]=7，此时e=null,由此可以发现数据丢失11,而且还形成了环形链表，为后续操作造成死循环
jdk1.8进行了优化，不再采用头插法，而是直接插入链表底部，因此避免了环形链表，但是多线程仍然不安全，会造成数据丢失。主要原因是put操作的时候
// 如果计算出来的索引位置之前没有放过数据，即没有hash碰撞，就直接放入
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
假设线程A和线程B同时put操作，而且这个两个数据的hash值是相等的，即发生hash碰撞，此时该位置数据为null，所以线程A和B 都进入到
tab[i] = newNode(hash, key, value, null);
这一行。假设此时线程A挂起，线程B未挂起，线程B正常插入数据，然后cpu时间片切换到线程A,此时线程A已经不再进行hash判断了，直接就会把线程B原先的值给覆盖了。
如果要保证线程安全可以使用ConcurrentHashMap。
网友评论