详解 Java HashMap 实现原理

2023-07-04 20:30:03 201

HashMap是Java中最常见数据结构之一，它能够在O(1)时间复杂度存储键值对和根据键值读取值操作。本文将分析其内部实现原理（基于jdk1.8.0_231）。

数据结构

HashMap是基于哈希值的一种映射，所谓映射，即可以根据key获取到相应的value。例如：数组是一种的映射，根据下标能够取到值。不过相对于数组，HashMap占用的存储空间更小，复杂度却同样为O(1)。

HashMap内部定义了一排“桶”，用一个叫table的Node数组表示；key-value存放到HashMap中时，根据key计算的哈希值决定存放的桶。当多个键值对计算出来的哈希值相等时，就产生了哈希碰撞，此时多个元素会放到同一个桶中。

transientNode[]table;//桶数组
transientintsize;//统计HashMap实例中有多少个元素，不等于table.length

桶的实例有两种，一种是Node的实例，是链表；另一种是TreeNode的实例，是红黑树。Node是HashMap中的一个静态内部类，TreeNode继承了Node。当桶中的元素较少时，桶的结构为单链表；当桶中的元素较多时，桶的结构会被转化为红黑树。

staticclassNodeimplementsMap.Entry{
finalinthash;
finalKkey;
Vvalue;
Nodenext;
}

staticfinalclassTreeNodeextendsLinkedHashMap.Entry{
TreeNodeparent;//red-blacktreelinks
TreeNodeleft;
TreeNoderight;
TreeNodeprev;//neededtounlinknextupondeletion
booleanred;
}

下图表示的是一个HashMap内部存储结构。第1行表示的是table数组，数组中的元素可能为Node实例，TreeNode实例，或者null。table数组的长度至少为64才能存放TreeNode。

需要注意的是，单链表的长度和红黑树元素数量取决于TREEIFY_THRESHOLD（值为8）,UNTREEIFY_THRESHOLD（值为6），MIN_TREEIFY_CAPACITY（值为64）三者。

下面几个结论不是很准确：

❌单链表长度最多为8，超过了8就会被树化。

✅单链表树化不仅要满足单链表长度超过8，而且要满足table数组的长度达到MIN_TREEIFY_CAPACITY，只不过每次尝试树化而实际没有树化的话，都会将table的长度增加1倍。所以单链表的长度有可能超过8。

❌红黑树中元素的数量总是超过8

✅table在扩容的过程中可能会触发树的拆分，即一个桶中的元素在table扩容之后可能分配到两个不同的桶里，一棵红黑树可能被拆分成两棵。若拆分后红黑树元素的数量小于等于UNTREEIFY_THRESHOLD，树会被转化为单链表。意味着拆分之后红黑树元素的数量可能为7或者8。

为什么单链表元素较多的时候要转化为红黑树？

单链表桶转化为红黑树桶的过程称为桶的树化，在HashMap源码中对应treeifyBin(table,hash)函数。如果使用单链表作为桶的数据结构，存在大量哈希碰撞时，链表会变得很长，进行一次操作的时间复杂度将变成O(K)，其中K为所操作的桶中元素的个数。而红黑树能够保证时间复杂度为O(log(K))，所以桶中元素过多时，使用树效果会更好，也可以在一定程度上防范利用哈希碰撞进行的黑客攻击。是一种时间上的优化。

不过相对于链表节点Node，红黑树节点TreeNode需要多维护4个引用和1个红黑标志，存储空间相对更大。而HashMap中的大部分桶都是存储很少量元素的（如果大多数桶都存储很多，键的哈希函数设计可能不太不合理），所以在一般情况下，也就是桶中元素很少时使用链表进行存储。是一种空间上的优化。

另外，桶的数据结构之所以不使用二叉排序树，是因为二叉排序树在特殊情况下会退化成单链表。例如：不断往同一个桶中从小到大顺序放入元素，会导致所有的节点都只有右孩子。而红黑树能够确保从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。

构造器

HashMap提供了4个构造器，其中带有参数initialCapacity和loadFactor这两个参数的构造器最为关键。其源码如下。

publicHashMap(intinitialCapacity,floatloadFactor){
if(initialCapacity<0)
thrownewIllegalArgumentException("Illegalinitialcapacity:"+
initialCapacity);
if(initialCapacity>MAXIMUM_CAPACITY)
initialCapacity=MAXIMUM_CAPACITY;
if(loadFactor<=0||Float.isNaN(loadFactor))
thrownewIllegalArgumentException("Illegalloadfactor:"+
loadFactor);
this.loadFactor=loadFactor;
this.threshold=tableSizeFor(initialCapacity);
}

