TOP

HashMap原理(一) 概念和底层架构
2019-08-14 00:08:00 】 浏览:43
Tags:HashMap 原理 概念 底层 架构

我们从此处进入源码,逐步揭露HashMap


我们发现了两个变量loadFactor和DEFAULT_LOAD_FACTOR,从命名方式来看:因为没有接收到loadFactor参数,从而将某个默认值赋值给了loadFactor。这两变量到底是什么意思,还有无其他变量?


其实HashMap中定义的静态变量和成员变量很多,我们看一下


共有6个静态变量,都设置了初始值,且被final修饰,叫常量更合适,它们的作用其实也能猜出来,就是用于成员变量的默认值设定以及方法中相关的条件判断等情况。


共有6个成员变量,除这些成员变量外,还有一个重要概念capacity,我们主要说一下table,entrySet,capacity, size,threshold,loadFactor,我们我们简单解释一下它们的作用。


table变量为HashMap的底层数据结构,用于存储添加到HashMap中的Key-value对,是一个Node数组,Node是一个静态内部类,一种数组和链表相结合的复合结构,我们看一下Node类:


若以乘机做比喻的话,那么你买票的身份证号就是(key),通过hash算法生成的(hash)值就相当于值机后得到的航班座位号;你自己自然就是(value),你旁边的座位、人就是下一个Node(next);这样的一个座位整体(包括所坐人员及其身份证号、座位号)就是一个table,这许多的table的构建的Node[] table,就构成了本次航班任务。


那么为什么要用到数组和链表结合的数据结构?


我们知道数组和链表都有其各自的优点和缺点,数组连续存储,寻址容易,插入删除操作相对困难;而链表离散存储,寻址相对困难,而插入删除操作容易;而HashMap结合了这两种数据结构,保留了各自的优点,又弥补了各自的缺点,当然链表长度太长的话,在JDK8中会转化为红黑树,红黑树在后面的TreeMap章节在讲解。


HashMap的结构图如下:



怎么解释这种结构呢?


还是以乘机为例来说明,假如购票系统比较人性化并取消了值机操作,购票按照年龄段进行了区分,方便大家旅途沟通交流,于是20岁以下共6个人的分为了一组在20A~20F,20~30岁共6个人分为一组在21A~21F,30~40岁共6个人分为一组在22A~22F,40~50岁共6个人分为一组在23A~23F。


这时我们如果要找20几岁的小姐姐,我们很容易知道去21排找,从21A开始往下找,应该就能很快找到。


从数据的角度看,按年龄段分组(通过hash算法得到hash值,不同年龄段hash值不同,相同年龄段hash值相同)后,将各年龄段中第一个坐到座位上的人放到数组table中,下一个人来的时候,将第一个人往里面挪,自己在数组里,并将next指向第一个人。


entrySet变量为EntrySet实体,定义为变量可保证不重复多次创建,是一个Map.Entry的集合,Map.Entry<K,V>是一个接口,Node类就实现了该接口,因此EntrySet中方法需要操作的数据就是HashMap的Node实体。


capacity并不是一个成员变量,但HashMap中很多地方都会使用到这个概念,意思是容量,很好理解,在前面的文中提到了两个常量都与之相关


同时HashMap还具有扩容机制,容量的规则为2的幂次,即capacity可以是1,2,4,8,16,32...,怎么实现这种容量规则呢?


用该方法即可找到传递进来的容量的最近的2的幂次,即


cap = 2, return 2;


cap = 3, return 4;


cap = 9, return 16;


...


大家可以传递值进去自己算一下,先cap-1操作,是因为当传递的cap本身就是2的幂次情况下,假如为4,不减去一最后得到的结果将是传递的cap的2倍。


我们来一行行计算一下:tableSizeFor(11),按规则最后得到的结果应该是16


最终的结果正如预期,算法很牛逼啊,ヽ(ー_ー)ノ,能看懂,但却设计不出来。


size变量记录了Map中的key-value对的数量,在调用putValue()方法以及removeNode()方法时,都会对其造成改变,和capacity区分一下即可。


threshold为临界值,顾名思义,当过了临界值就需要做一些操作了,在HashMap中临界值“threshold = capacity * loadFactor”,当超过临界值时,HashMap就该扩容了。


loadFactor为装载因子,就是用来衡量HashMap满的程度,默认值为DEFAULT_LOAD_FACTOR,即0.75f,可通过构造器传递参数调整(0.75f已经很合理了,基本没人会去调整它),很好理解,举个例子:


本文主要讲解了HashMap中的一些主要概念,同时对其底层数据结构从源码的角度进行了分析,table是一个数据和链表的复合结构,size记录了key-value对的数量,capacity为HashMap的容量,其容量规则为2的幂次,loadFactor为装载因此,衡量满的程度,而threshold为临界值,当超出临界值时就会扩容。



HashMap原理(一) 概念和底层架构 https://www.cppentry.com/bencandy.php?fid=54&id=228505

】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇HashMap原理(二) 扩容机制及存取.. 下一篇红黑树(R-B tree)原理图文详解