文章目录
前言
HashMap看过几次源码, 大致流程清楚, 但是有几个比较关键的点还是不太明白, 这次尝试比较彻底的搞明白这几个关键点:
- 1、散列函数
- 2、哈希冲突
- 3、扩容方案
一、HashMap初始化
1.1 tableSizeFor
public HashMap(int initialCapacity, float loadFactor) {
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
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;
}
总结: 经过一系列的右移、或运算, 将结果进行+1操作得到的最终结果比输入的initialCapacity大, 同时满足该结果是所有比initialCapacity大的数里面最小的2的整数次幂数.
二、HashMap.put
put方法分析时需要重点关注以下几个点:
- 1、hash值的计算
- 2、扩容
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
2.1 哈希函数
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
HashMap中的哈希桶使用Object key的hash值与哈希桶长度的计算结果作为索引值, 哈希值的计算如上面代码所示, 低16位与高16位进行异或运算.
先说结论: 一般的数组长度都会比较简短, 取模运算中只有低位参与散列, 高位与低位进行异或, 让高位得以参与散列运算, 使得散列更加均匀.
2.2 putVal计算索引值
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// hash与数组长度-1进行位与运算, 得到下标
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
}
直接盗图展示hash和[(n - 1) & hash]的计算过程
2.3 总结
结合上图可以知道, hash()中将高16位与低16位进行异或运算, 一个原因 也是为了让高16位参与到后边的散列计算, 2^15 = 32768, 实际情况中HashMap数组中并不会存这么多元素, 只有低位会参与散列运算.
因此先将高16位与低16位进行异或运算, 散列运算就会保证让高位也能够参与, 使得散列更加均匀.
三、数组扩容
3.1 putVal数组扩容
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {}
++modCount;
if (++size > threshold)
resize();
}
插入元素时 两处会执行扩容逻辑: 数组为空时、元素新增成功后. 第二处元素新增成功之后将size与threshold ( = 装载因子 * 数组长度) 进行比较, 满足条件之后进行数组扩容操作
3.2 resize数组扩容
resize数组扩容分为两部分: 1、创建新数组, 2、数组数据拷贝
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) {
// 1. 数组有数据时扩容
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 2. 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
// 3. 数组无数据时的初始化, 默认大小为16
newCap = DEFAULT_INITIAL_CAPACITY;
// 根据装载因子*数组大小 计算每次扩容临界值
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
}
总结:
- 1、无数据初始化数组, 容量默认16
- 2、有数据时数组扩容, 容量和扩容临界值均按2倍进行扩容
- 3、临界值 =
装载因子* 数组长度
3.3 loadFactor装载因子
- 1、装载因子的作用
- 2、装载因子为什么是0.75
3.1 装载因子的作用
HashMap有两个参数影响其性能: 初始化容量和装载因子. 装载因子 是哈希表在其容量自动扩容之前可以达到多满的一种度量. 当哈希表中的条目数超出了装载因子与当前容量的乘积时, 则要对该哈希表进行扩容、rehash操作.
装载因子需要在时间和空间成本上寻求一种折中.
-
1、装载因子过高:例如为1, 虽然减少了空间开销, 提高了空间利用率, 但是同时也增加了查询时间成本, 因为装载因子表示Hash表中元素的填满的程度, 装载因子越大, 填满的元素越多, 空间利用率就会越高, 但是冲突的机会加大了, 冲突的机会加大了, 同时HashMap解决哈希冲突用的是链地址法, 因此查询的成本会增加 - 2、装载因子过低: 例如为0.5, 虽然可以减少查询时间成本, 但是空间利用率很低, 同时提高了resize操作的次数(装载因子越小, 填满的元素越少, 冲突的机会越少).
3.2 为什么是0.75
在理想情况下, 使用随机哈希码, 节点出现的频率在hash桶中遵循泊松分布, 同时给出了桶中元素个数和概率的对照表.
从上面的表中可以看到当桶中元素达到8个时, 概率已经变得非常小, 也就是说用0.75作为装载因子, 每个碰撞位置的链表长度超过8个几乎是不可能的.
3.3 resize扩容时数组拷贝
final Node<K,V>[] resize() {
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 { // preserve order
/**
* 如果是以链表的方式存在, 根据e.hash与原长度进行位与运算, 将结果分为0和!0两种情况
* 按照0与!0将旧数组中每条链表一分为二: 低位链表与高位链表.
* 低位链表在新数组中的位置与旧数组一致;
* 高位链表在新数组中的位置 = 旧数组位置 + 旧数组长度
*/
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// 与数组长度进行位与运算, 如果是0, 归为低位链表
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// 如果是!0, 归为高位链表
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;
}
}
}
}
}
结合上图解释为什么2次幂扩容效率非常的高
// 扩容前
hash1.oldIndex = hash2.oldIndex = 15,
// 扩容后
hash1.newIndex = 31 = 15 + 16 = hash1.oldIndex + oldCap;
hash2.newIndex = 15 = hash2.oldIndex
在扩容时, 根据hash & oldCap计算结果0/!0, 将元素分为高/低位, 然后直接将元素放置在oldIndex/oldIndex + oldCap处, 即可满足newCap根据hash计算得到的索引值index.为何会出现这么巧的情况?
其实这并不是碰巧, 因为扩容是按照2次幂的方式进行的扩容.
index = hash & (cap - 1)
// 扩容前, 如果hash & oldCap = 0, 则说明hash值对应oldCap位的值为0, 即上图中的hash2
// 反之如果hash & oldCap = 1, 则说明hash值对应oldCap位的值为1, 即上图中的hash1
// 那么按照2次幂扩容之后
newCap - 1的高点值与oldCap是一致的.
// 因此以下运算式1与运算式2结果是一致的
(1) newIndex = hash & (newCap - 1);
(2) newIndex = oldCap + oldIndex;