这篇文章将为大家详细讲解有关基于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是如何扩容的
刚开始，阈值设定为空
当未声明的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;当数组为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的源码过程中，我看到了关于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 << 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
探究完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的身份。
关于“基于hashmap扩容和树形化的示例分析”这篇文章就分享到这里了，希望以上内容可以对大家有一定的帮助，使各位可以学到更多知识，如果觉得文章不错，请把它分享出去让更多的人看到。
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
