HashMap实现原理分析文档格式.docx
《HashMap实现原理分析文档格式.docx》由会员分享，可在线阅读，更多相关《HashMap实现原理分析文档格式.docx（33页珍藏版）》请在冰点文库上搜索。
开放寻址法把所有的元素都存放在散列表中，也就是每个表项包含动态集合的一个元素（元素可以为NULL）。
1.在开放寻址法中，当要插入一个元素时，可以连续地检查散列表的个各项（连续检查是可以通过不同的算法获得偏移位），直到找到一个空槽来放置这个元素为止。
2.当查找一个元素时，要检查所有的表项，直到找到所需的元素，或者最终发现元素不在表中。
3.在开放寻址法中，对散列表元素的删除操作执行起来比较困难。
当我们从槽i中删除关键字时，不能仅将此位置元素置空。
因为这样做的话，会导致在无法判断此位置是否有元素。
应该用个特殊的值表示该元素已经删除。
Hi=（H（key）+di）MODm,[i=1,2，…，k（k<
=m-1）]
其中H（key）为散列函数，m为散列表长，di为增量序列，可有下列三种取法:
di=1,2,3，…，m-1，称线性探测再散列。
di=1^2,-1^2,2^2,-2^2，⑶^2，…，±
（k）^2,（k<
=m/2）称二次探测再散列。
di=伪随机数序列，称伪随机探测再散列。
1.3.2再散列法（再散列法）
产生碰撞时，再使用另一个散列函数计算地址，直到碰撞不再发生，这种方法不易产生“聚集”，但增加了计算时间（一个地址的产生可能会经过多个散列函数的计算）
Hi=Hn（key）,[n=1,2...,]
有一个包含一组哈希函数H1…Hn的集合。
当需要从哈希表中添加或获取元素时，首先使用哈希函数H1。
如果导致碰撞，则尝试使用H2，以此类推，直到Hn。
所有的哈希函数都与H1十分相似，不同的是它们选用的乘法因子。
1.3.3拉链法
产生碰撞时，把哈希到同一个槽中的所有元素都放到一个链表中。
拉链法采用额外的数据结构来处理碰撞，其将哈希表中每个位置（slot）都映射到了一个链表。
1.3.4公共溢出区
建立一个公共溢出区，当发生碰撞时，把碰撞元素放到缓冲区。
1.4负载因子
负载因子（loadfactor），它用来衡量哈希表的空/满程度，一定程度上也可以体现查询的效率，
计算公式为:
负载因子=总键值对数/箱子个数
负载因子越大，意味着哈希表越满，越容易导致冲突，性能也就越低。
因此，一般来说，当负载因子大于某个常数（可能是1，或者0.75等）时，哈希表将自动扩容。
2红黑树的复习
2.HashMap
2.1HashMap的定义
publicclassHashMap<
K,V>
extendsAbstractMap<
implementsMap<
Cloneable,Serializable{
/**
默认的哈希表的负载因子
*/
staticfinalfloatDEFAULT_LOAD_FACTOR=0.75f;
hashMap的最大容量
staticfinalintMAXIMUM_CAPACITY=1<
30;
hashMap的默认容量
staticfinalintDEFAULT_INITIAL_CAPACITY=1<
4;
//aka16
HashMap要调整的下一个容量大小
intthreshold;
hashMap容量的变量
哈希表负载因子的变量
finalfloatloadFactor;
构造一个具有默认初始容量（16）和默认加载因子（0.75）的HashMap
publicHashMap（）{
this.loadFactor=DEFAULT_LOAD_FACTOR;
//allotherfieldsdefaulted
}
构造一个带指定初始容量和默认加载因子（0.75）的HashMap。
publicHashMap（intinitialCapacity）{
this（initialCapacity,DEFAULT_LOAD_FACTOR）;
构造一个带指定初始容量和加载因子的HashMap。
publicHashMap（intinitialCapacity,floatloadFactor）{
if（initialCapacity<
0）
thrownewIllegalArgumentException（"
Illegalinitialcapacity:
"
+
initialCapacity）;
if（initialCapacity>
MAXIMUM_CAPACITY）
initialCapacity=MAXIMUM_CAPACITY;
if（loadFactor<
=0||Float.isNaN（loadFactor））
Illegalloadfactor:
loadFactor）;
this.loadFactor=loadFactor;
this.threshold=tableSizeFor（initialCapacity）;
publicHashMap（Map<
?
extendsK,?
extendsV>
m）{
putMapEntries（m,false）;
返回给定容量大小的下一个容量。
staticfinalinttableSizeFor（intcap）{
intn=cap-1;
n|=n>
1;
2;
8;
16;
return（n<
0）?
1:
（n>
=MAXIMUM_CAPACITY）?
MAXIMUM_CAPACITY:
n+1;
构造map的结构或者将map的内容全部赋值
evict初始化hashMap时是false，其余的情况为true。
finalvoidputMapEntries（Map<
m,booleanevict）{
ints=m.size（）;
if（s>
0）{
if（table==null）{//pre-size初始化空间
floatft=（（float）s/loadFactor）+1.0F;
intt=（（ft<
（float）MAXIMUM_CAPACITY）?
（int）ft:
MAXIMUM_CAPACITY）;
if（t>
threshold）
threshold=tableSizeFor（t）;
elseif（s>
threshold）//重新调整空间
resize（）;
for（Map.Entry<
e:
m.entrySet（））{
Kkey=e.getKey（）;
Vvalue=e.getValue（）;
putVal（hash（key）,key,value,false,evict）;
}
HashMap实现了Map接口，继承AbstractMap。
其中Map接口定义了键映射到值的规则，而AbstractMap类提供Map接口的骨干实现，以最大限度地减少实现此接口所需的工作。
在这里提到了两个参数：
初始容量，加载因子。
这两个参数是影响HashMap性能的重要参数，其中容量表示哈希表中桶的数量，初始容量是创建哈希表时的容量，加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度，它衡量的是一个散列表的空间的使用程度，负载因子越大表示散列表的装填程度越高，反之愈小。
对于使用链表法的散列表来说，查找一个元素的平均时间是O（1+a），因此如果负载因子越大，对空间的利用更充分，然而后果是查找效率的降低；
如果负载因子太小，那么散列表的数据将过于稀疏，对空间造成严重浪费。
系统默认负载因子为0.75，一般情况下我们是无需修改的。
2.2数据存储结构
HashMap是基于哈希表存储“Key－Value”对象应用的数据结构。
存入HashMap的键必须具备两个关键函数：
（1）equals（）：
判断两个Key是否相同，用来保证存入的Key的唯一性；
（2）hashCode（）：
genjkey-value对象的Key来计算其引用在散列表中存放的位置。
transientNode<
[]table;
staticclassNode<
implementsMap.Entry<
{
finalinthash;
finalKkey;
Vvalue;
Node<
next;
Node（inthash,Kkey,Vvalue,Node<
next）{
this.hash=hash;
this.key=key;
this.value=value;
this.next=next;
publicfinalKgetKey（）{returnkey;
publicfinalVgetValue（）{returnvalue;
publicfinalStringtoString（）{returnkey+"
="
+value;
publicfinalinthashCode（）{
returnObjects.hashCode（key）^Objects.hashCode（value）;
publicfinalVsetValue（VnewValue）{
VoldValue=value;
value=newValue;
returnoldValue;
publicfinalbooleanequals（Objecto）{
if（o==this）
returntrue;
if（oinstanceofMap.Entry）{
Map.Entry<
?
e=（Map.Entry<
）o;
if（Objects.equals（key,e.getKey（））&
&
Objects.equals（value,e.getValue（）））
returnfalse;
总结：
1.HashMap中有一个叫table的Node数组。
2.这个数组存储了Node类的对象。
HashMap类有一个叫做Node的内部类。
这个Node类包含了key-value作为实例变量。
3.每当往Hashmap里面存放key-value对的时候，都会为它们实例化一个Node对象，这个Node对象就会存储在前面提到的Node数组table中。
根据key的hashcode（）方法计算出来的hash值来决定。
hash值用来计算key在Entry数组的索引。
2.2.3resize
//不使用红黑树的阀值
staticfinalintUNTREEIFY_THRESHOLD=6;
//使用红黑树的阀值
staticfinalintTREEIFY_THRESHOLD=8;
finalNode<
[]resize（）{
[]oldTab=table;
intoldCap=（oldTab==null）?
0:
oldTab.length;
intoldThr=threshold;
intnewCap,newThr=0;
if（oldCap>
=MAXIMUM_CAPACITY）{
//hash表达到最大时，返回旧的hash表。
threshold=Integer.MAX_VALUE;
returnoldTab;
elseif（（newCap=oldCap<
1）<
MAXIMUM_CAPACITY&
oldCap>
=DEFAULT_INITIAL_CAPACITY）
//容量允许的时候，内存扩大一倍
newThr=oldThr<
//doublethreshold
elseif（oldThr>
0）//initialcapacitywasplacedinthreshold
//初始化带指定容量因子和碰撞因子的hashmap。
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<
ft<
（float）MAXIMUM_CAPACITY?
Integer.MAX_VALUE）;
threshold=newThr;
@SuppressWarnings（{"
rawtypes"
"
unchecked"
}）
[]newTab=（Node<
[]）newNode[newCap];
table=newTab;
if（oldTab!
=null）{
//循环遍历，将旧的hash表中的数据复制到新的hash表中。
for（intj=0;
j<
oldCap;
++j）{
e;
if（（e=oldTab[j]）!
oldTab[j]=null;
if（e.next==null）
newTab[e.hash&
（newCap-1）]=e;
elseif（eTreeNode）
（（TreeNode<
）e）.split（this,newTab,j,oldCap）;
else{//preserveorder
//拆分链表
loHead=null,loTail=null;
hiHead=null,hiTail=null;
do{
next=e.next;
//用（e.hash&
oldCap）规则切割链表，为零在loHead，否则在hiHead
if（（e.hash&
oldCap）==0）{
if（loTail==null）
loHead=e;
else
loTail.next=e;
loTail=e;
else{
if（hiTail==null）
hiHead=e;
hiTail.next=e;
hiTail=e;
}while（（e=next）!
=null）;
if（loTail!
loTail.next=null;
newTab[j]=loHead;
if（hiTail!
hiTail.next=null;
newTab[j+oldCap]=hiHead;
returnnewTab;
//拆分红黑树
finalvoidsplit（HashMap<
map,Node<
[]tab,intindex,intbit）{
TreeNode<
b=this;
//Relinkintoloandhilists,preservingorder
intlc=0,hc=0;
for（TreeNode<
e=b,next;
e!
=null;
e=next）{
next=（TreeNode<
）e.next;
e.next=null;
bit）==0）{
if（（e.prev=loTail）==null）
++lc;
if（（e.prev=hiTail）==null）
++hc;
if（loHead!
//UNTREEIFY_THRESHOLD使用红黑树的阀值
if（lc<
=UNTREEIFY_THRESHOLD）
tab[index]=loHead.untreeify（map）;
tab[index]=loHead;
if（hiHead!
=null）//（elseisalreadytreeified）
loHead.treeify（tab）;
if（hc<
tab[index+bit]=hiHead.untreeify（map）;
tab[index+bit]=hiHead;
=null）
hiHead.treeify（tab）;
//链表构造法
finalNode<
untreeify（HashMap<
map）{
hd=null,tl=null;
for（Node<
q=this;
q!
q=q.next）{
p=map.replacementNode（q,null）;
if（tl==null）
hd=p;
tl.next=p;
tl=p;
returnhd;
//红黑树的构造方法
finalvoidtreeify（Node<
[]tab）{
root=null;
x=this,next;
x!
x=next）{
）x.next;
x.left=x.right=null;
if（root==null）{
x.parent=null;
x.red=false;
root=x;
Kk=x.key;
inth=x.hash;
Class<
kc=null;
p=root;
;
）{
intdir,ph;
Kpk=p.key;
if（（ph=p.hash）>
h）
dir=-1;
elseif（ph<
dir=1;
elseif（（kc==null&
（kc=comparableClassFor（k））==null）||
（dir=compareComparables（kc,k,pk））
升级会员 