Java源码分析HashTable源码分析.docx
《Java源码分析HashTable源码分析.docx》由会员分享，可在线阅读，更多相关《Java源码分析HashTable源码分析.docx（14页珍藏版）》请在冰点文库上搜索。
Java源码分析HashTable源码分析
【Java源码分析】HashTable源码分析
android6.0源码分析之Runtime的初始化类的定义
publicclassHashtable
extendsDictionary
implementsMap,Cloneable,java.io.Serializable{}
注意前面虽然说HashTable和HashMap是非常像的，但是这两个类的父类是不一样的。
前者是字典类的子类，后者是抽象Map的子类。
HashTable也是将key映射到value的集合类，key不允许为null，并且作为key的类是必须实现hashCode（）和equals（）方法
影响HashTable的性能的两个因素也是容量capacity和装载因子load-factor。
关于这一点和HashMap是一样的，默认装载因子也是0.75
初始化容量用于控制空间利用率和扩容之间的平衡，如果初始容量很小，那么后续可能引发多次扩容（扩容会重新分配空间，再hash，并拷贝数据，所以比较耗时）；如果初始容量很大，可能会有点浪费存储空间；所以和HashMap一样，最好预估一个合理的初始大小
迭代器创建并迭代的过程中同样是不允许修改HashTable结构的（比如增加或者删除数据），否则出现fail-fast，同时fail-fast虽然抛出了ConcurrentModificationException但是它并不能保证线程安全性
HashTable是线程安全的如果程序本身不是多线程环境下运行，那么建议使用HashMap，如果是高并发环境下，建议使用java.util.concurrent.ConcurrentHashMap，只有在一般并发环境下建议使用HashTable
重要的成员变量
privatetransientEntry[]table;//基于数组实现
privatetransientintcount;//实际存放的实体个数
privateintthreshold;//阈值，用于判断是否需要扩容
privatefloatloadFactor;//装载因子
构造函数
publicHashtable（）{
this（11,0.75f）;
}
publicHashtable（intinitialCapacity）{
this（initialCapacity,0.75f）;
}
publicHashtable（intinitialCapacity,floatloadFactor）{
if（initialCapacity<0）
thrownewIllegalArgumentException（"IllegalCapacity:
"+
initialCapacity）;
if（loadFactor<=0||Float.isNaN（loadFactor））
thrownewIllegalArgumentException（"IllegalLoad:
"+loadFactor）;
if（initialCapacity==0）
initialCapacity=1;
this.loadFactor=loadFactor;
table=newEntry[initialCapacity];
threshold=（int）Math.min（initialCapacity*loadFactor,MAX_ARRAY_SIZE+1）;
useAltHashing=sun.misc.VM.isBooted（）&&
（initialCapacity>=Holder.ALTERNATIVE_HASHING_THRESHOLD）;
}
publicHashtable（Map
extendsK,?
extendsV>t）{
this（Math.max（2*t.size（）,11）,0.75f）;
putAll（t）;
}
构造函数和HashMap一样，不同点在于默认容量不一样，HashTable的默认容量是11
hash函数
transientfinalinthashSeed=sun.misc.Hashing.randomHashSeed（this）;
privateinthash（Objectk）{
if（useAltHashing）{
if（k.getClass（）==String.class）{
returnsun.misc.Hashing.stringHash32（（String）k）;
}else{
inth=hashSeed^k.hashCode（）;
//ThisfunctionensuresthathashCodesthatdifferonlyby
//constantmultiplesateachbitpositionhaveabounded
//numberofcollisions（approximately8atdefaultloadfactor）.
h^=（h>>>20）^（h>>>12）;
returnh^（h>>>7）^（h>>>4）;
}
}else{
returnk.hashCode（）;
}
}
hash的计算和HashMap是一样的
判断是否存在给定值
publicsynchronizedbooleancontains（Objectvalue）{
if（value==null）{
thrownewNullPointerException（）;
}
Entrytab[]=table;
for（inti=tab.length;i-->0;）{
for（Entrye=tab[i];e!
=null;e=e.next）{
if（e.value.equals（value））{
returntrue;
}
}
}
returnfalse;
}
publicbooleancontainsValue（Objectvalue）{
returncontains（value）;
}
可以看到这里一旦发现value是null就直接抛出异常，这样直接说明HashTable是不允许null-value的。
另外该方法虽然是contains（），但是实际功能和containsValue（）是一样的，从containsValue（）的实现可以看出
给定的key是否存在
publicsynchronizedbooleancontainsKey（Objectkey）{
Entrytab[]=table;
inthash=hash（key）;
intindex=（hash&0x7FFFFFFF）%tab.length;
for（Entrye=tab[index];e!
=null;e=e.next）{
if（（e.hash==hash）&&e.key.equals（key））{
returntrue;
}
}
returnfalse;
}
当且仅当给定的key是存在的时候才返回true，但是注意一点的是这里所说的是否存在是取决于equals（）方法是如何实现的。
这和开头所强调的存入HashTable的key必须实现hashCode和equals方法是一致的.这里（hash&0x7FFFFFFF）的目的应该是为了保证hash是一个正值，毕竟只有第32位为0其他都是1
使用给定的key查找
publicsynchronizedVget（Objectkey）{
Entrytab[]=table;
inthash=hash（key）;
intindex=（hash&0x7FFFFFFF）%tab.length;
for（Entrye=tab[index];e!
=null;e=e.next）{
if（（e.hash==hash）&&e.key.equals（key））{
returne.value;
}
}
returnnull;
}
同HashMap，因为这里的底层实现结构都是一样的，都是基于数组，数组的每个下标对应一个单链表。
如果对应的key在HashTable中存在着对应的value那么返回找到的value，否则返回Null
扩容
protectedvoidrehash（）{
intoldCapacity=table.length;
Entry[]oldMap=table;
//overflow-consciouscode
intnewCapacity=（oldCapacity<<1）+1;
if（newCapacity-MAX_ARRAY_SIZE>0）{
if（oldCapacity==MAX_ARRAY_SIZE）
//KeeprunningwithMAX_ARRAY_SIZEbuckets
return;
newCapacity=MAX_ARRAY_SIZE;
}
Entry[]newMap=newEntry[newCapacity];
modCount++;
threshold=（int）Math.min（newCapacity*loadFactor,MAX_ARRAY_SIZE+1）;
booleancurrentAltHashing=useAltHashing;
useAltHashing=sun.misc.VM.isBooted（）&&
（newCapacity>=Holder.ALTERNATIVE_HASHING_THRESHOLD）;
booleanrehash=currentAltHashing^useAltHashing;
table=newMap;
for（inti=oldCapacity;i-->0;）{
for（Entryold=oldMap[i];old!
=null;）{
Entrye=old;
old=old.next;
if（rehash）{
e.hash=hash（e.key）;
}
intindex=（e.hash&0x7FFFFFFF）%newCapacity;
e.next=newMap[index];
newMap[index]=e;
}
}
}
当实际装入的键值对的个数超过了table的长度也就是容量capacity和装载因子的乘积，就会进行扩容，扩容过程是自动的，但是比较耗时。
扩增后的容量是最初的容量的2倍加1，这里和HashMap对比就很容易理解，HashMap的初始容量是偶数，而且要求容量一直是偶数，那么扩容的时候就直接扩大到原来的2倍。
相应的，HashTable的初始容量是奇数11，2倍之后变成偶数，所以加1。
不过这里没有要求HashTable的容量必须是奇数，但无论如何扩容后容量都会变成奇数
添加键值对
publicsynchronizedVput（Kkey,Vvalue）{
//Makesurethevalueisnotnull
if（value==null）{
thrownewNullPointerException（）;
}
//Makessurethekeyisnotalreadyinthehashtable.
Entrytab[]=table;
inthash=hash（key）;
intindex=（hash&0x7FFFFFFF）%tab.length;
for（Entrye=tab[index];e!
=null;e=e.next）{
if（（e.hash==hash）&&e.key.equals（key））{
Vold=e.value;
e.value=value;
returnold;
}
}
modCount++;
if（count>=threshold）{
//Rehashthetableifthethresholdisexceeded
rehash（）;
tab=table;
hash=hash（key）;
index=（hash&0x7FFFFFFF）%tab.length;
}
//Createsthenewentry.
Entrye=tab[index];
tab[index]=newEntry<>（hash,key,value,e）;
count++;
returnnull;
}
注意键和值都必须不能为NULL添加过程中如果发现给定的key已经存在，那么替换旧值并返回旧值，否则将新的键值对加入到HashTable，其中如果添加过程中发现实际键值对数目已经超过阈值，那么就进行扩容
删除键值对
publicsynchronizedVremove（Objectkey）{
Entrytab[]=table;
inthash=hash（key）;
intindex=（hash&0x7FFFFFFF）%tab.length;
for（Entrye=tab[index],prev=null;e!
=null;prev=e,e=e.next）{
if（（e.hash==hash）&&e.key.equals（key））{
modCount++;
if（prev!
=null）{
prev.next=e.next;
}else{
tab[index]=e.next;
}
count--;
VoldValue=e.value;
e.value=null;
returnoldValue;
}
}
returnnull;
}
如果找到了给定key对应的键值对，那么就做删除操作，如果没有找到，那么就什么也不做。
实际的删除过程就是单链表的节点删除
清空操作
publicsynchronizedvoidclear（）{
Entrytab[]=table;
modCount++;
for（intindex=tab.length;--index>=0;）
tab[index]=null;
count=0;
}
和HashMap的清空操作一样，只是将每个slot置为NULL，剩下的交给GC
比较两个HashTable是否相等
publicsynchronizedbooleanequals（Objecto）{
if（o==this）
returntrue;
if（!
（oinstanceofMap））
returnfalse;
Mapt=（Map）o;
if（t.size（）!
=size（））
returnfalse;
try{
Iterator>i=entrySet（）.iterator（）;
while（i.hasNext（））{
Map.Entrye=i.next（）;
Kkey=e.getKey（）;
Vvalue=e.getValue（）;
if（value==null）{
if（!
（t.get（key）==null&&t.containsKey（key）））
returnfalse;
}else{
if（!
value.equals（t.get（key）））
returnfalse;
}
}
}catch（ClassCastExceptionunused）{
returnlse;
}catch（NullPointerExceptionunused）{
returnfalse;
}
returntrue;
}
首先比较大小是否相等，如果大小相等，那么就依次比较实体集合中每个实体的是否是一样的键值对，如果所有的键值对都一样，那么就返回true，否则返回false，注意由于HashTable中数据存储并不是有序的，所以实际比较的时候使用的是get（）根据指定的key获取对应的value
获取HashTable的hashCode
publicsynchronizedinthashCode（）{
/*
*Thiscodedetectstherecursioncausedbycomputingthehashcode
*ofaself-referentialhashtableandpreventsthestackoverflow
*thatwouldotherwiseresult.Thisallowscertain1.1-era
*appletswithself-referentialhashtablestowork.Thiscode
*abusestheloadFactorfieldtododouble-dutyasahashCode
*inprogressflag,soasnottoworsenthespaceperformance.
*Anegativeloadfactorindicatesthathashcodecomputationis
*inprogress.
*/
inth=0;
if（count==0||loadFactor<0）
returnh;//Returnszero
loadFactor=-loadFactor;//MarkhashCodecomputationinprogress
Entry[]tab=table;
for（Entryentry:
tab）
while（entry!
=null）{
h+=entry.hashCode（）;
entry=entry.next;
}
loadFactor=-loadFactor;//MarkhashCodecomputationcomplete
returnh;
}
实际计算HashTable的hashCode是根据每个实体的hashCode来计算的，所有实体的hashCode（）之和就是HashTable的hashCode。
loadFractor扮演了一个标志位的角色，标志计算的开始和结束。
关于这里h+=entry.hashCode（）中h是否会溢出的问题，上面再hash（）函数中已经看到了每次求hash的时候都会与0x7fffffff，也就是说hash永远为正，不会溢出
序列化和反序列化
privatevoidwriteObject（java.io.ObjectOutputStreams）
throwsIOException{
EntryentryStack=null;
synchronized（this）{
//Writeoutthelength,threshold,loadfactor
s.defaultWriteObject（）;
//Writeoutlength,countofelements
s.writeInt（table.length）;
s.writeInt（count）;
//Stackcopiesoftheentriesinthetable
for（intindex=0;indexEntryentry=table[index];
while（entry!
=null）{
entryStack=
newEntry<>（0,entry.key,entry.value,entryStack）;
entry=entry.next;
}
}
}
//Writeoutthekey/valueobjectsfromthestackedentries
while（entryStack!
=null）{
s.writeObject（entryStack.key）;
s.writeObject（entryStack.value）;
entryStack=entryStack.next;
}
}
privatevoidreadObject（java.io.ObjectInputStreams）
throwsIOException,ClassNotFoundException
{
//Readinthelength,threshold,andloadfactor
s.defaultReadObject（）;
//sethashSeed
UNSAFE.putIntVolatile（this,HASHSEED_OFFSET,
sun.misc.Hashing.randomHashSeed（this））;
//Readtheoriginallengthofthearrayandnumberofelements
intoriglength=s.readInt（）;
intelements=s.readInt（）;
//Computenewsizewithabitofroom5%togrowbut
//nolargerthantheoriginalsize.Makethelength
//oddifit'slargeenough,thishelpsdistributetheentries.
升级会员 