initialCapacity表示的为期望的table的长度，JDK源码中的大多数capacity指的都是底层存储数组的长度；loadFactor（负载因子）是一个在区间(0,1)的小数，它决定了何时应该对table进行扩容。

table数组的长度发生改变时，将根据loadFactor计算threshold的值，公式为threshold=table.length*loadFactor。当HashMap中元素的数量size大于阈值threshod时，将触发table扩容。

构造器将传入的loadFactor直接赋值给了成员变量this.loadFactor，然后调用了tableSizeFor(capacity)函数计算了this.threshold的初始值。在这里thershold的意义是临时存储table的初始长度，只有往HashMap中放入元素时，才构造table数组，这是一种延迟初始化策略。

tableSizeFor(capacity)函数将计算出一个恰好大于等于capacity的2的n次方整数，作为table数组的长度，也就是说table数组的长度总是2的n次方。看这个算法时，将关注点放在cap的二进制最高位1比较容易理解。

staticfinalinttableSizeFor(intcap){
intn=cap-1;//处理特殊情况：cap恰好为2的n次方，即最高二进制位1右边全部为0的情况
n|=n>>>1;//最二进制位1右边1位填充1个1
n|=n>>>2;//继续填充2个1
n|=n>>>4;//填充4个1
n|=n>>>8;//填充8个1
n|=n>>>16;//填充16个1。执行完这句之后，已经确保最高位右边部分全部填充成了1，例如：cap=101_0101b时，n=111_1111b
return(n<0)?1:(n>=MAXIMUM_CAPACITY)?MAXIMUM_CAPACITY:n+1;//n+1进位，返回1000_0000b
}

剩下的3个构造器如下。

//传入initialCapacity，负载因子使用的是默认值0.75
publicHashMap(intinitialCapacity){
this(initialCapacity,DEFAULT_LOAD_FACTOR);
}
//capacity和loadFactor均使用默认值
publicHashMap(){
this.loadFactor=DEFAULT_LOAD_FACTOR;//allotherfieldsdefaulted
}

//传入一个map，传入的元素会逐个放入到新构造的HashMap实例中
publicHashMap(Mapm){
this.loadFactor=DEFAULT_LOAD_FACTOR;
putMapEntries(m,false);
}

put(k,v)过程

put(key,v)是先调用了hash(key)方法计算了一下键的哈希值，然后调用的是putVal()方法将节点放到HashMap中。

publicVput(Kkey,Vvalue){
returnputVal(hash(key),key,value,false,true);
}

哈希值计算

staticfinalinthash(Objectkey){
inth;
return(key==null)?0:(h=key.hashCode())^(h>>>16);
}

若key为null，则直接返回0作为哈希值；
若key不为null，则对key.hashCode()的结果的高16位和低16位进行异或操作再返回

这里对哈希值二进制的高16位和低16位取余的原因是为了让这两部分的二进制位都对桶的选择结果产生影响，减小哈希碰撞的概率。

