细节决定成败 一文逐行解读HashMap源码

时间:2020-02-04 来源:www.ican-cintest.com

所有这些“集合视图方法”返回的迭代器都很快失败:迭代器创建后,如果映射在结构上被修改,迭代器将抛出并发修改异常,除非它在任何时候通过迭代器自己的移除或添加方法被修改。因此,面对并发修改,迭代器将很快完全失败,而不会在未来不确定的时间冒任何不确定行为的风险。

注意迭代器的快速失败行为无法保证。一般来说,当有异步并发修改时,不可能做出任何可靠的保证。快速失败迭代器尽最大努力抛出并发异常。因此,编写依赖于这个异常的程序是错误的。正确的方法是迭代器的快速失败行为应该只用于检测程序错误。

该类是Java集合框架的成员。

3。HashMap存储结构

在学习源代码之前,最好在头脑中弄清楚HashMap的存储结构。否则,当您稍后阅读源代码并遇到容量和数量等参数时,您可能会有点困惑。

我相信你已经听说了,哈希表包含一个节点类型的数组表。节点存储键值对。

节点类的源代码如下:

它包含四个字段。我们可以从下一个字段中看到节点是一个链表。也就是说,数组中的每个位置都被视为一个存储桶,每个存储桶存储一个链表。哈希映射(HashMap)使用链地址方法来解决哈希冲突,即具有相同哈希值的节点存储在同一链表中,哈希桶模运算的结果相同。哈希表存储结构如下图所示:

4,哈希表静态属性

static final int default _ initial _ capacity=14;//又名16

默认表容量,14=2 4=16,必须是2的幂。

静态最终int MAXIM _ CAPITION=1 30;

最大表容量必须是2的幂,键入int,用手指计数,只能是。因为在Java中int有32位,除了第一位的符号位,只有31位和130位满足条件。

这里需要解释的是,对于2的幂,在计算机世界中存在一个特殊的群体。它们的二进制只有一个1,其余的位都是0。该特性将影响钻头的使用效果,并具有一些特殊效果。

静态最终浮点DEFAULT _ LOAD _ FACTOR=0.75f

构造函数中未指定时要使用的加载因子。

静态最终int TREEIFY _ THreshold=8;

我相信很多人都知道,如果链表长度大于8,根据这个字段的注释,它将变成一棵红黑树。但事实上这只是条件之一,另一个条件是以下参数。

静态最终int MIN _ TREEIFY _ CAPACITY=64

将链表转换为红黑树时,第一步是检查链表的长度是否大于或等于8。第二步是检查表数组的容量是否小于该值。如果小于该值,则取消到红黑树的转换,仅执行表数组的扩展。

静态最终int UNTRIIFY _ THreshold=6;

当键值对太多时,需要扩展表数组,并将每个键值对放入一个新的存储桶中(或者不进行更改)。原始桶的内部结构可以是链表或红黑树。经过一些洗牌后,如果桶结构中键值对的数量对于红黑树来说太低,它将再次转换为链表。它有多低?这是这个字段的大小。

V. HashMap成员属性

瞬态节点[]表;

HashMap的内部节点类型数组,带有属性名称表。

瞬态int modCount

此字段用作标记。该值是对哈希表进行结构修改的次数。它主要用于检测哈希映射的内部机制是否由于迭代器访问期间的删除等其他操作而发生了变化。

瞬态集熵集;

HashMap有许多内部类,这些类扩展了HashMap的一些功能。EntrySet类就是其中之一。这个类相对简单,没有内部属性。你可以把它理解为一个工具类。哈希表被简单封装,提供了方便的遍历和删除操作。

调用哈希映射的entrySet()方法返回EntrySet实例对象。为了不在每次调用方法时都返回新的EntrySet对象,请设置此属性并缓存EntrySet实例。

瞬态int大小;

键值对的数量。

int阈值;

size的临界值,当大小为

