HashMap源码解读——创建与扩容
文章目录
有了解过HashMap的同学们应该都清楚,在JDK1.8中HashMap的底层数据结构其实是数组+链表+红黑树,既然是数组,那么必然存在扩容的问题,那么想创建一个容量合理,性能较高HashMap自然需要了解其创建方法及扩容机制,那么本文会基于1.8.0_91的源码粗略的解析一下创建与扩容,分享给大家,如果有解析错误的地方欢迎大家解析讨论。
首先大致的描述创建与扩容是怎样实现的
当我们在new 一个HashMap的时候其实并没有真正的在底层创建了什么东西,真正的创建是在put方法中实现的,new的这个过程只是初始化了一些相关变量的值,这些变量包括一下几个
//哈希桶数组
transient Node<K,V>[] table;
//默认的HashTable的长度,默认为16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//负载系数
final float loadFactor;
//默认的负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//临界值
int threshold;
//已使用容量
transient int size;
创建一个HashMap对象的第一步是是创建一个哈希桶数组(table)既然创建的是数组那么就需要在创建是指定其长度,当我们使用的是空参构造函数是,数组使用的就是默认的长度DEFAULT_INITIAL_CAPACITY = 16,使用带参数的构造函数那么长度就是大于或等于该参数的最小的2次幂(例如我传的是31,那么创建出来的哈希桶数组长度就是大于31的2^5,即为32)。初始化过后当里面的存放对象过多时,就会出现越来越多的哈希冲突,影响HashMap的查询插入效率,这个时候就需要扩容,使得HashMap有越多的Hash槽来减少哈希冲突,提高效率,但是我们知道扩容是非常消耗内容的,所以频繁的扩容也是不可行的。那么什么时候需要扩容呢?HashMap在设计上已经考虑了这一点,扩容的时机就是在达到当内部存放的元素数量(size)达到临界值时(threshold),那么HashTable就会进行扩容,临界值 = 哈希桶长度 x 负载因子(loadFactor)。了解了这些基本的变量也就粗略了解了HashMap的扩容原理,我们接下来跟着源码深入刨析一下其实现。
以下是构造函数源码
//核心构造函数
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
//初始容量小于0异常
throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
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);
}
//含容量构造函数
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//空参构造函数
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
//复制初始化
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
比较常见的问题是:获取大于或等于一个数的最小2的幂即tableSizeFor()方法是如何实现的?
源码如下:
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;
}
首先分析 n |= n >>> x 这个就是把一个数或该数无符号右移x位的值,上面这个代码达到的效果如下
01 00000 00000 00000 00000 00000 00000 (n)
01 10000 00000 00000 00000 00000 00000 (n |= n >>> 1)
01 11100 00000 00000 00000 00000 00000 (n |= n >>> 2)
01 11111 11000 00000 00000 00000 00000 (n |= n >>> 4)
01 11111 11111 11111 00000 00000 00000 (n |= n >>> 8)
01 11111 11111 11111 11111 11111 11111 (n |= n >>> 16)
其实目的就是让n的二进制最高位之后所有的位上都是1,最后算出来+1 ,所有位进1,得到的结果就是最高为是1其他都为0的数,这样的数就是2的n次方,也是最接近n的2的幂。
接着为什么要cap - 1呢?
是因为如果传进来的数就是2的n次方,那么默认值就应该是2的n次方,不减一的话那么按上述运算出来就变成了2的(n+1)次方。
例如传进来是32,那么减一之后计算出来是32,不减一算出来的结果是64。
讲解完构造函数接下来就是扩容的resize()函数
final Node<K,V>\[\] resize() {
//由于初始化是调用的也是resize方法所table 可能为空
Node<K,V>\[\] oldTab = table;
//获取旧Hash桶长度
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//获取旧负载临界值
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
//已初始化,map是扩容
//旧Hash桶已到最大长度无法扩容,则将负载临界值设置到最大,返回旧的Hash桶
if (oldCap >= MAXIMUM\_CAPACITY) {
threshold = Integer.MAX\_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM\_CAPACITY && oldCap >= DEFAULT\_INITIAL\_CAPACITY)
//2倍当前容量<最大容量且原容量大于默认初始容量,则进行扩容至之前的2倍(<<1 = \\\*2)
newThr = oldThr << 1; // double threshold
}else if (oldThr > 0)
//未初始化,oldThr只在带有参数的Map构造函数中有定义
//如果指定了初始容量参数作为容量则Hash会选择一个大于或等于该数字的第一2的幂作为容量,在构造函数逻辑中已完成
newCap = oldThr;
else {
//未初始化,无参构造行数,按默认的数据进行参数
newCap = DEFAULT\_INITIAL\_CAPACITY;
newThr = (int)(DEFAULT\_LOAD\_FACTOR \* DEFAULT\_INITIAL\_CAPACITY);
}
if (newThr == 0) {
/*
根据上面的逻辑,有两种情况newThr是0
1.扩容,且容量大于16
2.无参构造函数初始化
*/
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 = newTab;
//以上完成新建,非扩容返回newTab初始化完成
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)
((TreeNode<K,V\\>)e).split(this, newTab, j, oldCap);
else { // preserve order
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;
}
JDK1.7之前,扩容时都会rehash,Jdk1.8之后对这个点进行了优化
//原位置链表
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;
//新链表hash槽为原为+原hashtable长度
newTab[j + oldCap] = hiHead;
}
看了述代码就会产生一个问题:(e.hash & oldCap) == 0为什么能判断是否需要改变位置?
假设:计算hashtbale槽位时算法 e.hash & (newCap - 1),那么我们以16扩容至32为例
扩容前:
16 0000 0000 0000 0000 0000 0000 0001 0000
16-1=15 0000 0000 0000 0000 0000 0000 0000 1111
hash1 1111 1111 1111 0000 1111 0000 0000 1010
hash2 1111 1111 1111 0000 1111 0000 0001 1010
hash1:
&(newCap - 1) 结果 :1010 =10
&newCap 结果 :0
hash2:
&(newCap - 1) 结果 :1010 =10
&newCap 结果 :0001 0000
所以hash1,hash2 &15的结构是一样的在同一个hash槽中。
扩容后:
32 0000 0000 0000 0000 0000 0000 0010 0000
32-1=31 0000 0000 0000 0000 0000 0000 0001 1111
hash1 1111 1111 1111 0000 1111 0000 0000 1010
hash2 1111 1111 1111 0000 1111 0000 0001 1010
hash1:
&(newCap - 1) 结果 :1010 =10
&newCap 结果 :0
hash2:
&(newCap - 1) 结果 :0001 1010 =26 = 10+16 = 原位置+oldCap
&newCap 结果 :0001 0000
因为扩容后本来只取4位计算变成了五位。所以rehash的结果是两种,一种是在原位子,还有一种在原位置+oldCap。所以我们只需要对hash结果在新位置上的key进行rehash计算。那么可以根据(e.hash & oldCap) == 0则说明e.hash最高位是左边一位是0,所以 e.hash & newCap-1的结果与e.hash & oldCap-1的结果是相等的。(e.hash & oldCap) != 0则说明最高位是左边一位是1,则原位置+oldcap
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论