Java HashMap的原理、扩容机制、以及性能

Wesley13
• 阅读 927

Java HashMap

说明

此文档所介绍的HashMap是基于JDK1.8之后的。此文受到网上很多其他Java生态爱好者文章的影响,写此文的目的是系统的概括下HashMap,并把一些优秀文章的脉络连接起来起到目录作用。在此感谢优秀文章作者的启发,由于自身实力有限,若有纰漏之处还请评论指导。

原理(参考[1][3])

HashMap类似于HashTable,本质都是存储的键值对,也就是keyvaluekey用作存储初始索引,通过对其进行一系列运算把value映射存储到底层数据结构中。其存储的数据结构(JDK 1.8之后)如下:

  • 数据结构(引用[1]) Java HashMap的原理、扩容机制、以及性能

如上图所示,每个数组是有存储的是一个链表或者红黑树(视情况而定) * 数组 * 链表 * 红黑树

  • 存储过程

    • 对key进行hash运算,得到key的hash值。
    • 把key的hash值和hashMap的(length-1)进行&运算,得到index,index即为数据的索引下标,例如0,1,2,3。
    • 根据索引下标,把该Entry<key, value>存到对应的数据结构中。
      • 计算索引下标,也就是keyHash&(length-1)时,不同的keyHash会产生同样的索引下标,也就是说一个数组元素可能会存储多个数据;
      • 所以每个数组元素存储的是一个链表,当链表的长度超过TREEIFY_ THRESHOLD:8时,把链表改为红黑树。

    graph LR;   key-->|进行Hash运算|key的hash值;   key的hash值-->|和hashMap的length-1进行&运算|数组下标index;   数组下标index-->|根据index存储该Entry也就是key, value|该index的数组元素数据结构被更新:链表或者红黑树插入该Entry;

  • HashMap的阈值(参考[1])

    • DEFAULT INITIAL CAPACITY: 数组的初始容量,也就是默认会数组初始长度为16,长度不能太大或者太小。如果太小,很容易触发扩容,如果太大, 遍历HashMap会比较慢。值: 1<<4; //16

    • MAXIMUM CAPACITY: HashMap最大容量,一.般情况下只要内存够用,HashMap不会出现问题。值: 1<<30 (整数最大值的一半)

    • DEFAULT LOAD FACTOR: 默认的负载因子。因此初始情况下,当键值对的数量大于16 * 0.75 = 12时,就会触发扩容。值: 0.75f。

    • TREEIFY_ THRESHOLD: 如果哈希函数不合理,即使扩容也无法数组元素中链表的长度,因此Java 的处理方案是当链表太长 时,转换成红黑树。这个值表示当某个数组元素中,链表长度大于8时,有可能会转化成树。值: 8

    • UNTREEIFY _THRESHOLD: 在HashMap扩容时,如果发现链表长度小于6,则会由树重新退化为链表。值: 6

    • MIN_ TREEIFY_ CAPACITY: 在转变成树之前,还会有一次判断,只有键值对数量大于64才会发生转换。这是为了避免在HashMap建立初期,多 个键值对恰好被放入了同一个链表中而导致不必要的转化。值: 64

扩容(参考[2])

* 当元素超过数组长度的75%就会发生扩容,既长度增加一倍。
* 默认的数组长度```DEFAULT _INITIAL_ CAPACITY```=16,默认的负载因子```DEFAULT LOAD FACTOR```=0.75;当键值对数量超过16 * 0.75 = 12时,就会触发扩容导致数组长度变为16 * 2 = 32。

注意:扩容后,每个键值对数据存储的索引下标需要重新计算。通过公式:keyHash&(newLength-1)。结果会变成:newIndex = oldIndex + 扩容增加的长度

性能(参考[4])

  • 影响性能的因素

    • 存储长度(数组长度):需要为2的整数次幂,此文[5]已经详细解释,就不重复造轮子。
    • 扩容频率->负载因子:选择一个合适的负载因子,如果负载因子太小会导致扩容太频繁,从而导致性能损失。
  • 实践案例 文章[4]已经为我们很好地举了一个提高性能的实践案例。 ”比如说,我们有1000个元素new HashMap(1000), 但是理论上来讲new HashMap(1024)更合适,不过上面annegu已经说过,即使是1000,hashmap也自动会将其设置为1024。 但是new HashMap(1024)还不是更合适的,因为0.75*1000 < 1000, 也就是说为了让0.75 * size > 1000, 我们必须这样new HashMap(2048)才最合适,既考虑了&的问题,也避免了resize的问题。“

参考文章

点赞
收藏
评论区
推荐文章
blmius blmius
3年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
待兔 待兔
4个月前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
Jacquelyn38 Jacquelyn38
3年前
2020年前端实用代码段,为你的工作保驾护航
有空的时候,自己总结了几个代码段,在开发中也经常使用,谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
Stella981 Stella981
3年前
KVM调整cpu和内存
一.修改kvm虚拟机的配置1、virsheditcentos7找到“memory”和“vcpu”标签,将<namecentos7</name<uuid2220a6d1a36a4fbb8523e078b3dfe795</uuid
Easter79 Easter79
3年前
Twitter的分布式自增ID算法snowflake (Java版)
概述分布式系统中,有一些需要使用全局唯一ID的场景,这种时候为了防止ID冲突可以使用36位的UUID,但是UUID有一些缺点,首先他相对比较长,另外UUID一般是无序的。有些时候我们希望能使用一种简单一些的ID,并且希望ID能够按照时间有序生成。而twitter的snowflake解决了这种需求,最初Twitter把存储系统从MySQL迁移
Wesley13 Wesley13
3年前
00:Java简单了解
浅谈Java之概述Java是SUN(StanfordUniversityNetwork),斯坦福大学网络公司)1995年推出的一门高级编程语言。Java是一种面向Internet的编程语言。随着Java技术在web方面的不断成熟,已经成为Web应用程序的首选开发语言。Java是简单易学,完全面向对象,安全可靠,与平台无关的编程语言。
Stella981 Stella981
3年前
Django中Admin中的一些参数配置
设置在列表中显示的字段,id为django模型默认的主键list_display('id','name','sex','profession','email','qq','phone','status','create_time')设置在列表可编辑字段list_editable
Wesley13 Wesley13
3年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
Python进阶者 Python进阶者
10个月前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这