由final修改的负载系数在构造方法中初始化,默认情况下不指定而使用。

6。HashMap构造方法

HashMap有三种构造方法。源代码如下:

PublicHashMap(){

this . load factor=default _ load factor;//所有其他字段默认

公共哈希表(int IniticalCapacity){

此(IniticalCapacity,DEFAULT _ LOAD _ FACTOR);

公共哈希表(初始容量,浮动负载系数){

如果(初始容量0)

抛出新的非法初始容量: '

初始容量);

如果(初始容量最大_容量)

初始容量=最大_容量;

如果(负载系数=0 || Float.isNaN(负载系数))

抛出新的IllegalArgumentException(“非法负载系数:”

负载系数);

this.loadFactor=loadFactor

this.threshold=tableSizeFor(初始容量);

首先查看源代码,我们会发现final修改的loadFactor肯定会在构造方法中初始化。

带参数的施工方法主要是验证初始承载力和荷载系数,并通过表大小法计算其合理的初始承载力。由于此时表数组尚未实例化,因此合理的初始容量暂时存储在threshold属性中并由它保存。

7。表大小(int cap)方法

表大小(int cap)静态方法(Static Method)用于计算其合理的初始容量,即满足2的幂,且大于或等于参数cap,即最接近的数。该方法使用位操作来设计高效的算法逻辑,其源代码如下:

static final int tablesize for(int cap){

int n=cap-1;

n |=n1;

n |=N2;

n |=n ^ 4;

n |=n 8;

n |=n 16

return(n ^ 0)?1 :(n=最大容量)?最大容量: n1;

参数cap的值肯定大于0,因此n大于或等于0。假设n=0,右移后,它仍然是0,0和0的异或仍然是0。1,即2的0的幂,由返回语句的n 1计算。

当n大于0时,n的二进制位肯定会有1的值,即001xx的形式.xx。然后,向右移动1位,获得0001xx.xx,并执行位或。因为1和0或1的异或结果是1,结果必须是0011xx的形式.xx。类似地,移位2位、4位、8位和16位,最后算法可以将最高位的1之后的所有位改变为1。

让我们举一个图片的例子:

算法的最终结果是n 1,结果是2的整数次方。为了使结果大于或等于参数cap,在算法开始时进行cap-1。

八。哈希(对象键)方法

该方法是哈希映射的核心静态方法,用于计算键的哈希值。此方法的源代码如下:

静态最终Inthis(object Key){

Inthis;

return (key==null)?^(h16);

方法逻辑简单。键为null,返回0。根据桶下标计算公式(capacity-1)的散列0和0或1位,结果都是0,可以看出对应于空键的桶下标是0。

当密钥不为空时,调用key.hashCode()并将hashCode的低16位与高16位进行异或运算。

此操作是因为表数组使用2的幂作为容量,并且计算桶下标是通过(capacity-1)散列的,所以只在当前容量以上的位中改变的散列码总是冲突的。

例如,初始容量是16,哈希值是按32位计算的。

16=(二进制)

16-1=0000 0000 0000 0000 0000 0000 111

has h1=0000 0000 0000 0000 0000 0001 111

has 2=000 000 000 000 000 000 000 000 000 000 000

has 2=000 000 000 000 000 111如果哈希值仅在前32-4=28位发生变化,则计算结果是相同的,并将被放入同一个桶中,冲突将始终发生。

因此,设计者在平衡速度、实用性和位扩展质量之后应用了一种变换,通过异或哈希值的低16位和高16位来向下扩展高位的影响。

由于许多常见的哈希值已经被合理地分配(例如,哈希值的前16位都是一些0的数字,并且它们的低16位和高16位在异或之后没有改变,因此它们不能从扩展中受益),并且因为我们使用树来处理容器中的大量冲突, 我们只以最方便的方式异或一些移位的位,以减少系统损耗并合并最高位的影响,否则,由于表数组容量的限制,这些位将永远不会用于索引计算。

九。桶下标计算公式

计算桶下标时,需要通过哈希映射(HashMap)内部的哈希()方法计算桶下标的哈希值,然后将哈希值模数化为桶数,即

hash% capacity

如果容量可以保证为2的幂,那么这个运算就可以转换成高效的位运算。也就是说,HashMap源代码中计算桶下标的公式:

(capacity-1) hash

或以上是HashMap内部数组的容量是2的幂的原因之一,另一个原因是桶下标可以在resize()扩展方法中更有效地重新计算。

x. put(K键,V值)方法

此方法将指定值与映射中的指定键相关联。如果密钥已经存在,覆盖并返回旧值(可以为空);如果没有键值对映射,则返回null。此方法的源代码如下:

publicvput (kkey,vvalue) {

returnputval (hash (key),key,value,false,true);

如您所见,这个方法实际上是封装的putVal()方法。putVal()方法有五个参数,它们是键的哈希值、键本身、值本身和onlyIfAbsent参数,指示当键已经存在时是否放弃覆盖旧值。参数逐出,作为afterNodeInsertion(逐出)方法的参数,不被HashMap使用,而是由LinkedHashMap处理。

这个方法的源代码如下:

XI。resize()方法

此方法的功能是初始化表数组或增加表数组的大小。

如果表数组为空,分配将基于字段阈值中维护的初始容量。否则,将进行扩展,因为我们使用2的幂,所以每个桶中的元素必须保持相同的索引,或者在新表中偏移2的幂。

例如,当容量从16扩展到32时,具体变化如下:

当容量为16时,hash1和hash2将在桶下标计算后进入相同的桶,结果相同。当容量扩展到32时,新的桶下标计算过程如下:

hash1和hash2由桶下标公式重新计算,hash1的结果不变,因此仍在原来的桶中;hash2的结果比原始结果多1位,即2 4=16,即原始容量被偏移。如下图所示:

因此,扩展哈希映射(hashMap)时,不需要重新计算哈希,只需要检查二进制哈希中与二进制桶下标中新有效位位置相同的位(以下简称“新位”)是0还是1。如果为0,索引将不会改变,如果为1,索引将变为“原始索引旧Cap”。

如何检查新位是0还是1?哈希旧Cap位和操作在哈希映射中用于检查新位。OldCap是2的幂,所以二进制意味着只有1位是1,这个位正好对应于它。我不得不说,这种设计非常巧妙,不仅节省了重新计算哈希值的时间,而且因为新添加的1位是0或1,这可以被认为是随机的,之前碰撞的节点在扩展过程中均匀地分散到新旧桶中。

resize()方法的源代码如下:

final node[]resize(){

node[]old tab=table;

int oldCap=(oldTab==null)?0 : oldTab .长度;

int oldThr=阈值;

int newCap,NEWTHr=0;

//步骤①:根据oldCap判断是扩展还是初始化数组。如果扩张.

如果(oldCap 0) {

//超过最大容量,它将不再扩展,并将与

if (Oldcap=最大容量){

threshold=integer.max _ value冲突;

返回旧标签;

//没有超过最大值,如果((new cap=old cap 1)maximum _ capacity

old cap=default _ initial _ capacity)

new thr=old tr 1,则扩展到原始

else的2倍;//双阈值

//步骤2:如果数组已初始化,如果初始容量

else if(old tr 0)//初始容量在阈值

new cap=old tr中已保存在字段中

否则{ //零初始阈值表示使用默认值

NEWcap=DEFAULT _ INITIAL _ CAPITION;

NewTHr=(int)(DEFAULT _ LOAD _ FACTOR * DEFAULT _ INITIAL _ CAPACITY);

Lotail=e;

//步骤4:计算新的键值对阈值

if(new thr==0){

float ft=(float)new cap *负载系数;

newThr=(newCap最大容量英尺(浮动)最大容量?

(整数)英尺:整数。最大值);

Lotail=e;

threshold=newThr

SuppressWarnings()

//步骤5:实例化新的表数组

节点[]新选项卡=(节点[])新节点[新帽];

table=newTab

if (oldTab!=null) {

//步骤⑥:将每个存储桶和内部节点移动到新的表数组

for(int j=0;j oldCap{

节点e;

如果((e=oldTab[j])!=null) {

//删除旧数组对桶

oldTab[j]=null的引用;

//如果存储桶没有哈希冲突,如果(下一个==空)

newtab [e.hash (newcap-1)]=e,则重新计算存储桶下标;

//如果桶的内部结构是树

elseif(树节点的实例)

((树节点)e)。拆分(此,newtab,j,old cap);

//如果桶的内部结构是链表,冲突节点或者在原始桶中,或者在新桶的头和尾节点

else {//preserve order

//reference

nodelohead=null,lotail=null

//新桶的头和尾节点引用

nodehead=null,hitail=null

下一个节点;

//循环遍历桶中的冲突节点

do {

next=e.next

//原始桶的新位为0

if((e . hash old cap)=0){

if(lotail==null)

lohead=e;

hihead=e;

Lotail . next=e;

Lotail=e;

HiTail=e;

//新位为1,表示放入新桶

else {

if(hitail==null)

lohead=e;

else

HiTail . next=e;

Lotail=e;

newTab[j]=LoHead;

}同时((e=下一个)!=空);

//将新的表数组放入原始的bucket

if (loTail!=null){

Lotail . next=null;

Lotail=e;

newTab[j old cap]=HiHead;

//将新的表数组放入新的桶

if (hiTail!=null){

HiTail . next=null;

Lotail=e;

Lotail=e;

Lotail=e;

Lotail=e;

Lotail=e;

public vget(object key){

Lotail=e;

public vget(object key){

返回新标签;

public vget(object key){

十二,get(对象键)方法

此方法返回由指定键映射的值,如果不包含对应于该键的映射关系,则返回null。

for(int j=0;j oldCap{

此方法的源代码如下:

Lotail=e;

node;

return (e=getNode(散列(键),键))==null?null : e .值;

s.writeInt(桶);

方法内部调用的getNode()方法将键的哈希值和键本身作为参数。该方法的源代码如下:

XIII。HashMap序列化和反序列化

在前面的介绍中,HashMap在内部使用transient关键字来修改属性,如表。transient关键字用于防止修改后的成员属性被序列化。为什么HashMap应该使用这个关键字?

当使用put存储键值对时,需要调用key.hashCode()方法来参与哈希值计算。虽然Object.hashCode()是一种本机方法,但在不同的JVM中可能会有所不同。

例如,在JVM-1中,您使用字符串“123”作为键来存储键值对,调用key.hashCode()方法,结果是1,然后在JVM-1中序列化它,并在JVM-2中反序列化它。当您仍然使用字符串“123”作为键来获取值时,key.hashCode()方法的结果可能是2。

因此,哈希映射取消了成员属性表的序列化,并实现了自己的序列化和反序列化方法。

在序列化方法中,所有键和值都通过两层for循环进行遍历和提取;在反序列化方法中,读取每个键值对,并调用put方法存储在表数组中。

序列化代码如下:

private void write object(Java . io . objectoutputstreams)

throw SiO exception {

int buckets=capacity();

//写出阈值、负载系数和任何隐藏的东西

s . DefaultWriteObject();

Lotail=e;

s.writeInt(大小);

internalWriteEntries

}

void InternalwriteEntries(Java . io . objectoutputStream)引发IOException {

Node[]选项卡;

s . WriteObject(e . key);

s . WriteObject(e . value);

root=balanceInsertion(根,x);

root=balanceInsertion(根,x);

root=balanceInsertion(根,x);

root=balanceInsertion(根,x);

反序列化代码如下:

XIV。treeifyBin(节点[)选项卡,int hash)方法

在之前的put操作介绍中,当链表的长度大于或等于TREEIFY_THRESHOLD,即8时,将调用treeifyBin()方法将桶的结构从节点改为树节点,即链表将被转换成红色和黑色的树。但严格来说,这句话不应该这样表达。因为treeifyBin()方法将确定当前表阵列的容量是否小于min _ treife _ capacity (64),如果小于min _ treife _ capacity(64),则链表将被红黑树替换,并选择扩展。

此方法的源代码如下:

finalvoid treeifybin(节点[)选项卡,在此{

intn,index节点e;

//如果当前表数组的容量小于64,将放弃树的形成并选择扩展。

如果(tab==null | |(n=tab . length)MIN _ TREEIFY _ CAPACITY)

resize();

//链接到红黑树

else if((e=tab[索引=(n-1)哈希))!=null) {

//hd:链表头节点,tl:链表尾节点

TreeNode hd=null,tl=null

do {

//将节点转换为树节点,并保留链表的结构

treenode p=替换树节点(e,null);

if(TL==null)

HD=p;

else {

p.prev=tl

TL . next=p;

root=balanceInsertion(根,x);

TL=p;

}同时((e=e.next)!=空);

如果((制表符[索引]=hd)!=null)

//此步骤是指向红色和黑色树

hd.treeify(选项卡)的真实链接列表;

root=balanceInsertion(根,x);

root=balanceInsertion(根,x);

十五,树节点。Treife(节点[)选项卡)方法

HashMap除了节点(链表)之外,还有一个树节点(树)的桶类型。树节点类包含成员方法treeify(),它以当前的树节点对象作为根节点形成一棵红黑树。此方法的源代码如下:

finalvoid treife(节点[)选项卡){

treenoderroot=null

//步骤1:遍历当前的树节点链表

for(树节点x=这个,下一个;x!=null。x=next){

next=(TreeNode)x . next;

x . left=x . right=null;

//步骤2:如果根节点.

如果(root==null) {

x.parent=null尚未设置;

x.red=false

root=x;

root=balanceInsertion(根,x);

//步骤3:如果设置了根节点.

else {

K k=x.key

int h=x . hash;

类?kc=null

//步骤④:从根节点开始遍历,并为插入一个新节点

for(树节点p=根;){

int dir,ph;

K pk=p.key

//步骤⑤:比较当前节点的哈希值和新节点的哈希值

//如果新节点的哈希值较小

if ((ph=p哈希)h)

dir=-1;

//如果新节点的哈希值较大

else如果(ph h)

dir=1;

//如果新节点的哈希值等于当前节点的哈希值

else if (

//如果新节点的键不实现可比接口.

(KC==null(KC=Comparable astfor(k))==null)

//或者如果实现了Comparable接口,但k . Comparate to(PK)的结果为0

|(dir=Comparable(KC,k,PK))==0)

//然后调用tieBreakOrder继续比较大小

dir=tieBreakOrder(k,PK);

TReNode XP=p;

//步骤⑥:如果比较后新节点小于或等于当前节点,并且当前节点的左子节点为空,则插入新节点,反之亦然

if ((p=(dir=0))?p . left : p . right)=null){

x . parent=XP;

if(dir=0)

XP . left=x;

else

XP . right=x;

//步骤⑦:平衡红黑树

root=balanceInsertion(根,x);

root=balanceInsertion(根,x);

root=balanceInsertion(根,x);

root=balanceInsertion(根,x);

//步骤⑧:确保给定根节点是

//步骤⑧:确保给定根节点是

root=balanceInsertion(根,x);

moveRootToFront(选项卡,根)桶中的第一个节点;《介绍》的作者

秦雪目前在阿里巴巴工作,他热衷于Java技术堆栈,并对基本原则有独特的追求。他在Github