finalVputVal(inthash,Kkey,Vvalue,booleanonlyIfAbsent,
booleanevict){
//tab代表table数组；p表示节点；n表示桶的数量；i指向应该放入的桶的下标
Node[]tab;Nodep;intn,i;
//table没有初始化，调用resize()构造table数组
if((tab=table)==null||(n=tab.length)==0)
n=(tab=resize()).length;
//如果桶中没有元素，则table数组的元素作为节点
if((p=tab[i=(n-1)&hash])==null)//因为n=2^x，所以(n-1)&hash等价于hash%n
tab[i]=newNode(hash,key,value,null);
else{//桶中有元素
Nodee;Kk;//e表示要存放值的Node，k表示对应的键，如果键不存在e的值为空，如果键存在，让e指向该节点
if(p.hash==hash&&//p此时指向table中的元素，也就是链表或者树的根
((k=p.key)==key||(key!=null&&key.equals(k))))//如果p.key恰好与key相等，存在着一个节点，让e指向它
e=p;
elseif(pinstanceofTreeNode)//桶是红黑树
e=((TreeNode)p).putTreeVal(this,tab,hash,key,value);
else{//桶是链表
for(intbinCount=0;;++binCount){//遍历链表
if((e=p.next)==null){//遍历到了末尾
p.next=newNode(hash,key,value,null);
//这一句很魔幻，有人说链表中达到了7个元素就会被树化，也有说是8个的，
//实际上往桶里放入第9个元素时才会树化，不信可以看一下这个实验：https://github.com/Robothy/java-experiments/blob/main/HashMap/TreeifyThreshold/TreeifyThresholdTest.java
if(binCount>=TREEIFY_THRESHOLD-1)//-1for1st
treeifyBin(tab,hash);
break;
}
if(e.hash==hash&&
((k=e.key)==key||(key!=null&&key.equals(k))))//在链表中找到了相同的key
break;
p=e;
}
}
//如果key已经存在了，HashMap不会取构造新的Node，而是直接修改Node中的value属性
if(e!=null){//existingmappingforkey
VoldValue=e.value;
if(!onlyIfAbsent||oldValue==null)
e.value=value;
afterNodeAccess(e);//这句在这里什么也没干，留给LinkedHashMap的
returnoldValue;
}
}
++modCount;//操作数统计，用来检查是否有多个线程同时修改HashMap，JDK中很多非线程安全的容器中都用了这些操作
if(++size>threshold)//size超过了threshold，进行扩容操作
resize();
afterNodeInsertion(evict);
returnnull;
}

上面代码中，需要注意以下几点：

根据哈希值选择桶的算法是(n-1)&hash，由于n为2的幂次方，所以(n-1)&hash等价于hash%n。之所以采用位运算而不使用取余运算，是因为对于计算机来说，取余的计算开销远大于位运算。能够这样进行等价的前提是n为2的幂次方。这是哈希桶的数量总保持为2的幂次方的重要原因。可以在这里验证一下这个算法。
桶中如果只有少量元素，桶的结构为单链表，某个桶中的元素超过了TREEFIED_THRESHOLD，值为8（必要非充分条件，前面有介绍，还需要满足桶的数量达到MIN_TREEIFY_CAPACITY，值为64），该桶的结构将会转化为红黑树；
当HashMap中元素的数量超过了阈值threshold时（threshold=桶数量*loadFactor），将触发哈希表的扩容。

整个put(k,v)大致流程：

resize()/rehash

上述流程中，还有两个重要的过程。首先是红黑树的操作，它能够在log(K)的时间复杂度内完成增删查改，K为红黑树中元素的数量。

另一个操作时resize()，它的目的是初始化哈希表table或者增加哈希桶的数量，减小哈希碰撞的概率。具体操作是让成员变量table指向一个Node数组。

上面流程图中可以看到，有两个地方可能会触发resize()。一是table未初始化时，需要初始化table。此时table初始长度可能为：
1）threshold，指定了initialCapaclity的情况下，构造器中会根据initialCapacity计算出一个capcacity并赋值给threshold；
2）DEFAULT_INITIAL_CAPACITY（值为16），没有指定initialCapacity的情况下。

二是HashMap中元素的数量超过了阈值（即：size>threshold），需要对table进行扩容。此时table的长度为变为原来的2倍，HashMap的内部结构也会发生改变，同一个桶中的元素可能被分配到不同的桶中。这个过程也叫rehash。

resize()源代码比较长，这里分为两部分来看，一部分是构造新的Node数组，更新threshold；另一部分是将旧的table中的元素放到新table中的过程。先看前一部分：

