HashMap源码分析
2022-01-11 本文已影响0人
陈兄
HashMap源码刨析
Map接口的基于哈希表的实现。
官网解释
image
剖析解析
重点一
默认初始容量 (16) 和默认负载因子 (0.75) 的空HashMap,最大容量，在两个带参数的构造函数中的任何一个隐式指定更高的值时使用。 必须是 2 的幂 <= 1<<30 (1073741824)。
构造函数
/**
*最大容量，在两个带参数的构造函数中的任何一个隐式指定更高的值时使用。 必须是 2 的幂 <= 1<<30。
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 构造一个具有指定初始容量和负载因子的空HashMap 。
* 参数：
*
* initialCapacity – 初始容量
* loadFactor – 负载因子
* 抛出：
* IllegalArgumentException – 如果初始容量为负或负载因子为非正
*/
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;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
/**
* 实现了把一个数变为最接近的2的n次方
* 如果传入A，当A大于0，小于定义的最大容量时，
* 如果A是2次幂则返回A，否则将A转化为一个比A大且差距最小的2次幂。
* 例如传入7返回8，传入8返回8，传入9返回16
* cap=7 代码逻辑如下
* n|=n代表或运算 0对应0则是0 否则1
*/
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1; //n|(n>>>1) 6|6>>>1 00000110|00000110>>>1 00000110|00000011 =00000111 n=7
n |= n >>> 2; //n|(n>>>2) 7|7>>>2 00000111|00000111>>>2 00000111|00000001 =00000111 n=7
n |= n >>> 4; //n|(n>>>4) 7|7>>>4 00000111|00000111>>>4 00000111|00000000 =00000111 n=7
n |= n >>> 8; //n|(n>>>8) 7|7>>>8 00000111|00000111>>>8 00000111|00000000 =00000111 n=7
n |= n >>> 16;//n|(n>>>16) 7|7>>>16 00000111|00000111>>>16 00000111|00000000 =00000111 n=7
//(n < 0) =false
//(n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1
//(n >= 1<<30) n>=1073741824 = false
//false 得 n+1 = 8
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
核心函数put函数
put函数
/**
* put函数
*/
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* 获取hash值
*/
static final int hash(Object key) {
int h;
//^异或运算：相同置0，不同置1
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
为什么要右移16位?
- 保证高16位也参与计算， 我们直到int占4字节 32位，16是中位数
- 因为大部分情况下，都是低16位参与运算，高16位可以减少hash冲突
putVal函数
/**
* 表，在第一次使用时初始化，并根据需要调整大小。 分配时，长度始终是 2 的幂。 （我们还在某些操作中容忍长度为零，以允许当前不需要的引导机制。）
*/
transient Node<K,V>[] table;
/**
* 使用树而不是列表的 bin 计数阈值。 将元素添加到至少具有这么多节点的 bin 时，bin 会转换为树。 该值必须大于 2 且至少应为 8，以与树移除中关于在收缩时转换回普通 bin 的假设相匹配。
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* 创建新的node
*/
Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
return new Node<>(hash, key, value, next);
}
/**
* 参数：
* hash – 密钥的散列
* value – 要放置的值
* onlyIfAbsent – 如果为真，则不更改现有值
* evict – 如果为 false，则表处于创建模式。
* 返回：
* 以前的值，如果没有，则为 null
*/
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等于null或者tab长度为0 则调用resize()方法获取长度。
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//2、数组长度与计算得出的hash进行比较
if ((p = tab[i = (n - 1) & hash]) == null)//如果位置空，则将i位置值赋值给新的一个node对象
tab[i] = newNode(hash, key, value, null);
else {//3、位置不为空
Node<K,V> e; K k;
if (p.hash == hash &&//4、p旧节点与新添加元素完相同
((k = p.key) == key || (key != null && key.equals(k))))
e = p;//则将旧节点赋值给新节点
else if (p instanceof TreeNode)//5、如果p已经是树节点的一个实例，既这里已经是树了
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {//p旧节点与e新节点完全不相同，p也不是树节点treenode实例
for (int binCount = 0; ; ++binCount) {//死循环
if ((e = p.next) == null) {//e新节点=p旧节点.next下一个节点等于空
p.next = newNode(hash, key, value, null);//则赋值新的节点
if (binCount >= TREEIFY_THRESHOLD - 1) // 如果链表长度大于等于8
treeifyBin(tab, hash);//将链表转为红黑树
break;//跳出循环
}
//如果遍历过程中链表中的元素与新添加的元素完全相同，则跳出循环
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;//跳出循环
p = e;//则将遍历节点元素赋值给新节点
}
}
if (e != null) { //这个判断中代码作用为：如果添加的元素产生了hash冲突，那么调用
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)//如果元素数量大于临界值，则进行扩容
resize();
afterNodeInsertion(evict);
return null;
}
为什么会考虑红黑树？
链表过长则使用红黑树，提高查找效率。
HashMap链表转红黑树为什么是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
上面这段话的意思是，如果 hashCode 分布良好，也就是 hash 计算的结果离散好的话，那么红黑树这种形式是很少会被用到的，因为各个值都均匀分布，很少出现链表很长的情况。在理想情况下，链表长度符合泊松分布，各个长度的命中概率依次递减，当长度为 8 的时候，概率仅为 0.00000006。这是一个小于千万分之一的概率，通常我们的 Map 里面是不会存储这么多的数据的，所以通常情况下，并不会发生从链表向红黑树的转换。
此问题参考连接
resize扩容函数（源码详解）
//2的幂数
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//要调整大小的下一个大小值（容量 * 负载因子）。
int threshold;
final Node<K,V>[] resize() {
//主干table赋值给oldTab
Node<K,V>[] oldTab = table;
//获取原哈希表容量 如果哈希表为空则容量为0 ，否则为原哈希表长度
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//获取原生的扩容标准（容量16 * 负载因子0.75）
int oldThr = threshold;
//初始化新容量和新扩容门槛为0
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;//当容量超过最大值时，临界值设置成int最大值
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)//未达到1<<30，则进行扩容操作
newThr = oldThr << 1; // 容量扩充到2倍
}
else if (oldThr > 0) //不执行
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;//将新的临界值赋值给threshold
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;//新的数组赋值给table
//扩容后，重新计算元素新的位置
if (oldTab != null) {
//循环老的容量
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)
//当前index对应的节点为红黑树，当树的个数小于等于UNTREEIFY_THRESHOLD则转成链表
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
//分成两个链表，减少扩容的迁移量
//loHead，下标不变情况下的链表头
//loTail，下标不变情况下的链表尾
//hiHead，下标改变情况下的链表头
//hiTail，下标改变情况下的链表尾
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;
// 扩容长度为当前index位置+旧的容量
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
什么时候进行扩容？
hashMap中元素个数超过【数组长度（容量）*localFactor（负载因子）】时，就会进行数组扩容。
- localFactor（负载因子）默认0.75
- 容量默认16，也就是说0.7516=12，超过12，就会把数组大小扩容为212=32，扩容一倍。然后重新计算每个元素的仔数组中的位置。
扩容限制机制？
- 限制扩容大小不能大于1<<30（1073741824），最低16。
- 扩容倍数是最接近2的幂次，例如：new HashMap(13) 最终仍会是16长度。
步骤
1、定义了oldCap原table长度，newCap新table长度，newCap是oldCap的两倍。
2、循环原table，获取链上元素存入新table
3、计算新旧下标结果，要么相同，要么新下标=旧下标+旧小标数组长度。
hashMap是先插入还是先扩容？
1、初始容量，是先扩容在插入，后续就是先插入后扩容，因为resize()会进行新旧table做比较。
结合源码说说HashMap在高并发场景中为什么会出现死循环？
- jdk1.7，hashMap容量是有限的，高并发下，多元素插入，hashMap会达到一定的饱和程度。
- 就会进行resize扩容。
- 扩容后将rehash遍历数组数据，把所有的数据数据重新刷新到新数组。
jdk1.8的优化？
- JDK 8 中采用的是位桶 + 链表/红黑树的方式，当某个位桶的链表的长度超过 8 的时候，这个链表就将转换成红黑树。
HashMap和HashTable有何不同？
- hashMap适合单线程，允许key/value为空
- hashTable适合多线程，不许key/value为空
