java集合框架---HashMap
1、介绍
HashMap简介
HashMap是一个散列表，它存储的内容是键值对(key-value)映射。
HashMap继承于AbstractMap，实现了Map、Cloneable、java.io.Serializable接口。
HashMap的实现不是同步的，这意味着它不是线程安全的。它的key、value都可以为null。此外，HashMap中的映射不是有序的。
HashMap的实例有两个参数影响其性能：“初始容量”和“加载因子”。容量是哈希表中桶的数量，初始容量只是哈希表在创建时的容量。加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行rehash操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数。
通常，默认加载因子是0.75,这是在时间和空间成本上寻求一种折衷。加载因子过高虽然减少了空间开销，但同时也增加了查询成本（在大多数HashMap类的操作中，包括get和put操作，都反映了这一点）。在设置初始容量时应该考虑到映射中所需的条目数及其加载因子，以便最大限度地减少rehash操作次数。如果初始容量大于最大条目数除以加载因子，则不会发生rehash操作。
HashMap的构造函数
HashMap共有4个构造函数,如下：
//默认构造函数。
HashMap()
//指定“容量大小”的构造函数
HashMap(intcapacity)
//指定“容量大小”和“加载因子”的构造函数
HashMap(intcapacity,floatloadFactor)
//包含“子Map”的构造函数
HashMap(Mapmap)
HashMap的API
voidclear()
Objectclone()
booleancontainsKey(Objectkey)
booleancontainsValue(Objectvalue)
Set>entrySet()
Vget(Objectkey)
booleanisEmpty()
SetkeySet()
Vput(Kkey,Vvalue)
voidputAll(Mapmap)
Vremove(Objectkey)
intsize()
Collectionvalues()
2、数据结构
HashMap继承于AbstractMap类，实现了Map接口。Map是”key-value键值对”接口，AbstractMap实现了”键值对”的通用函数接口。
HashMap是通过”拉链法”实现的哈希表。它包括几个重要的成员变量：table,size,threshold,loadFactor,modCount。
1）table是一个Entry[]数组类型，而Entry实际上就是一个单向链表。哈希表的”key-value键值对”都是存储在Entry数组中的。
2）size是HashMap的大小，它是HashMap保存的键值对的数量。
3）threshold是HashMap的阈值，用于判断是否需要调整HashMap的容量。threshold的值=”容量加载因子”，当HashMap中存储数据的数量达到threshold时，就需要将HashMap的容量加倍。
4）loadFactor就是加载因子。
5）modCount是用来实现fail-fast机制的。
3、源码分析
packagejava.util;
importjava.io.;
publicclassHashMap
extendsAbstractMap
implementsMap,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
capacity<<=1;
//设置“加载因子”
this.loadFactor=loadFactor;
//设置“HashMap阈值”，当HashMap中存储数据的数量达到threshold时，就需要将HashMap的容量加倍。
threshold=(int)(capacityloadFactor);
//创建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_CAPACITYDEFAULT_LOAD_FACTOR);
//创建Entry数组，用来保存数据
table=newEntry[DEFAULT_INITIAL_CAPACITY];
init();
}
//包含“子Map”的构造函数
publicHashMap(Mapm){
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(Entrye=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(Entrye=table[0];e!=null;e=e.next){
if(e.key==null)
returne.value;
}
returnnull;
}
//HashMap是否包含key
publicbooleancontainsKey(Objectkey){
returngetEntry(key)!=null;
}
//返回“键为key”的键值对
finalEntrygetEntry(Objectkey){
//获取哈希值
//HashMap将“key为null”的元素存储在table[0]位置，“key不为null”的则调用hash()计算哈希值
inthash=(key==null)?0:hash(key.hashCode());
//在“该hash值对应的链表”上查找“键值等于key”的元素
for(Entrye=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(Entrye=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(Entrye=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(Entrye=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(Mapm){
//利用迭代器将元素逐个添加到HashMap中
for(Iterator>i=m.entrySet().iterator();i.hasNext();){
Map.Entrye=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)(newCapacityloadFactor);
}
//将HashMap中的全部元素都添加到newTable中
voidtransfer(Entry[]newTable){
Entry[]src=table;
intnewCapacity=newTable.length;
for(intj=0;j
Entrye=src[j];
if(e!=null){
src[j]=null;
do{
Entrynext=e.next;
inti=indexFor(e.hash,newCapacity);
e.next=newTable[i];
newTable[i]=e;
e=next;
}while(e!=null);
}
}
}
//将"m"的全部元素都添加到HashMap中
publicvoidputAll(Mapm){
//有效性判断
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
newCapacity<<=1;
if(newCapacity>table.length)
resize(newCapacity);
}
//通过迭代器，将“m”中的元素逐个添加到HashMap中。
for(Iterator>i=m.entrySet().iterator();i.hasNext();){
Map.Entrye=i.next();
put(e.getKey(),e.getValue());
}
}
//删除“键为key”元素
publicVremove(Objectkey){
Entrye=removeEntryForKey(key);
return(e==null?null:e.value);
}
//删除“键为key”的元素
finalEntryremoveEntryForKey(Objectkey){
//获取哈希值。若key为null，则哈希值为0；否则调用hash()进行计算
inthash=(key==null)?0:hash(key.hashCode());
inti=indexFor(hash,table.length);
Entryprev=table[i];
Entrye=prev;
//删除链表中“键为key”的元素
//本质是“删除单向链表中的节点”
while(e!=null){
Entrynext=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;
}
//删除“键值对”
finalEntryremoveMapping(Objecto){
if(!(oinstanceofMap.Entry))
returnnull;
Map.Entryentry=(Map.Entry)o;
Objectkey=entry.getKey();
inthash=(key==null)?0:hash(key.hashCode());
inti=indexFor(hash,table.length);
Entryprev=table[i];
Entrye=prev;
//删除链表中的“键值对e”
//本质是“删除单向链表中的节点”
while(e!=null){
Entrynext=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[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
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
for(Entrye=tab[i];e!=null;e=e.next)
if(e.value==null)
returntrue;
returnfalse;
}
//克隆一个HashMap，并返回Object对象
publicObjectclone(){
HashMapresult=null;
try{
result=(HashMap)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()这些函数
staticclassEntryimplementsMap.Entry{
finalKkey;
Vvalue;
//指向下一个节点
Entrynext;
finalinthash;
//构造函数。
//输入参数包括"哈希值(h)","键(k)","值(v)","下一节点(n)"
Entry(inth,Kk,Vv,Entryn){
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(HashMapm){
}
//当从HashMap中删除元素时，绘调用recordRemoval()。
//这里不做任何处理
voidrecordRemoval(HashMapm){
}
}
//新增Entry。将“key-value”插入指定位置，bucketIndex是位置索引。
voidaddEntry(inthash,Kkey,Vvalue,intbucketIndex){
//保存“bucketIndex”位置的值到“e”中
Entrye=table[bucketIndex];
//设置“bucketIndex”位置的元素为“新Entry”，
//设置“e”为“新Entry的下一个节点”
table[bucketIndex]=newEntry(hash,key,value,e);
//若HashMap的实际大小不小于“阈值”，则调整HashMap的大小
if(size++>=threshold)
resize(2table.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”中
Entrye=table[bucketIndex];
//设置“bucketIndex”位置的元素为“新Entry”，
//设置“e”为“新Entry的下一个节点”
table[bucketIndex]=newEntry(hash,key,value,e);
size++;
}
//HashIterator是HashMap迭代器的抽象出来的父类，实现了公共了函数。
//它包含“key迭代器(KeyIterator)”、“Value迭代器(ValueIterator)”和“Entry迭代器(EntryIterator)”3个子类。
privateabstractclassHashIteratorimplementsIterator{
//下一个元素
Entrynext;
//expectedModCount用于实现fast-fail机制。
intexpectedModCount;
//当前索引
intindex;
//当前元素
Entrycurrent;
HashIterator(){
expectedModCount=modCount;
if(size>0){//advancetofirstentry
Entry[]t=table;
//将next指向table中第一个不为null的元素。
//这里利用了index的初始值为0，从0开始依次向后遍历，直到找到不为null的元素就退出循环。
while(index
;
}
}
publicfinalbooleanhasNext(){
returnnext!=null;
}
//获取下一个元素
finalEntrynextEntry(){
if(modCount!=expectedModCount)
thrownewConcurrentModificationException();
Entrye=next;
if(e==null)
thrownewNoSuchElementException();
//注意！！！
//一个Entry就是一个单向链表
//若该Entry的下一个节点不为空，就将next指向下一个节点;
//否则，将next指向下一个链表(也是下一个Entry)的不为null的节点。
if((next=e.next)==null){
Entry[]t=table;
while(index
;
}
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{
publicVnext(){
returnnextEntry().value;
}
}
//key的迭代器
privatefinalclassKeyIteratorextendsHashIterator{
publicKnext(){
returnnextEntry().getKey();
}
}
//Entry的迭代器
privatefinalclassEntryIteratorextendsHashIterator>{
publicMap.Entrynext(){
returnnextEntry();
}
}
//返回一个“key迭代器”
IteratornewKeyIterator(){
returnnewKeyIterator();
}
//返回一个“value迭代器”
IteratornewValueIterator(){
returnnewValueIterator();
}
//返回一个“entry迭代器”
Iterator>newEntryIterator(){
returnnewEntryIterator();
}
//HashMap的Entry对应的集合
privatetransientSet>entrySet=null;
//返回“key的集合”，实际上返回一个“KeySet对象”
publicSetkeySet(){
Setks=keySet;
return(ks!=null?ks:(keySet=newKeySet()));
}
//Key对应的集合
//KeySet继承于AbstractSet，说明该集合中没有重复的Key。
privatefinalclassKeySetextendsAbstractSet{
publicIteratoriterator(){
returnnewKeyIterator();
}
publicintsize(){
returnsize;
}
publicbooleancontains(Objecto){
returncontainsKey(o);
}
publicbooleanremove(Objecto){
returnHashMap.this.removeEntryForKey(o)!=null;
}
publicvoidclear(){
HashMap.this.clear();
}
}
//返回“value集合”，实际上返回的是一个Values对象
publicCollectionvalues(){
Collectionvs=values;
return(vs!=null?vs:(values=newValues()));
}
//“value集合”
//Values继承于AbstractCollection，不同于“KeySet继承于AbstractSet”，
//Values中的元素能够重复。因为不同的key可以指向相同的value。
privatefinalclassValuesextendsAbstractCollection{
publicIteratoriterator(){
returnnewValueIterator();
}
publicintsize(){
returnsize;
}
publicbooleancontains(Objecto){
returncontainsValue(o);
}
publicvoidclear(){
HashMap.this.clear();
}
}
//返回“HashMap的Entry集合”
publicSet>entrySet(){
returnentrySet0();
}
//返回“HashMap的Entry集合”，它实际是返回一个EntrySet对象
privateSet>entrySet0(){
Set>es=entrySet;
returnes!=null?es:(entrySet=newEntrySet());
}
//EntrySet对应的集合
//EntrySet继承于AbstractSet，说明该集合中没有重复的EntrySet。
privatefinalclassEntrySetextendsAbstractSet>{
publicIterator>iterator(){
returnnewEntwww.shanxiwang.netryIterator();
}
publicbooleancontains(Objecto){
if(!(oinstanceofMap.Entry))
returnfalse;
Map.Entrye=(Map.Entry)o;
Entrycandidate=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>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.Entrye=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
Kkey=(K)s.readObject();
Vvalue=(V)s.readObject();
putForCreate(key,value);
}
}
//返回“HashMap总的容量”
intcapacity(){returntable.length;}
//返回“HashMap的加载因子”
floatloadFactor(){returnloadFactor;}
}
HashMap就是一个散列表，它是通过“拉链法”解决哈希冲突的。
影响HashMap性能的有两个参数：初始容量(initialCapacity)和加载因子(loadFactor)。容量
是哈希表中桶的数量，初始容量只是哈希表在创建时的容量。加载因子
是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行rehash
操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数。
HashMap拉链法分析
HashMap数据存储数组
transientEntry[]table;
HashMap中的key-value都是存储在Entry数组中的。
数据节点Entry的数据结构
staticclassEntryimplementsMap.Entry{
finalKkey;
Vvalue;
//指向下一个节点
Entrynext;
finalinthash;
//构造函数。
//输入参数包括"哈希值(h)","键(k)","值(v)","下一节点(n)"
Entry(inth,Kk,Vv,Entryn){
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(HashMapm){
}
//当从HashMap中删除元素时，绘调用recordRemoval()。
//这里不做任何处理
voidrecordRemoval(HashMapm){
}
}
从中，我们可以看出Entry实际上就是一个单向链表。这也是为什么我们说HashMap是通过拉链法解决哈希冲突的。
Entry实现了Map.Entry接口，即实现getKey(),getValue(),setValue(Vvalue),equals(Objecto),hashCode()这些函数。这些都是基本的读取/修改key、value值的函数。
主要的对外接口
1）clear方法
clear()的作用是清空HashMap。它是通过将所有的元素设为null来实现的。
publicvoidclear(){
modCount++;
Entry[]tab=table;
for(inti=0;i
tab[i]=null;
size=0;
}
2）containsKey()
containsKey()的作用是判断HashMap是否包含key。
publicbooleancontainsKey(Objectkey){
returngetEntry(key)!=null;
}
containsKey()首先通过getEntry(key)获取key对应的Entry，然后判断该Entry是否为null。
getEntry()源码：
finalEntrygetEntry(Objectkey){
//获取哈希值
//HashMap将“key为null”的元素存储在table[0]位置，“key不为null”的则调用hash()计算哈希值
inthash=(key==null)?0:hash(key.hashCode());
//在“该hash值对应的链表”上查找“键值等于key”的元素
for(Entrye=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;
}
getEntry()的作用就是返回“键为key”的键值对，它的实现源码中已经进行了说明。
这里需要强调的是：HashMap将“key为null”的元素都放在table的位置0处，即table[0]中；“key不为null”的放在table的其余位置！
3）containsValue()
containsValue()的作用是判断HashMap是否包含“值为value”的元素。
publicbooleancontainsValue(Objectvalue){
//若“value为null”，则调用containsNullValue()查找
if(value==null)
returncontainsNullValue();
//若“value不为null”，则查找HashMap中是否有值为value的节点。
Entry[]tab=table;
for(inti=0;i
for(Entrye=tab[i];e!=null;e=e.next)
if(value.equals(e.value))
returntrue;
returnfalse;
}
从中，我们可以看出containsNullValue()分为两步进行处理：第一，若“value为null”，则调用containsNullValue()。第二，若“value不为null”，则查找HashMap中是否有值为value的节点。
containsNullValue()的作用判断HashMap中是否包含“值为null”的元素。
privatebooleancontainsNullValue(){
Entry[]tab=table;
for(inti=0;i
for(Entrye=tab[i];e!=null;e=e.next)
if(e.value==null)
returntrue;
returnfalse;
}
4）entrySet()、values()、keySet()
它们3个的原理类似，这里以entrySet()为例来说明。
entrySet()的作用是返回“HashMap中所有Entry的集合”，它是一个集合。实现代码如下：
//返回“HashMap的Entry集合”
publicSet>entrySet(){
returnentrySet0();
}
//返回“HashMap的Entry集合”，它实际是返回一个EntrySet对象
privateSet>entrySet0(){
Set>es=entrySet;
returnes!=null?es:(entrySet=newEntrySet());
}
//EntrySet对应的集合
//EntrySet继承于AbstractSet，说明该集合中没有重复的EntrySet。
privatefinalclassEntrySetextendsAbstractSet>{
publicIterator>iterator(){
returnnewEntryIterator();
}
publicbooleancontains(Objecto){
if(!(oinstanceofMap.Entry))
returnfalse;
Map.Entrye=(Map.Entry)o;
Entrycandidate=getEntry(e.getKey());
returncandidate!=null&&candidate.equals(e);
}
publicbooleanremove(Objecto){
returnremoveMapping(o)!=null;
}
publicintsize(){
returnsize;
}
publicvoidclear(){
HashMap.this.clear();
}
}
HashMap是通过拉链法实现的散列表。表现在HashMap包括许多的Entry，而每一个Entry本质上又是一个单向链表。那么HashMap遍历key-value键值对的时候，是如何逐个去遍历的呢？
下面我们就看看HashMap是如何通过entrySet()遍历的。
entrySet()实际上是通过newEntryIterator()实现的。下面我们看看它的代码：
//返回一个“entry迭代器”
Iterator>newEntryIterator(){
returnnewEntryIterator();
}
//Entry的迭代器
privatefinalclassEntryIteratorextendsHashIterator>{
publicMap.Entrynext(){
returnnextEntry();
}
}
//HashIterator是HashMap迭代器的抽象出来的父类，实现了公共了函数。
//它包含“key迭代器(KeyIterator)”、“Value迭代器(ValueIterator)”和“Entry迭代器(EntryIterator)”3个子类。
privateabstractclassHashIteratorimplementsIterator{
//下一个元素
Entrynext;
//expectedModCount用于实现fast-fail机制。
intexpectedModCount;
//当前索引
intindex;
//当前元素
Entrycurrent;
HashIterator(){
expectedModCount=modCount;
if(size>0){//advancetofirstentry
Entry[]t=table;
//将next指向table中第一个不为null的元素。
//这里利用了index的初始值为0，从0开始依次向后遍历，直到找到不为null的元素就退出循环。
while(index
;
}
}
publicfinalbooleanhasNext(){
returnnext!=null;
}
//获取下一个元素
finalEntrynextEntry(){
if(modCount!=expectedModCount)
thrownewConcurrentModificationException();
Entrye=next;
if(e==null)
thrownewNoSuchElementException();
//注意！！！
//一个Entry就是一个单向链表
//若该Entry的下一个节点不为空，就将next指向下一个节点;
//否则，将next指向下一个链表(也是下一个Entry)的不为null的节点。
if((next=e.next)==null){
Entry[]t=table;
while(index
;
}
current=e;
returne;
}
//删除当前元素
publicvoidremove(){
if(current==null)
thrownewIllegalStateException();
if(modCount!=expectedModCount)
thrownewConcurrentModificationException();
Objectk=current.key;
current=null;
HashMap.this.removeEntryForKey(k);
expectedModCount=modCount;
}
}
当我们通过entrySet()获取到的Iterator的next()方法去遍历HashMap时，实际上调用的是nextEntry()。而nextEntry()的实现方式，先遍历Entry(根据Entry在table中的序号，从小到大的遍历)；然后对每个Entry(即每个单向链表)，逐个遍历。
5）get()
get()的作用是获取key对应的value，它的实现代码如下：
publicVget(Objectkey){
if(key==null)
returngetForNullKey();
//获取key的hash值
inthash=hash(key.hashCode());
//在“该hash值对应的链表”上查找“键值等于key”的元素
for(Entrye=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;
}
6）put()
put()的作用是对外提供接口，让HashMap对象可以通过put()将“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(Entrye=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;
}
若要添加到HashMap中的键值对对应的key已经存在HashMap中，则找到该键值对；然后新的value取代旧的value，并退出！
若要添加到HashMap中的键值对对应的key不在HashMap中，则将其添加到该哈希值对应的链表中，并调用addEntry()。
下面看看addEntry()的代码：
voidaddEntry(inthash,Kkey,Vvalue,intbucketIndex){
//保存“bucketIndex”位置的值到“e”中
Entrye=table[bucketIndex];
//设置“bucketIndex”位置的元素为“新Entry”，
//设置“e”为“新Entry的下一个节点”
table[bucketIndex]=newEntry(hash,key,value,e);
//若HashMap的实际大小不小于“阈值”，则调整HashMap的大小
if(size++>=threshold)
resize(2table.length);
}
addEntry()的作用是新增Entry。将“key-value”插入指定位置，bucketIndex是位置索引。
createEntry()的代码如下：
voidcreateEntry(inthash,Kkey,Vvalue,intbucketIndex){
//保存“bucketIndex”位置的值到“e”中
Entrye=table[bucketIndex];
//设置“bucketIndex”位置的元素为“新Entry”，
//设置“e”为“新Entry的下一个节点”
table[bucketIndex]=newEntry(hash,key,value,e);
size++;
}
比较addEntry()和createEntry()的代码，我们发现addEntry()多了两句：
if(size++>=threshold)
resize(2table.length);
1
2
那它们的区别到底是什么呢？
阅读代码，我们可以发现，它们的使用情景不同。
(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()即可。
7）putAll
8）remove
4、遍历方式
遍历HashMap的键值对
第一步：根据entrySet()获取HashMap的“键值对”的Set集合。
第二步：通过Iterator迭代器遍历“第一步”得到的集合。
//假设map是HashMap对象
//map中的key是String类型，value是Integer类型
Integerinteg=null;
Iteratoriter=map.entrySet().iterator();
while(iter.hasNext()){
Map.Entryentry=(Map.Entry)iter.next();
//获取key
key=(String)entry.getKey();
//获取value
integ=(Integer)entry.getValue();
}
遍历HashMap的键
第一步：根据keySet()获取HashMap的“键”的Set集合。
第二步：通过Iterator迭代器遍历“第一步”得到的集合。
//假设map是HashMap对象
//map中的key是String类型，value是Integer类型
Stringkey=null;
Integerinteg=null;
Iteratoriter=map.keySet().iterator();
while(iter.hasNext()){
//获取key
key=(String)iter.next();
//根据key，获取value
integ=(Integer)map.get(key);
}
遍历HashMap的值
第一步：根据value()获取HashMap的“值”的集合。
第二步：通过Iterator迭代器遍历“第一步”得到的集合。
//假设map是HashMap对象
//map中的key是String类型，value是Integer类型
Integervalue=null;
Collectionc=map.values();
Iteratoriter=c.iterator();
while(iter.hasNext()){
value=(Integer)iter.next();
}
|
|