finalNode[]resize(){
Node[]oldTab=table;//oldTab指向旧的table
intoldCap=(oldTab==null)?0:oldTab.length;//旧table的长度，如果table为空，则长度为0
intoldThr=threshold;//旧的阈值，如果table没有初始化，threshold临时存储的是构造方法中根据initialCapacity计算的初始capacity
intnewCap,newThr=0;
if(oldCap>0){//这句的含义是table已经初始化了，现在要对它扩容
if(oldCap>=MAXIMUM_CAPACITY){//值已经达到了2^31，不能再扩容了，因为int范围内不能再进行乘以2操作了，否则会导致整数溢出
threshold=Integer.MAX_VALUE;//直接将threshold的值提高到int范围内的最大值，让后续的put操作不再触发resize()
returnoldTab;//直接返回，不扩容了
}
elseif((newCap=oldCap<<1)=DEFAULT_INITIAL_CAPACITY)
newThr=oldThr<<1;//新的threshold变为原来的两倍，因为新的capacity也是原来的两倍，而threshod=capacity*loadFactor
}
elseif(oldThr>0)//旧的threshold大于0；含义是table需要初始化，不过在构造HashMap时指定了initialCapacity，table的初始长度已经定下来了，临时存放在this.threshold中，等于oldThr
newCap=oldThr;//那么新的table的长度直接设置为oldThr即可
else{//含义是table需要初始化，但是构造器中没有指定初始化的相关参数，则直接使用默认参数计算即可
newCap=DEFAULT_INITIAL_CAPACITY;//值为16
newThr=(int)(DEFAULT_LOAD_FACTOR*DEFAULT_INITIAL_CAPACITY);//值为16*0.75=12
}
if(newThr==0){//table需要初始化，且构造器中指定了初始化参数
floatft=(float)newCap*loadFactor;//使用构造器指定的参数计算阈值，临时放在ft中。新阈值=新数组长度*负载因子
newThr=(newCap[]newTab=(Node[])newNode[newCap];//实例化新的Node数组
table=newTab;//让table指向新的Node数组
if(oldTab!=null){//旧的table不为空，则需要将旧table中的元素放到新的table中
//省略将旧的table中的元素放到新的table中的代码
}
returnnewTab;
}

resize()前半部分代码计算了新的阈值threshold，创建了空的哈希表。接下来的代码是将旧的哈希表中的元素放到新的哈希表中。

代码算法的大致流程为：遍历每一个桶，若桶为单链表，则拆成两个链表作为2个新的桶；若桶为红黑树，则拆成2棵红黑树作为新的桶，若新的红黑树中元素的数量小于等于UNTREEIFY_THRESHOLD，值为6，则将红黑树转化为单链表。

旧的桶之所以能够恰好拆分成两个新的桶，是因为新的桶的总数newCap为旧桶总数oldCap的2倍，即newCap=2*oldCap，若hash%oldCap==j，则hash%(2*oldCap)的值为j或oldCap+j。也就是说下标为j的桶会可能被拆分成下标为j和oldCap+j的两个桶。

if(oldTab!=null){
for(intj=0;je;
if((e=oldTab[j])!=null){//桶中有元素
oldTab[j]=null;
if(e.next==null)//桶中只有1个元素
newTab[e.hash&(newCap-1)]=e;
elseif(einstanceofTreeNode)//桶为红黑树
((TreeNode)e).split(this,newTab,j,oldCap);//同样拆分成两个桶
else{//桶为单链表
NodeloHead=null,loTail=null;//子链表（新桶），存放哈希值%newCap==j的元素
NodehiHead=null,hiTail=null;//子链表（新桶），存放哈希值%newCap==j+oldCap的元素。

Nodenext;
do{//遍历链表
next=e.next;
if((e.hash&oldCap)==0){//算法比较巧妙，通过临界的1位二进制位即可判断该哈希值余上newCap所属桶
if(loTail==null)
loHead=e;
else
loTail.next=e;
loTail=e;
}
else{
if(hiTail==null)
hiHead=e;
else
hiTail.next=e;
hiTail=e;
}
}while((e=next)!=null);
if(loTail!=null){//余数较小的桶有元素
loTail.next=null;
newTab[j]=loHead;
}
if(hiTail!=null){//余数较大的桶有元素
hiTail.next=null;
newTab[j+oldCap]=hiHead;
}
}
}
}
}

get(k)过程

get(k)方法显得比较简单，它调用了getNode()方法。算法的时间复杂度约等于O(1)

publicVget(Objectkey){
Nodee;
	//计算哈希值
return(e=getNode(hash(key),key))==null?null:e.value;
}

finalNodegetNode(inthash,Objectkey){
Node[]tab;Nodefirst,e;intn;Kk;
if((tab=table)!=null&&(n=tab.length)>0&&
(first=tab[(n-1)&hash])!=null){//hash%table.length定位到桶
		
if(first.hash==hash&&//alwayscheckfirstnode
((k=first.key)==key||(key!=null&&key.equals(k))))
returnfirst;//直接取table中的元素
if((e=first.next)!=null){
if(firstinstanceofTreeNode)//红黑树查找
return((TreeNode)first).getTreeNode(hash,key);
do{//单链表遍历查找
if(e.hash==hash&&
((k=e.key)==key||(key!=null&&key.equals(k))))
returne;
}while((e=e.next)!=null);
}
}
returnnull;
}

remove(k)与remove(k,v)

这两个重载方法均调用了removeNode方法。remove(k)只要找到对应的key匹配即移除，remove(k,v)需要key和value均匹配才移除。

publicVremove(Objectkey){
Nodee;
return(e=removeNode(hash(key),key,null,false,true))==null?
null:e.value;
}

publicbooleanremove(Objectkey,Objectvalue){
returnremoveNode(hash(key),key,value,true,true)!=null;
}

removeNode()方法中流程大致为：根据key和hash找到对应Node，然后根据各种条件判断是否执行移除。HashMap的数据结构决定了此操作的时间复杂度仍然大致为O(1)。

finalNoderemoveNode(inthash,Objectkey,Objectvalue,
booleanmatchValue,booleanmovable){
Node[]tab;Nodep;intn,index;
if((tab=table)!=null&&(n=tab.length)>0&&
(p=tab[index=(n-1)&hash])!=null){
Nodenode=null,e;Kk;Vv;
if(p.hash==hash&&
((k=p.key)==key||(key!=null&&key.equals(k))))//key为桶中的第1个元素
node=p;//直接取table[(n-1)&hash]
elseif((e=p.next)!=null){//桶中超过1个元素
if(pinstanceofTreeNode)//桶为红黑树
node=((TreeNode)p).getTreeNode(hash,key);
else{//桶为单链表
do{//单链表搜索
if(e.hash==hash&&
((k=e.key)==key||
(key!=null&&key.equals(k)))){
node=e;
break;
}
p=e;
}while((e=e.next)!=null);
}
}
		
		//若找到了key，对应的节点由node指向
if(node!=null&&(!matchValue||(v=node.value)==value||
(value!=null&&value.equals(v)))){//检查key和value是否均符合要求
if(nodeinstanceofTreeNode)//node为红黑树节点
((TreeNode)node).removeTreeNode(this,tab,movable);//执行红黑树移除操作
elseif(node==p)//查找到的node为桶中的第1个元素
tab[index]=node.next;
else
p.next=node.next;//执行单链表移除
++modCount;
--size;
afterNodeRemoval(node);
returnnode;
}
}
returnnull;
}

迭代

HashMap没有直接或间接实现Iterable接口，因此不能直接使用for-each语法结构去遍历一个HashMap。不过可以通过entrySet()方法获取一个EntrySet，然后对EntrySet进行遍历来达到访问每一个key-value的目的。

方法entrySet()采用了延迟加载和缓存的机制，只有调用entrySet()方法时才创建EntrySet对象，并赋值给成员变量this.entrySet缓存起来。重复调用entrySet()并不会产生多个EntrySet对象。

publicSet>entrySet(){
Set>es;
return(es=entrySet)==null?(entrySet=newEntrySet()):es;
}

EntrySet中的iterator()返回的是EntryIterator对象，迭代相关的部分代码如下。

intindex;//指向当前的桶，初始值为0
finalNodenextNode(){
Node[]t;
Nodee=next;
if(modCount!=expectedModCount)
thrownewConcurrentModificationException();
if(e==null)
thrownewNoSuchElementException();
if((next=(current=e).next)==null&&(t=table)!=null){
do{}while(index
迭代HashMap的顺序是逐个遍历哈希桶，桶中有元素，则遍历单链表或红黑树。因此，遍历HashMap时的顺序与放入顺序无任何关系。HashMap内部也没有维护任何与插入顺序有关的信息。
小结


以上内容就是HashMap的实现原理以及核心API，这里直接总结一些关于HashMap的结论性的东西。
1）HashMap的Key和Value都可以为null，当key为null时，计算的哈希值为0；
2）HashMap默认的加载因子loadFactor是0.75，它与table.length一同决定了扩容阈值threshold，计算公式为：threshold=table.length*loadFactor；
3）HashMap各项操作的效率很高，在哈希碰撞不严重的情况下时间复杂度为O(1)
4）HashMap中的元素是无序的，它没有维护任何与顺序有关的内容；
5）单个哈希桶中的元素过多时，桶的结构会由单链表转化为红黑树；
6）HashMap中哈希表table的长度（桶的数量）总是2的幂次方，这保证了能够通过高效的位运算将key映射到对应的桶。
以上就是详解JavaHashMap实现原理的详细内容，更多关于JavaHashMap实现原理的资料请关注毛票票其它相关文章！
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。