看完这篇还不懂HashMap的扩容机制,那我要哭了~(1)-阿里云开发者社区

开发者社区> 沉默王二> 正文

看完这篇还不懂HashMap的扩容机制,那我要哭了~(1)

简介: 看完这篇还不懂HashMap的扩容机制,那我要哭了~
+关注继续查看

HashMap 发出的 Warning:这是《Java 程序员进阶之路》专栏的第 56 篇。那天,小二垂头丧气地跑来给我诉苦,“老王,有个学弟小默问我‘ HashMap 的扩容机制’,我愣是支支吾吾讲了半天,没给他讲明白,讲到最后我内心都是崩溃的,差点哭出声!”


我安慰了小二好一会,他激动的情绪才稳定下来。我给他说,HashMap 的扩容机制本来就很难理解,尤其是 JDK8 新增了红黑树之后。先基于 JDK7 讲,再把红黑树那块加上去就会容易理解很多。


小二这才恍然大悟,佩服地点了点头。


HashMap 发出的呼声:有 GitHub 账号的小伙伴记得去安排一波 star 呀,《Java 程序员进阶之路》开源教程目前在 GitHub 上有 244 个 star 了,准备冲 1000 了,求求各位了。


GitHub 地址:https://github.com/itwanger/toBeBetterJavaer

在线阅读地址:https://itwanger.gitee.io/tobebetterjavaer

大家都知道,数组一旦初始化后大小就无法改变了,所以就有了 ArrayList这种“动态数组”,可以自动扩容。


HashMap 的底层用的也是数组。向 HashMap 里不停地添加元素,当数组无法装载更多元素时,就需要对数组进行扩容,以便装入更多的元素。


当然了,数组是无法自动扩容的,所以如果要扩容的话,就需要新建一个大的数组,然后把小数组的元素复制过去。


HashMap 的扩容是通过 resize 方法来实现的,JDK 8 中融入了红黑树,比较复杂,为了便于理解,就还使用 JDK 7 的源码,搞清楚了 JDK 7 的,我们后面再详细说明 JDK 8 和 JDK 7 之间的区别。


resize 方法的源码:


// newCapacity为新的容量
void resize(int newCapacity) {
    // 小数组,临时过度下
    Entry[] oldTable = table;
    // 扩容前的容量
    int oldCapacity = oldTable.length;
    // MAXIMUM_CAPACITY 为最大容量,2 的 30 次方 = 1<<30
    if (oldCapacity == MAXIMUM_CAPACITY) {
        // 容量调整为 Integer 的最大值 0x7fffffff(十六进制)=2 的 31 次方-1
        threshold = Integer.MAX_VALUE;
        return;
    }
    // 初始化一个新的数组(大容量)
    Entry[] newTable = new Entry[newCapacity];
    // 把小数组的元素转移到大数组中
    transfer(newTable, initHashSeedAsNeeded(newCapacity));
    // 引用新的大数组
    table = newTable;
    // 重新计算阈值
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}



代码注释里出现了左移(<<),这里简单介绍一下:


a=39

b = a << 2



十进制 39 用 8 位的二进制来表示,就是 00100111,左移两位后是 10011100(低位用 0 补上),再转成十进制数就是 156。


移位运算通常可以用来代替乘法运算和除法运算。例如,将 0010011(39)左移两位就是 10011100(156),刚好变成了原来的 4 倍。


实际上呢,二进制数左移后会变成原来的 2 倍、4 倍、8 倍。


transfer 方法用来转移,将小数组的元素拷贝到新的数组中。


void transfer(Entry[] newTable, boolean rehash) {
    // 新的容量
    int newCapacity = newTable.length;
    // 遍历小数组
    for (Entry<K,V> e : table) {
        while(null != e) {
            // 拉链法,相同 key 上的不同值
            Entry<K,V> next = e.next;
            // 是否需要重新计算 hash
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            // 根据大数组的容量,和键的 hash 计算元素在数组中的下标
            int i = indexFor(e.hash, newCapacity);
            // 同一位置上的新元素被放在链表的头部
            e.next = newTable[i];
            // 放在新的数组上
            newTable[i] = e;
            // 链表上的下一个元素
            e = next;
        }
    }
}



e.next = newTable[i],也就是使用了单链表的头插入方式,同一位置上新元素总会被放在链表的头部位置;这样先放在一个索引上的元素终会被放到链表的尾部(如果发生了hash冲突的话),这一点和 JDK 8 有区别。


在旧数组中同一个链表上的元素,通过重新计算索引位置后,有可能被放到了新数组的不同位置上(仔细看下面的内容,会解释清楚这一点)。


假设 hash 算法(之前的章节有讲到,点击链接再温故一下)就是简单的用键的哈希值(一个 int 值)和数组大小取模(也就是 hashCode % table.length)。


继续假设:


数组 table 的长度为 2

键的哈希值为 3、7、5

取模运算后,哈希冲突都到 table[1] 上了,因为余数为 1。那么扩容前的样子如下图所示。


image.png


小数组的容量为 2, key 3、7、5 都在 table[1] 的链表上。


假设负载因子 loadFactor 为 1,也就是当元素的实际大小大于 table 的实际大小时进行扩容。


扩容后的大数组的容量为 4。


key 3 取模(3%4)后是 3,放在 table[3] 上。

key 7 取模(7%4)后是 3,放在 table[3] 上的链表头部。

key 5 取模(5%4)后是 1,放在 table[1] 上。


image.png


按照我们的预期,扩容后的 7 仍然应该在 3 这条链表的后面,但实际上呢? 7 跑到 3 这条链表的头部了。针对 JDK 7 中的这个情况,JDK 8 做了哪些优化呢?


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
使用NAT网关轻松为单台云服务器设置多个公网IP
在应用中,有时会遇到用户询问如何使单台云服务器具备多个公网IP的问题。 具体如何操作呢,有了NAT网关这个也不是难题。
26742 0
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
9497 0
阿里云服务器ECS远程登录用户名密码查询方法
阿里云服务器ECS远程连接登录输入用户名和密码,阿里云没有默认密码,如果购买时没设置需要先重置实例密码,Windows用户名是administrator,Linux账号是root,阿小云来详细说下阿里云服务器远程登录连接用户名和密码查询方法
11214 0
windows server 2008阿里云ECS服务器安全设置
最近我们Sinesafe安全公司在为客户使用阿里云ecs服务器做安全的过程中,发现服务器基础安全性都没有做。为了为站长们提供更加有效的安全基础解决方案,我们Sinesafe将对阿里云服务器win2008 系统进行基础安全部署实战过程! 比较重要的几部分 1.
9055 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
13186 0
阿里云ECS云服务器初始化设置教程方法
阿里云ECS云服务器初始化是指将云服务器系统恢复到最初状态的过程,阿里云的服务器初始化是通过更换系统盘来实现的,是免费的,阿里云百科网分享服务器初始化教程: 服务器初始化教程方法 本文的服务器初始化是指将ECS云服务器系统恢复到最初状态,服务器中的数据也会被清空,所以初始化之前一定要先备份好。
6895 0
阿里云服务器ECS登录用户名是什么?系统不同默认账号也不同
阿里云服务器Windows系统默认用户名administrator,Linux镜像服务器用户名root
4013 0
+关注
沉默王二
微信搜索「沉默王二」,回复关键字「00」获取硬核计算机基础资料。
1084
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载