在Java8与Java7中HashMap源码实现的对比
一、HashMap的原理介绍
此乃老生常谈，不作仔细解说。
一句话概括之：HashMap是一个散列表，它存储的内容是键值对(key-value)映射。
二、Java7中HashMap的源码分析
首先是HashMap的构造函数代码块1中，根据初始化的Capacity与loadFactor（加载因子）初始化HashMap.
//代码块1
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;
threshold=initialCapacity;
init();
}
Java7中对于<key1,value1>的put方法实现相对比较简单，首先根据key1的key值计算hash值，再根据该hash值与table的length确定该key所在的index,如果当前位置的Entry不为null，则在该Entry链中遍历，如果找到hash值和key值都相同，则将值value覆盖，返回oldValue；如果当前位置的Entry为null，则直接addEntry。
代码块2
publicVput(Kkey,Vvalue){
if(table==EMPTY_TABLE){
inflateTable(threshold);
}
if(key==null)
returnputForNullKey(value);
inthash=hash(key);
inti=indexFor(hash,table.length);
for(Entry<K,V>e=table[i];e!=null;e=e.next){
Objectk;
if(e.hash==hash&&((k=e.key)==key||key.equals(k))){
VoldValue=e.value;
e.value=value;
e.recordAccess(this);
returnoldValue;
}
}
modCount++;
addEntry(hash,key,value,i);
returnnull;
}
//addEntry方法中会检查当前table是否需要resize
voidaddEntry(inthash,Kkey,Vvalue,intbucketIndex){
if((size>=threshold)&&(null!=table[bucketIndex])){
resize(2*table.length);//当前map中的size如果大于threshole的阈值，则将resize将table的length扩大2倍。
hash=(null!=key)?hash(key):0;
bucketIndex=indexFor(hash,table.length);
}
createEntry(hash,key,value,bucketIndex);
}
Java7中resize（）方法的实现比较简单，将OldTable的长度扩展，并且将oldTable中的Entry根据rehash的标记重新计算hash值和index移动到newTable中去。
代码如代码块3中所示，
//代码块3--JDK7中HashMap.resize()方法
voidresize(intnewCapacity){
Entry[]oldTable=table;
intoldCapacity=oldTable.length;
if(oldCapacity==MAXIMUM_CAPACITY){
threshold=Integer.MAX_VALUE;
return;
}
Entry[]newTable=newEntry[newCapacity];
transfer(newTable,initHashSeedAsNeeded(newCapacity));
table=newTable;
threshold=(int)Math.min(newCapacity*loadFactor,MAXIMUM_CAPACITY+1);
}
/**
*将当前table的Entry转移到新的table中
*/
voidtransfer(Entry[]newTable,booleanrehash){
intnewCapacity=newTable.length;
for(Entry<K,V>e:table){
while(null!=e){
Entry<K,V>next=e.next;
if(rehash){
e.hash=null==e.key?0:hash(e.key);
}
inti=indexFor(e.hash,newCapacity);
e.next=newTable[i];
newTable[i]=e;
e=next;
}
}
}
HashMap性能的有两个参数：初始容量(initialCapacity)和加载因子(loadFactor)。容量是哈希表中桶的数量，初始容量只是哈希表在创建时的容量。加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行rehash操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数。
根据源码分析可以看出：在Java7中HashMap的entry是按照index索引存储的，遇到hash冲突的时候采用拉链法解决冲突，将冲突的key和value插入到链表list中。
然而这种解决方法会有一个缺点，假如key值都冲突，HashMap会退化成一个链表，get的复杂度会变成O(n)。
在Java8中为了优化该最坏情况下的性能，采用了平衡树来存放这些hash冲突的键值对，性能由此可以提升至O(logn)。
代码块4--JDK8中HashMap中常量定义 staticfinalintDEFAULT_INITIAL_CAPACITY=1<<4; staticfinalintTREEIFY_THRESHOLD=8;//是否将list转换成tree的阈值 staticfinalintUNTREEIFY_THRESHOLD=6;//在resize操作中，决定是否untreeify的阈值 staticfinalintMIN_TREEIFY_CAPACITY=64;//决定是否转换成tree的最小容量 staticfinalfloatDEFAULT_LOAD_FACTOR=0.75f;//default的加载因子
在Java8HashMap的put方法实现如代码块5所示，
代码块5--JDK8HashMap.put方法
publicVput(Kkey,Vvalue){
returnputVal(hash(key),key,value,false,true);
}
finalVputVal(inthash,Kkey,Vvalue,booleanonlyIfAbsent,
booleanevict){
Node<K,V>[]tab;Node<K,V>p;intn,i;
if((tab=table)==null||(n=tab.length)==0)
n=(tab=resize()).length;//table为空的时候，n为table的长度
if((p=tab[i=(n-1)&hash])==null)
tab[i]=newNode(hash,key,value,null);//(n-1)&hash与Java7中indexFor方法的实现相同，若i位置上的值为空，则新建一个Node，table[i]指向该Node。
else{
//若i位置上的值不为空，判断当前位置上的Nodep是否与要插入的key的hash和key相同
Node<K,V>e;Kk;
if(p.hash==hash&&
((k=p.key)==key||(key!=null&&key.equals(k))))
e=p;//相同则覆盖之
elseif(pinstanceofTreeNode)
//不同，且当前位置上的的nodep已经是TreeNode的实例，则再该树上插入新的node。
e=((TreeNode<K,V>)p).putTreeVal(this,tab,hash,key,value);
else{
//在i位置上的链表中找到p.next为null的位置，binCount计算出当前链表的长度，如果继续将冲突的节点插入到该链表中，会使链表的长度大于tree化的阈值，则将链表转换成tree。
for(intbinCount=0;;++binCount){
if((e=p.next)==null){
p.next=newNode(hash,key,value,null);
if(binCount>=TREEIFY_THRESHOLD-1)//-1for1st
treeifyBin(tab,hash);
break;
}
if(e.hash==hash&&
((k=e.key)==key||(key!=null&&key.equals(k))))
break;
p=e;
}
}
if(e!=null){//existingmappingforkey
VoldValue=e.value;
if(!onlyIfAbsent||oldValue==null)
e.value=value;
afterNodeAccess(e);
returnoldValue;
}
}
++modCount;
if(++size>threshold)
resize();
afterNodeInsertion(evict);
returnnull;
}
再看下resize方法，由于需要考虑hash冲突解决时采用的可能是list也可能是balancetree的方式，因此resize方法相比JDK7中复杂了一些,
代码块6--JDK8的resize方法
inalNode<K,V>[]resize(){
Node<K,V>[]oldTab=table;
intoldCap=(oldTab==null)?0:oldTab.length;
intoldThr=threshold;
intnewCap,newThr=0;
if(oldCap>0){
if(oldCap>=MAXIMUM_CAPACITY){
threshold=Integer.MAX_VALUE;//如果超过最大容量，无法再扩充table
returnoldTab;
}
elseif((newCap=oldCap<<1)<MAXIMUM_CAPACITY&&
oldCap>=DEFAULT_INITIAL_CAPACITY)
newThr=oldThr<<1;//threshold门槛扩大至2倍
}
elseif(oldThr>0)//initialcapacitywasplacedinthreshold
newCap=oldThr;
else{//zeroinitialthresholdsignifiesusingdefaults
newCap=DEFAULT_INITIAL_CAPACITY;
newThr=(int)(DEFAULT_LOAD_FACTOR*DEFAULT_INITIAL_CAPACITY);
}
if(newThr==0){
floatft=(float)newCap*loadFactor;
newThr=(newCap<MAXIMUM_CAPACITY&&ft<(float)MAXIMUM_CAPACITY?
(int)ft:Integer.MAX_VALUE);
}
threshold=newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[]newTab=(Node<K,V>[])newNode[newCap];//创建容量为newCap的newTab，并将oldTab中的Node迁移过来，这里需要考虑链表和tree两种情况。
table=newTab;
if(oldTab!=null){
for(intj=0;j<oldCap;++j){
Node<K,V>e;
if((e=oldTab[j])!=null){
oldTab[j]=null;
if(e.next==null)
newTab[e.hash&(newCap-1)]=e;
elseif(einstanceofTreeNode)
((TreeNode<K,V>)e).split(this,newTab,j,oldCap);
//split方法会将树分割为lower和uppertree两个树，
如果子树的节点数小于了UNTREEIFY_THRESHOLD阈值，则将树untreeify，将节点都存放在newTab中。
else{//preserveorder
Node<K,V>loHead=null,loTail=null;
Node<K,V>hiHead=null,hiTail=null;
Node<K,V>next;
do{
next=e.next;
if((e.hash&oldCap)==0){
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;
}
}
}
}
}
returnnewTab;
}
再看一下tree的treeifyBin方法和putTreeVal方法的实现，底层采用了红黑树的方法。
//代码块7
//MIN_TREEIFY_CAPACITY的值为64，若当前table的length不够，则resize（）
finalvoidtreeifyBin(Node<K,V>[]tab,inthash){
intn,index;Node<K,V>e;
if(tab==null||(n=tab.length)<MIN_TREEIFY_CAPACITY)
resize();
elseif((e=tab[index=(n-1)&hash])!=null){
TreeNode<K,V>hd=null,tl=null;
do{
TreeNode<K,V>p=replacementTreeNode(e,null);
if(tl==null)
hd=p;
else{
p.prev=tl;
tl.next=p;
}
tl=p;
}while((e=e.next)!=null);
if((tab[index]=hd)!=null)
hd.treeify(tab);
}
}
//putVal的tree版本
finalTreeNode<K,V>putTreeVal(HashMap<K,V>map,Node<K,V>[]tab,
inth,Kk,Vv){
Class<?>kc=null;
booleansearched=false;
TreeNode<K,V>root=(parent!=null)?root():this;
for(TreeNode<K,V>p=root;;){
intdir,ph;Kpk;
if((ph=p.hash)>h)
dir=-1;
elseif(ph<h)
dir=1;
elseif((pk=p.key)==k||(k!=null&&k.equals(pk)))
returnp;
elseif((kc==null&&
(kc=comparableClassFor(k))==null)||
(dir=compareComparables(kc,k,pk))==0){
if(!searched){
TreeNode<K,V>q,ch;
searched=true;
if(((ch=p.left)!=null&&
(q=ch.find(h,k,kc))!=null)||
((ch=p.right)!=null&&
(q=ch.find(h,k,kc))!=null))
returnq;
}
dir=tieBreakOrder(k,pk);
}
TreeNode<K,V>xp=p;
if((p=(dir<=0)?p.left:p.right)==null){
Node<K,V>xpn=xp.next;
TreeNode<K,V>x=map.newTreeNode(h,k,v,xpn);
if(dir<=0)
xp.left=x;
else
xp.right=x;
xp.next=x;
x.parent=x.prev=xp;
if(xpn!=null)
((TreeNode<K,V>)xpn).prev=x;
moveRootToFront(tab,balanceInsertion(root,x));
returnnull;
}
}
}
看了这些源码，并一一做了比较之后，惊叹于源码之妙，收益良多。
总结
以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作能带来一定的帮助，如果有疑问大家可以留言交流。