HashMap源码刨析
Map接口的基于哈希表的实现。
官网解释
剖析解析
重点一
默认初始容量 (16) 和默认负载因子 (0.75) 的空HashMap,最大容量,在两个带参数的构造函数中的任何一个隐式指定更高的值时使用。 必须是 2 的幂 <= 1<<30 (1073741824)。
构造函数
/** |
核心函数put函数
put函数
/** |
为什么要右移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扩容函数(源码详解)
|
什么时候进行扩容?
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为空