基于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的身份。以上为个人经验,希望能给大家一个参考,也希望大家多多支持我们。

时间: 2021-06-08

java HashMap扩容详解及实例代码

HashMap扩容 前言: HashMap的size大于等于(容量*加载因子)的时候,会触发扩容的操作,这个是个代价不小的操作. 为什么要扩容呢?HashMap默认的容量是16,随着元素不断添加到HashMap里,出现hash冲突的机率就更高,那每个桶对应的链表就会更长, 这样会影响查询的性能,因为每次都需要遍历链表,比较对象是否相等,一直到找到元素为止. 为了提升查询性能,只能扩容,减少hash冲突,让元素的key尽量均匀的分布. 扩容基本点 加载因子默认值是0.75 static final

HashMap原理的深入理解

hashing(散列法或哈希法)的概念 散列法(Hashing)是一种将字符组成的字符串转换为固定长度(一般是更短长度)的数值或索引值的方法,称为散列法,也叫哈希法.由于通过更短的哈希值比用原始值进行数据库搜索更快,这种方法一般用来在数据库中建立索引并进行搜索,同时还用在各种解密算法中. HashMap概念和底层结构 HashMap是基于哈希表的Map接口的非同步实现.此实现提供所有可选的映射操作,并允许使用null值和null键.HashMap储存的是键值对,HashMap很快.此类不保证映射

ArrayList及HashMap的扩容规则讲解

1.ArrayList 默认大小为10 /** * Default initial capacity. */ private static final int DEFAULT_CAPACITY = 10; 最大容量为2^30 - 8 /** * The maximum size of array to allocate. * Some VMs reserve some header words in an array. * Attempts to allocate larger arrays m

ArrayList和HashMap如何自己实现实例详解

 ArrayList和HashMap ArrayList的存储就是一个数组, HashMap的存储是一个数组加一个链表, 以下实现的MyArrayList及MyHashMap,在实际的工作中都是用不上的,最有可能用得到的地方就是面试找工作以及忽悠别人了.工作中虽然用不上,但是并不代表没有用,它可以帮助我们去理解他们的实现原理,等实现完后再去仔细查看JDK中的源码,就会发现别人实现当中那些可供学习的地方. MyArrayList public class MyArrayList<E> { pri

mocha的时序规则讲解

前言 对于新手而言,mocha的时序就像谜一般,许多奇怪的测试样例的失败都是由于对时序不清楚.下面我就把我在测试工作中总结的时序规则部分与大家共享. describe里地时序 simple case describe('work',function(){ it('1',func(){}); it('2',func(){}); .... }); //按1,2,3...顺序执行 规则1:describe里地it的非异步部分按它们定义的顺序执行,它们所触发的回调的注册顺序也遵从it的注册顺序 hook

Lambda表达式和Java集合框架

本文github地址 Java8为容器新增一些有用的方法,这些方法有些是为完善原有功能,有些是为引入函数式编程(Lambda表达式),学习和使用这些方法有助于我们写出更加简洁有效的代码.本文分别以ArrayList和HashMap为例,讲解Java8集合框架(Java Collections Framework)中新加入方法的使用. 前言 我们先从最熟悉的Java集合框架(Java Collections Framework, JCF)开始说起. 为引入Lambda表达式,Java8新增了jav

分析Java中ArrayList与LinkedList列表结构的源码

一.ArrayList源码分析(JDK7) ArrayList内部维护了一个动态的Object数组,ArrayList的动态增删就是对这个对组的动态的增加和删除. 1.ArrayList构造以及初始化 ArrayList实例变量 //ArrayList默认容量 private static final int DEFAULT_CAPACITY = 10; //默认空的Object数组, 用于定义空的ArrayList private static final Object[] EMPTY_ELE

JAVA开发中的一些规范讲解(阿里巴巴Java开发规范手册)

一.编程规约 (一) 命名规约 1.   [强制]所有编程相关命名均不能以下划线或美元符号开始,也不能以下划线或美元符号结束.反例: _name / __name / $Object / name_ / name$ / Object$ 2.   [强制]所有编程相关的命名严禁使用拼音与英文混合的方式,更不允许直接使用中文的方式.说明:正确的英文拼写和语法可以让阅读者易于理解,避免歧义.注意,即使纯拼音命名方式也要避免采用. 反例: DaZhePromotion [打折] / getPingfen

深入理解Java之HashMap源码剖析

一.HashMap概述 HashMap基于哈希表的 Map 接口的实现.此实现提供所有可选的映射操作,并允许使用 null 值和 null 键.(除了不同步和允许使用 null 之外,HashMap 类与 Hashtable 大致相同.)此类不保证映射的顺序,特别是它不保证该顺序恒久不变. 值得注意的是HashMap不是线程安全的,如果想要线程安全的HashMap,可以通过Collections类的静态方法synchronizedMap获得线程安全的HashMap. Map map = Coll

深入解析java HashMap实现原理

Mark一下,同时可以很好的结合hashCode()和equals()方法,覆盖equals方法时最好覆盖hashcode(),保证equals的两个对象,hashcode也相等,反过来:hashcode()不等,一定能推出equals()也不等:hashcode()相等,equals()可能相等,也可能不等. 因为HashMap在get时,先比较hashcode,再比较equals,hashcode==&&equals,两者都为true,则认为是相同的key 1.    HashMap概

全面解析Java中的HashMap类

HashMap 和 HashSet 是 Java Collection Framework 的两个重要成员,其中 HashMap 是 Map 接口的常用实现类,HashSet 是 Set 接口的常用实现类.虽然 HashMap 和 HashSet 实现的接口规范不同,但它们底层的 Hash 存储机制完全一样,甚至 HashSet 本身就采用 HashMap 来实现的. 实际上,HashSet 和 HashMap 之间有很多相似之处,对于 HashSet 而言,系统采用 Hash 算法决定集合元素

Java集合系列之ArrayList源码分析

本篇分析ArrayList的源码,在分析之前先跟大家谈一谈数组.数组可能是我们最早接触到的数据结构之一,它是在内存中划分出一块连续的地址空间用来进行元素的存储,由于它直接操作内存,所以数组的性能要比集合类更好一些,这是使用数组的一大优势.但是我们知道数组存在致命的缺陷,就是在初始化时必须指定数组大小,并且在后续操作中不能再更改数组的大小.在实际情况中我们遇到更多的是一开始并不知道要存放多少元素,而是希望容器能够自动的扩展它自身的容量以便能够存放更多的元素.ArrayList就能够很好的满足这样的