纯净、安全、绿色的下载网站

首页|软件分类|下载排行|最新软件|IT学院

当前位置:首页IT学院IT技术

hashmap扩容和树形化 基于hashmap 的扩容和树形化全面分析

温柔的谢世杰   2021-06-10 我要评论
想了解基于hashmap 的扩容和树形化全面分析的相关内容吗温柔的谢世杰在本文为您仔细讲解hashmap扩容和树形化的相关知识和一些Code实例欢迎阅读和指正我们先划重点:hashmap扩容,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的身份以上为个人经验希望能给大家一个参考也希望大家多多支持


相关文章

猜您喜欢

  • Java 网络编程 详解Java网络编程

    想了解详解Java网络编程的相关内容吗laizhenghua在本文为您仔细讲解Java 网络编程的相关知识和一些Code实例欢迎阅读和指正我们先划重点:Java,网络编程,Java,Socket下面大家一起来学习吧..
  • Spring编程式事务 Spring源码解析之编程式事务

    想了解Spring源码解析之编程式事务的相关内容吗星夜孤帆在本文为您仔细讲解Spring编程式事务的相关知识和一些Code实例欢迎阅读和指正我们先划重点:Spring编程式事务的使用,什么是编程式事务,Spring事务下面大家一起来学习吧..

网友评论

Copyright 2020 www.fresh-weather.com 【世纪下载站】 版权所有 软件发布

声明:所有软件和文章来自软件开发商或者作者 如有异议 请与本站联系 点此查看联系方式