HashMap实现原理分析文档格式.docx
- 文档编号:972986
- 上传时间:2023-04-29
- 格式:DOCX
- 页数:33
- 大小:30.44KB
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))
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- HashMap 实现 原理 分析