发布一篇Java汇合进修（十） HashMap具体先容(源码剖析)和利用示例 - 仓酷云

packagejava.util;
importjava.io.*;
publicclassHashMap<K,V>
extendsAbstractMap<K,V>
implementsMap<K,V>,Cloneable,Serializable
{
//默许的初始容量是16，必需是2的幂。
staticfinalintDEFAULT_INITIAL_CAPACITY=16;
//最年夜容量（必需是2的幂且小于2的30次方，传进容量过上将被这个值交换）
staticfinalintMAXIMUM_CAPACITY=1<<30;
//默许加载因子
staticfinalfloatDEFAULT_LOAD_FACTOR=0.75f;
//存储数据的Entry数组，长度是2的幂。
//HashMap是接纳拉链法完成的，每个Entry实质上是一个单向链表
transientEntry[]table;
//HashMap的巨细，它是HashMap保留的键值对的数目
transientintsize;
//HashMap的阈值，用于判别是不是必要调剂HashMap的容量（threshold=容量*加载因子）
intthreshold;
//加载因籽实际巨细
finalfloatloadFactor;
//HashMap被改动的次数
transientvolatileintmodCount;
//指定“容量巨细”和“加载因子”的机关函数
publicHashMap(intinitialCapacity,floatloadFactor){
if(initialCapacity<0)
thrownewIllegalArgumentException("Illegalinitialcapacity:"+
initialCapacity);
//HashMap的最年夜容量只能是MAXIMUM_CAPACITY
if(initialCapacity>MAXIMUM_CAPACITY)
initialCapacity=MAXIMUM_CAPACITY;
if(loadFactor<=0||Float.isNaN(loadFactor))
thrownewIllegalArgumentException("Illegalloadfactor:"+
loadFactor);
//找出“年夜于initialCapacity”的最小的2的幂
intcapacity=1;
while(capacity<initialCapacity)
capacity<<=1;
//设置“加载因子”
this.loadFactor=loadFactor;
//设置“HashMap阈值”，当HashMap中存储数据的数目到达threshold时，就必要将HashMap的容量更加。
threshold=(int)(capacity*loadFactor);
//创立Entry数组，用来保留数据
table=newEntry[capacity];
init();
}
//指定“容量巨细”的机关函数
publicHashMap(intinitialCapacity){
this(initialCapacity,DEFAULT_LOAD_FACTOR);
}
//默许机关函数。
publicHashMap(){
//设置“加载因子”
this.loadFactor=DEFAULT_LOAD_FACTOR;
//设置“HashMap阈值”，当HashMap中存储数据的数目到达threshold时，就必要将HashMap的容量更加。
threshold=(int)(DEFAULT_INITIAL_CAPACITY*DEFAULT_LOAD_FACTOR);
//创立Entry数组，用来保留数据
table=newEntry[DEFAULT_INITIAL_CAPACITY];
init();
}
//包括“子Map”的机关函数
publicHashMap(Map<?extendsK,?extendsV>m){
this(Math.max((int)(m.size()/DEFAULT_LOAD_FACTOR)+1,
DEFAULT_INITIAL_CAPACITY),DEFAULT_LOAD_FACTOR);
//将m中的全体元素逐一增加到HashMap中
putAllForCreate(m);
}
staticinthash(inth){
h^=(h>>>20)^(h>>>12);
returnh^(h>>>7)^(h>>>4);
}
//前往索引值
//h&(length-1)包管前往值的小于length
staticintindexFor(inth,intlength){
returnh&(length-1);
}
publicintsize(){
returnsize;
}
publicbooleanisEmpty(){
returnsize==0;
}
//猎取key对应的value
publicVget(Objectkey){
if(key==null)
returngetForNullKey();
//猎取key的hash值
inthash=hash(key.hashCode());
//在“该hash值对应的链表”上查找“键值即是key”的元素
for(Entry<K,V>e=table[indexFor(hash,table.length)];
e!=null;
e=e.next){
Objectk;
if(e.hash==hash&&((k=e.key)==key||key.equals(k)))
returne.value;
}
returnnull;
}
//猎取“key为null”的元素的值
//HashMap将“key为null”的元素存储在table[0]地位！
privateVgetForNullKey(){
for(Entry<K,V>e=table[0];e!=null;e=e.next){
if(e.key==null)
returne.value;
}
returnnull;
}
//HashMap是不是包括key
publicbooleancontainsKey(Objectkey){
returngetEntry(key)!=null;
}
//前往“键为key”的键值对
finalEntry<K,V>getEntry(Objectkey){
//猎取哈希值
//HashMap将“key为null”的元素存储在table[0]地位，“key不为null”的则挪用hash()盘算哈希值
inthash=(key==null)?0:hash(key.hashCode());
//在“该hash值对应的链表”上查找“键值即是key”的元素
for(Entry<K,V>e=table[indexFor(hash,table.length)];
e!=null;
e=e.next){
Objectk;
if(e.hash==hash&&
((k=e.key)==key||(key!=null&&key.equals(k))))
returne;
}
returnnull;
}
//将“key-value”增加到HashMap中
publicVput(Kkey,Vvalue){
//若“key为null”，则将该键值对增加到table[0]中。
if(key==null)
returnputForNullKey(value);
//若“key不为null”，则盘算该key的哈希值，然后将其增加到该哈希值对应的链表中。
inthash=hash(key.hashCode());
inti=indexFor(hash,table.length);
for(Entry<K,V>e=table[i];e!=null;e=e.next){
Objectk;
//若“该key”对应的键值对已存在，则用新的value代替旧的value。然前进出！
if(e.hash==hash&&((k=e.key)==key||key.equals(k))){
VoldValue=e.value;
e.value=value;
e.recordAccess(this);
returnoldValue;
}
}
//若“该key”对应的键值对不存在，则将“key-value”增加到table中
modCount++;
addEntry(hash,key,value,i);
returnnull;
}
//putForNullKey()的感化是将“key为null”键值对增加到table[0]地位
privateVputForNullKey(Vvalue){
for(Entry<K,V>e=table[0];e!=null;e=e.next){
if(e.key==null){
VoldValue=e.value;
e.value=value;
e.recordAccess(this);
returnoldValue;
}
}
//这里的完整不会被实行到!
modCount++;
addEntry(0,null,value,0);
returnnull;
}
//创立HashMap对应的“增加办法”，
//它和put()分歧。putForCreate()是外部办法，它被机关函数等挪用，用来创立HashMap
//而put()是对外供应的往HashMap中增加元素的办法。
privatevoidputForCreate(Kkey,Vvalue){
inthash=(key==null)?0:hash(key.hashCode());
inti=indexFor(hash,table.length);
//若该HashMap表中存在“键值即是key”的元素，则交换该元素的value值
for(Entry<K,V>e=table[i];e!=null;e=e.next){
Objectk;
if(e.hash==hash&&
((k=e.key)==key||(key!=null&&key.equals(k)))){
e.value=value;
return;
}
}
//若该HashMap表中不存在“键值即是key”的元素，则将该key-value增加到HashMap中
createEntry(hash,key,value,i);
}
//将“m”中的全体元素都增加到HashMap中。
//该办法被外部的机关HashMap的办法所挪用。
privatevoidputAllForCreate(Map<?extendsK,?extendsV>m){
//使用迭代器将元素逐一增加到HashMap中
for(Iterator<?extendsMap.Entry<?extendsK,?extendsV>>i=m.entrySet().iterator();i.hasNext();){
Map.Entry<?extendsK,?extendsV>e=i.next();
putForCreate(e.getKey(),e.getValue());
}
}
//从头调剂HashMap的巨细，newCapacity是调剂后的单元
voidresize(intnewCapacity){
Entry[]oldTable=table;
intoldCapacity=oldTable.length;
if(oldCapacity==MAXIMUM_CAPACITY){
threshold=Integer.MAX_VALUE;
return;
}
//新建一个HashMap，将“旧HashMap”的全体元素增加到“新HashMap”中，
//然后，将“新HashMap”赋值给“旧HashMap”。
Entry[]newTable=newEntry[newCapacity];
transfer(newTable);
table=newTable;
threshold=(int)(newCapacity*loadFactor);
}
//将HashMap中的全体元素都增加到newTable中
voidtransfer(Entry[]newTable){
Entry[]src=table;
intnewCapacity=newTable.length;
for(intj=0;j<src.length;j++){
Entry<K,V>e=src[j];
if(e!=null){
src[j]=null;
do{
Entry<K,V>next=e.next;
inti=indexFor(e.hash,newCapacity);
e.next=newTable[i];
newTable[i]=e;
e=next;
}while(e!=null);
}
}
}
//将"m"的全体元素都增加到HashMap中
publicvoidputAll(Map<?extendsK,?extendsV>m){
//无效性判别
intnumKeysToBeAdded=m.size();
if(numKeysToBeAdded==0)
return;
//盘算容量是不是充足，
//若“以后实践容量<必要的容量”，则将容量x2。
if(numKeysToBeAdded>threshold){
inttargetCapacity=(int)(numKeysToBeAdded/loadFactor+1);
if(targetCapacity>MAXIMUM_CAPACITY)
targetCapacity=MAXIMUM_CAPACITY;
intnewCapacity=table.length;
while(newCapacity<targetCapacity)
newCapacity<<=1;
if(newCapacity>table.length)
resize(newCapacity);
}
//经由过程迭代器，将“m”中的元素逐一增加到HashMap中。
for(Iterator<?extendsMap.Entry<?extendsK,?extendsV>>i=m.entrySet().iterator();i.hasNext();){
Map.Entry<?extendsK,?extendsV>e=i.next();
put(e.getKey(),e.getValue());
}
}
//删除“键为key”元素
publicVremove(Objectkey){
Entry<K,V>e=removeEntryForKey(key);
return(e==null?null:e.value);
}
//删除“键为key”的元素
finalEntry<K,V>removeEntryForKey(Objectkey){
//猎取哈希值。若key为null，则哈希值为0；不然挪用hash()举行盘算
inthash=(key==null)?0:hash(key.hashCode());
inti=indexFor(hash,table.length);
Entry<K,V>prev=table[i];
Entry<K,V>e=prev;
//删除链表中“键为key”的元素
//实质是“删除单向链表中的节点”
while(e!=null){
Entry<K,V>next=e.next;
Objectk;
if(e.hash==hash&&
((k=e.key)==key||(key!=null&&key.equals(k)))){
modCount++;
size--;
if(prev==e)
table[i]=next;
else
prev.next=next;
e.recordRemoval(this);
returne;
}
prev=e;
e=next;
}
returne;
}
//删除“键值对”
finalEntry<K,V>removeMapping(Objecto){
if(!(oinstanceofMap.Entry))
returnnull;
Map.Entry<K,V>entry=(Map.Entry<K,V>)o;
Objectkey=entry.getKey();
inthash=(key==null)?0:hash(key.hashCode());
inti=indexFor(hash,table.length);
Entry<K,V>prev=table[i];
Entry<K,V>e=prev;
//删除链表中的“键值对e”
//实质是“删除单向链表中的节点”
while(e!=null){
Entry<K,V>next=e.next;
if(e.hash==hash&&e.equals(entry)){
modCount++;
size--;
if(prev==e)
table[i]=next;
else
prev.next=next;
e.recordRemoval(this);
returne;
}
prev=e;
e=next;
}
returne;
}
//清空HashMap，将一切的元素设为null
publicvoidclear(){
modCount++;
Entry[]tab=table;
for(inti=0;i<tab.length;i++)
tab[i]=null;
size=0;
}
//是不是包括“值为value”的元素
publicbooleancontainsValue(Objectvalue){
//若“value为null”，则挪用containsNullValue()查找
if(value==null)
returncontainsNullValue();
//若“value不为null”，则查找HashMap中是不是有值为value的节点。
Entry[]tab=table;
for(inti=0;i<tab.length;i++)
for(Entrye=tab[i];e!=null;e=e.next)
if(value.equals(e.value))
returntrue;
returnfalse;
}
//是不是包括null值
privatebooleancontainsNullValue(){
Entry[]tab=table;
for(inti=0;i<tab.length;i++)
for(Entrye=tab[i];e!=null;e=e.next)
if(e.value==null)
returntrue;
returnfalse;
}
//克隆一个HashMap，并前往Object对象
publicObjectclone(){
HashMap<K,V>result=null;
try{
result=(HashMap<K,V>)super.clone();
}catch(CloneNotSupportedExceptione){
//assertfalse;
}
result.table=newEntry[table.length];
result.entrySet=null;
result.modCount=0;
result.size=0;
result.init();
//挪用putAllForCreate()将全体元素增加到HashMap中
result.putAllForCreate(this);
returnresult;
}
//Entry是单向链表。
//它是“HashMap链式存储法”对应的链表。
//它完成了Map.Entry接口，即完成getKey(),getValue(),setValue(Vvalue),equals(Objecto),hashCode()这些函数
staticclassEntry<K,V>implementsMap.Entry<K,V>{
finalKkey;
Vvalue;
//指向下一个节点
Entry<K,V>next;
finalinthash;
//机关函数。
//输出参数包含"哈希值(h)","键(k)","值(v)","下一节点(n)"
Entry(inth,Kk,Vv,Entry<K,V>n){
value=v;
next=n;
key=k;
hash=h;
}
publicfinalKgetKey(){
returnkey;
}
publicfinalVgetValue(){
returnvalue;
}
publicfinalVsetValue(VnewValue){
VoldValue=value;
value=newValue;
returnoldValue;
}
//判别两个Entry是不是相称
//若两个Entry的“key”和“value”都相称，则前往true。
//不然，前往false
publicfinalbooleanequals(Objecto){
if(!(oinstanceofMap.Entry))
returnfalse;
Map.Entrye=(Map.Entry)o;
Objectk1=getKey();
Objectk2=e.getKey();
if(k1==k2||(k1!=null&&k1.equals(k2))){
Objectv1=getValue();
Objectv2=e.getValue();
if(v1==v2||(v1!=null&&v1.equals(v2)))
returntrue;
}
returnfalse;
}
//完成hashCode()
publicfinalinthashCode(){
return(key==null?0:key.hashCode())^
(value==null?0:value.hashCode());
}
publicfinalStringtoString(){
returngetKey()+"="+getValue();
}
//当向HashMap中增加元素时，绘挪用recordAccess()。
//这里不做任那边理
voidrecordAccess(HashMap<K,V>m){
}
//当从HashMap中删除元素时，绘挪用recordRemoval()。
//这里不做任那边理
voidrecordRemoval(HashMap<K,V>m){
}
}
//新增Entry。将“key-value”拔出指定地位，bucketIndex是地位索引。
voidaddEntry(inthash,Kkey,Vvalue,intbucketIndex){
//保留“bucketIndex”地位的值到“e”中
Entry<K,V>e=table[bucketIndex];
//设置“bucketIndex”地位的元素为“新Entry”，
//设置“e”为“新Entry的下一个节点”
table[bucketIndex]=newEntry<K,V>(hash,key,value,e);
//若HashMap的实践巨细不小于“阈值”，则调剂HashMap的巨细
if(size++>=threshold)
resize(2*table.length);
}
//创立Entry。将“key-value”拔出指定地位，bucketIndex是地位索引。
//它和addEntry的区分是：
//(01)addEntry()一样平常用在新增Entry大概招致“HashMap的实践容量”凌驾“阈值”的情形下。
//比方，我们新建一个HashMap，然后不休经由过程put()向HashMap中增加元素；
//put()是经由过程addEntry()新增Entry的。
//在这类情形下，我们不晓得什么时候“HashMap的实践容量”会凌驾“阈值”；
//因而，必要挪用addEntry()
//(02)createEntry()一样平常用在新增Entry不会招致“HashMap的实践容量”凌驾“阈值”的情形下。
//比方，我们挪用HashMap“带有Map”的机关函数，它绘将Map的全体元素增加到HashMap中；
//但在增加之前，我们已盘算好“HashMap的容量和阈值”。也就是，能够断定“即便将Map中
//的全体元素增加到HashMap中，都不会凌驾HashMap的阈值”。
//此时，挪用createEntry()便可。
voidcreateEntry(inthash,Kkey,Vvalue,intbucketIndex){
//保留“bucketIndex”地位的值到“e”中
Entry<K,V>e=table[bucketIndex];
//设置“bucketIndex”地位的元素为“新Entry”，
//设置“e”为“新Entry的下一个节点”
table[bucketIndex]=newEntry<K,V>(hash,key,value,e);
size++;
}
//HashIterator是HashMap迭代器的笼统出来的父类，完成了大众了函数。
//它包括“key迭代器(KeyIterator)”、“Value迭代器(ValueIterator)”和“Entry迭代器(EntryIterator)”3个子类。
privateabstractclassHashIterator<E>implementsIterator<E>{
//下一个元素
Entry<K,V>next;
//expectedModCount用于完成fast-fail机制。
intexpectedModCount;
//以后索引
intindex;
//以后元素
Entry<K,V>current;
HashIterator(){
expectedModCount=modCount;
if(size>0){//advancetofirstentry
Entry[]t=table;
//将next指向table中第一个不为null的元素。
//这里使用了index的初始值为0，从0入手下手顺次向后遍历，直到找到不为null的元素就加入轮回。
while(index<t.length&&(next=t[index++])==null)
;
}
}
publicfinalbooleanhasNext(){
returnnext!=null;
}
//猎取下一个元素
finalEntry<K,V>nextEntry(){
if(modCount!=expectedModCount)
thrownewConcurrentModificationException();
Entry<K,V>e=next;
if(e==null)
thrownewNoSuchElementException();
//注重！！！
//一个Entry就是一个单向链表
//若该Entry的下一个节点不为空，就将next指向下一个节点;
//不然，将next指向下一个链表(也是下一个Entry)的不为null的节点。
if((next=e.next)==null){
Entry[]t=table;
while(index<t.length&&(next=t[index++])==null)
;
}
current=e;
returne;
}
//删除以后元素
publicvoidremove(){
if(current==null)
thrownewIllegalStateException();
if(modCount!=expectedModCount)
thrownewConcurrentModificationException();
Objectk=current.key;
current=null;
HashMap.this.removeEntryForKey(k);
expectedModCount=modCount;
}
}
//value的迭代器
privatefinalclassValueIteratorextendsHashIterator<V>{
publicVnext(){
returnnextEntry().value;
}
}
//key的迭代器
privatefinalclassKeyIteratorextendsHashIterator<K>{
publicKnext(){
returnnextEntry().getKey();
}
}
//Entry的迭代器
privatefinalclassEntryIteratorextendsHashIterator<Map.Entry<K,V>>{
publicMap.Entry<K,V>next(){
returnnextEntry();
}
}
//前往一个“key迭代器”
Iterator<K>newKeyIterator(){
returnnewKeyIterator();
}
//前往一个“value迭代器”
Iterator<V>newValueIterator(){
returnnewValueIterator();
}
//前往一个“entry迭代器”
Iterator<Map.Entry<K,V>>newEntryIterator(){
returnnewEntryIterator();
}
//HashMap的Entry对应的汇合
privatetransientSet<Map.Entry<K,V>>entrySet=null;
//前往“key的汇合”，实践上前往一个“KeySet对象”
publicSet<K>keySet(){
Set<K>ks=keySet;
return(ks!=null?ks:(keySet=newKeySet()));
}
//Key对应的汇合
//KeySet承继于AbstractSet，申明该汇合中没有反复的Key。
privatefinalclassKeySetextendsAbstractSet<K>{
publicIterator<K>iterator(){
returnnewKeyIterator();
}
publicintsize(){
returnsize;
}
publicbooleancontains(Objecto){
returncontainsKey(o);
}
publicbooleanremove(Objecto){
returnHashMap.this.removeEntryForKey(o)!=null;
}
publicvoidclear(){
HashMap.this.clear();
}
}
//前往“value汇合”，实践上前往的是一个Values对象
publicCollection<V>values(){
Collection<V>vs=values;
return(vs!=null?vs:(values=newValues()));
}
//“value汇合”
//Values承继于AbstractCollection，分歧于“KeySet承继于AbstractSet”，
//Values中的元素可以反复。由于分歧的key能够指向不异的value。
privatefinalclassValuesextendsAbstractCollection<V>{
publicIterator<V>iterator(){
returnnewValueIterator();
}
publicintsize(){
returnsize;
}
publicbooleancontains(Objecto){
returncontainsValue(o);
}
publicvoidclear(){
HashMap.this.clear();
}
}
//前往“HashMap的Entry汇合”
publicSet<Map.Entry<K,V>>entrySet(){
returnentrySet0();
}
//前往“HashMap的Entry汇合”，它实践是前往一个EntrySet对象
privateSet<Map.Entry<K,V>>entrySet0(){
Set<Map.Entry<K,V>>es=entrySet;
returnes!=null?es:(entrySet=newEntrySet());
}
//EntrySet对应的汇合
//EntrySet承继于AbstractSet，申明该汇合中没有反复的EntrySet。
privatefinalclassEntrySetextendsAbstractSet<Map.Entry<K,V>>{
publicIterator<Map.Entry<K,V>>iterator(){
returnnewEntryIterator();
}
publicbooleancontains(Objecto){
if(!(oinstanceofMap.Entry))
returnfalse;
Map.Entry<K,V>e=(Map.Entry<K,V>)o;
Entry<K,V>candidate=getEntry(e.getKey());
returncandidate!=null&&candidate.equals(e);
}
publicbooleanremove(Objecto){
returnremoveMapping(o)!=null;
}
publicintsize(){
returnsize;
}
publicvoidclear(){
HashMap.this.clear();
}
}
//java.io.Serializable的写进函数
//将HashMap的“总的容量，实践容量，一切的Entry”都写进到输入流中
privatevoidwriteObject(java.io.ObjectOutputStreams)
throwsIOException
{
Iterator<Map.Entry<K,V>>i=
(size>0)?entrySet0().iterator():null;
//Writeoutthethreshold,loadfactor,andanyhiddenstuff
s.defaultWriteObject();
//Writeoutnumberofbuckets
s.writeInt(table.length);
//Writeoutsize(numberofMappings)
s.writeInt(size);
//Writeoutkeysandvalues(alternating)
if(i!=null){
while(i.hasNext()){
Map.Entry<K,V>e=i.next();
s.writeObject(e.getKey());
s.writeObject(e.getValue());
}
}
}
privatestaticfinallongserialVersionUID=362498820763181265L;
//java.io.Serializable的读取函数：依据写进体例读出
//将HashMap的“总的容量，实践容量，一切的Entry”顺次读出
privatevoidreadObject(java.io.ObjectInputStreams)
throwsIOException,ClassNotFoundException
{
//Readinthethreshold,loadfactor,andanyhiddenstuff
s.defaultReadObject();
//Readinnumberofbucketsandallocatethebucketarray;
intnumBuckets=s.readInt();
table=newEntry[numBuckets];
init();//Givesubclassachancetodoitsthing.
//Readinsize(numberofMappings)
intsize=s.readInt();
//Readthekeysandvalues,andputthemappingsintheHashMap
for(inti=0;i<size;i++){
Kkey=(K)s.readObject();
Vvalue=(V)s.readObject();
putForCreate(key,value);
}
}
//前往“HashMap总的容量”
intcapacity(){returntable.length;}
//前往“HashMap的加载因子”
floatloadFactor(){returnloadFactor;}
}

复制代码