基于hashmap 的扩容和树形化全面分析
一、树形化
//链表转红黑树的阈值 static final int treeify_threshold = 8; //红黑树转链表的阈值 static final int untreeify_threshold = 6; /** *最小树形化容量阈值:即 当哈希表中的容量 > 该值时,才允许树形化链表 (即 将链表 转换成红黑树) *否则,若桶内元素太多时,则直接扩容,而不是树形化 *为了避免进行扩容、树形化选择的冲突,这个值不能小于 4 * treeify_threshold **/ static final int min_treeify_capacity = 64;
第一个和第二个变量没有什么问题,关键是第三个:是表示只有在数组长度大于64的时候,才能树形化列表吗?
实际上,这两个变量是应用于不同场景的。
链表长度大于8的时候就会调用treeifybin方法转化为红黑树,但是在treeifybin方法内部却有一个判断,当只有数组长度大于64的时候,才会进行树形化,否则就只是resize扩容。
为什么呢?
因为链表过长而数组过短,会经常发生hash碰撞,这个时候树形化其实是治标不治本,因为引起链表过长的根本原因是数组过短。执行树形化之前,会先检查数组长度,如果长度小于 64,则对数组进行扩容,而不是进行树形化。
所以发生扩容的时候是在两种情况下
超过阈值
链表长度超过8,但是数值长度不足64
二、扩容机制
hashmap内部创建过程
构造器(只是初始化一下参数,也就代表着只有添加数据的时候才会构建数组和链表)—调用put方法—put方法会调用resize方法(在数组为空或者超过阈值的时候,put方法调用resize方法)
hashmap是如何扩容的
1.hashmap中阈值threshold的设定
刚开始,阈值设定为空
当未声明的hashmap的大小的时候,阈值设定就是默认大小16*默认负载因子0.75=12
当声明hashmap的大小的时候,会先调用一个函数把阈值设定为刚刚大于设定值的2的次方(比如说设定的大小是1000,那阈值就是1024),然后在resize方法中,先把阈值赋给容量大小,然后在把容量大小*0.75在赋值给阈值。
代码如下:
node<k,v>[] oldtab = table; int oldcap = (oldtab == null) ? 0 : oldtab.length; int oldthr = threshold; int newcap, newthr = 0; if (oldcap > 0) { if (oldcap >= maximum_capacity) { threshold = integer.max_value; return oldtab; } 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;
2.数据转移
当数组为null的时候,会创建新的数组
当数组不为空,会把容量和阈值均*2,并创建一个容量为之前二倍的数组,然后把原有数组的数据都转移到新数组。
假设扩容前的 table 大小为 2 的 n 次方,元素的 table 索引为其 hash 值的后 n 位确定
扩容后的 table 大小即为 2 的 n+1 次方,则其中元素的 table 索引为其 hash 值的后 n+1 位确定,比原来多了一位
转移数据不在跟1.7一样重新计算hash值(计算hash值耗时巨大),只需要看索引中新增的是bit位是1还是0,
若为0则在新数组中与原来位置一样,
若为1则在新 原位置+oldcap 即可。
三、容量计算公式
扩容是一个特别耗性能的操作,所以当程序员在使用 hashmap 的时候,估算 map 的大小,初始化的时候给一个大致的数值,避免 map 进行频繁的扩容。
hashmap 的容量计算公式 :size/0.75 +1 。
原理就是保证,阈值(数组长度*0.75)>实际容量
hashmap的最大容量为什么是2的30次方(1左移30)?
在阅读hashmap的源码过程中,我看到了关于hashmap最大容量的限制,并产生了一丝疑问。
/** * the maximum capacity, used if a higher value is implicitly specified * by either of the constructors with arguments. * must be a power of two <= 1<<30. */ static final int maximum_capacity = 1 << 30;
为啥最大容量是 1 << 30?
探究过程1 – 为什么是30
首先是 << 这个操作符必须要理解,在一般情况下 1 << x 等于 2^x。这是左移操作符,对二进制进行左移。
来看1 << 30。它代表将1左移30位,也就是0010...0
来看这样一段代码:
public static void main(string[] args){ for (int i = 30; i <= 33; i++) { system.out.println("1 << "+ i +" = "+(1 << i)); } system.out.println("1 << -1 = " + (1 << -1)); }
输出结果为:
1 << 30 = 1073741824
1 << 31 = -2147483648
1 << 32 = 1
1 << 33 = 2
1 << -1 = -2147483648
结果分析:
- int类型是32位整型,占4个字节。
- java的原始类型里没有无符号类型。 -->所以首位是符号位 正数为0,负数为1
- java中存放的是补码,1左移31位的为 16进制的0x80000000代表的是-2147483648–>所以最大只能是30
探究过程2 – 为什么是 1 << 30
探究完1相信大家对 为什么是30有一点点了解。那为什么是 1 << 30,而不是0x7fffffff即integer.max_value
我们首先看代码的注释
/** * the maximum capacity, used if a higher value is implicitly specified * by either of the constructors with arguments. * must be a power of two <= 1<<30. */ static final int maximum_capacity = 1 << 30;
翻译一下大概就是:如果构造函数传入的值大于该数 ,那么替换成该数。
ok,我们看看构造函数的调用:
public hashmap(int initialcapacity, float loadfactor) { if (initialcapacity < 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); }
其中这一句:
if (initialcapacity > maximum_capacity) initialcapacity = maximum_capacity;
看到这有很有疑问了,如果我要存的数目大于 maximum_capacity,你还把我的容量缩小成 maximum_capacity???
别急继续看:在resize()方法中有一句:
if (oldcap >= maximum_capacity) { threshold = integer.max_value; return oldtab; }
在这里我们可以看到其实 hashmap的“最大容量“是integer.max_value;
总结
maximum_capacity作为一个2的幂方中最大值,这个值的作用涉及的比较广。其中有一点比较重要的是在hashmap中容量会确保是 2的k次方,即使你传入的初始容量不是 2的k次方,tablesizefor()方法也会将你的容量置为 2的k次方。这时候max_value就代表了最大的容量值。
另外还有一点就是threshold,如果对hashmap有一点了解的人都会知道threshold = 初始容量 * 加载因子。也就是扩容的 门槛。相当于实际使用的容量。而扩容都是翻倍的扩容。那么当容量到达maximum_capacity,这时候再扩容就是 1 << 31 整型溢出。
所以integer.max_value作为最终的容量,但是是一个threshold的身份。以上为个人经验,希望能给大家一个参考,也希望大家多多支持。