HashMap整体结构的学习总结

首先是HashMa的整体结构：
主体采用数组进行存储。
当数组处的节点产生碰撞，会向下延伸，生成一条链表
当超过成树阈值（8）且数组长度大于64后，采用红黑树进行存储（红黑树的结构复杂，但是查找效率高）HashTable的创建
jdk8以前：在创建的时候就会有一个Entry[]table来存储
jdk8以后：会在第一次ut方法被调用的时候创建Entry[]数组
数据的存储
通过Key的hashCode方法计算出值，再通过某种算法计算出数组中存储数据的空间的索引值，如果没有数据则存储。
计算索引的方式：key的hashCode方法计算出hash值，再用hash值与数组长度进行无符号右移(>>>)，按位异或（^）、按位与（&am;）计算出索引
如果key已经存在–检查hashCode是否一致。一致则更新数据
如果不一致，将会在索引位置上，生成一条链表来存储数据。
同时，会执行拉链法的数据查找，再这一条链表上进行key的equals方法比较（同时比较value和hashCode）。相等才进行数据更新HashMa的插入过程
为什么初始数组长度必须为2的n次方？
hash&am;（length-1）使数组分布更加均匀，有效的减少了碰撞的发生
采用取余：hash&am;(length-1)==hash%length（当为2的n次幂时）但是位运算效率高很多求近位数的算法
在算法之前会执行一次与MAXIMUM_CAPACITY的比较，超过则代入MAXIMUM_CAPACITY
staticfinalinttableSizeFor(intca){
intn=ca-1;
n|=n>>>1;
n|=n>>>2;
n|=n>>>4;
n|=n>>>8;
n|=n>>>16;
turn(n<0)?1:(n>=MAXIMUM_CAPACITY)?MAXIMUM_CAPACITY:n+1;
}算法执行过程：总共执行了32次移位操作HashMa常见参数
根据泊松分布来确认，链表超过8的概率非常小。因为红黑树的空间占用比较大树化为8，链化是6当链表长度大于8会转换成红黑树
staticfinalintTREEIFY_THRESHOLD=8;
当红黑树的大小小于6的时候会转化成链表
staticfinalintUNTREEIFY_THRESHOLD=6;
数组长度大于64才可以转化为红黑树
staticfinalintMIN_TREEIFY_CAPACITY=64;
HashMa的size不是指数组长度，而是指当前存储的节点个数
intsize;
容量*负载因子
intthshd;
负载因子0~1之间
intloadFactor;loadFactor–加载因子：
表示HashMa的稀疏程度，影响hash操作到同一个数组位置的概率
默认是0.75f，不建议修改。官方给出的一个比较科学的
数组的扩容是一个非常复杂的操作，很消耗性能，需要尽量避免hashma的扩容过大–数组太满，容易发生碰撞。链表会较多。影响查询性能
过小–数组会经常扩容，耗费时间HashMa的构造方法
ubcHashMa(intinitialCaacity){
this(initialCaacity,DEFAULT_LOAD_FACTOR);
}
尽量先预估存储的数值区间，再来创建HashMa，避免扩容操作finalvoidutMaEntries(Ma<?extendsK,?extendsV>m,boeanevict){
ints=m.size();
if(s>0){
if(table==nl){-size
之所以要+1.0f，主要是为了避免tableSizeFor中更新index的时候产生的扩容
floatft=((float)sloadFactor)+1.0F;
intt=((ft<(float)MAXIMUM_CAPACITY)?
(int)ft:MAXIMUM_CAPACITY);
if(t>thshd)
thshd=tableSizeFor(t);
}
elseif(s>thshd)
size();
for(Ma.Entry<?extendsK,?extendsV>e:m.entrySet()){
Kkey=e.getKey();
Vvalue=e.getValue();
utVal(hash(key),key,value,false,evict);
}
}
}成员方法
ut方法（重点）
hash值计算
staticfinalinthash(Objectkey){
主要目的：防止高位变化较大，而低位变化较小，从而导致hash冲突
inth;
turn(key==nl)?0:(h=key.hashCode())^(h>>>16);
}
finalVutVal(inthash,Kkey,Vvalue,boeanonlyIfAbsent,
boeanevict){
Node<K,V>[]tab;Node<K,V>;intn,i;
if((tab=table)==nl||(n=tab.length)==0)
在第一次ut的时候会创建Node数组
n=(tab=size()).length;
这里执行了hash计算的操作。没有出现碰撞
已经在这里实现了赋值，就是hash计算后的节点
if((=tab[i=(n-1)&am;hash])==nl)
如果没有碰撞，则直接ut
这里的nl代表的是拉链法链表的下一个结点暂时为nl（还没有碰撞产生）
tab[i]=newNode(hash,key,value,nl);
else{
Node<K,V>e;Kk;
判断key是否相同
if(.hash==hash&am;&am;
如果key相同或者key与k相等
((k=.key)==key||(key!=nl&am;&am;key.equals(k))))
e=;
判断是否是树节点
elseif(instanceofTeNode)
e=((TeNode<K,V>)).utTeVal(this,tab,hash,key,value);
else{
链表遍历
for(intbinCount=0;;++binCount){
if((e=.next)==nl){
.next=newNode(hash,key,value,nl);
如果结点大于8，那么链表成树
if(binCount>=TREEIFY_THRESHOLD-1)-1for1st
teifyBin(tab,hash);
eak;
}
链表上出现相同的key
if(e.hash==hash&am;&am;
((k=e.key)==key||(key!=nl&am;&am;key.equals(k))))
eak;
=e;
}
}
如果当前位置存在结点
if(e!=nl){existingmaingforkey
只修改值
VdValue=e.value;
if(!onlyIfAbsent||dValue==nl)
e.value=value;
afterNodeAccess(e);
turndValue;
}
}
记录ma的修改次数
++modCount;
插入成功，size+1，当大于阈值，执行扩容
if(++size>thshd)
size();
afterNodeInsertion(evict);
turnnl;
}红黑树转换
finalvoidteifyBin(Node<K,V>[]tab,inthash){
intn,index;Node<K,V>e;
如果数组长度小于64，会执行扩容，而不是建树
if(tab==nl||(n=tab.length)<MIN_TREEIFY_CAPACITY)
size();倍增扩容
判断当前桶中的节点是否为nl
elseif((e=tab[index=(n-1)&am;hash])!=nl){
hd--头结点，tl--尾结点
TeNode<K,V>hd=nl,tl=nl;
将链表里的每一个节点替换成TeNode
do{
将Node转换为TeNode
TeNode<K,V>=lacementTeNode(e,nl);
作为树的根节点
if(tl==nl)
hd=;
else{.v=tl;
tl.next=;
}
tl=;
}while((e=e.next)!=nl);
如果根节点不为空，执行建树
if((tab[index]=hd)!=nl)
hd.teify(tab);
}
}扩容方法-size
finalNode<K,V>[]size(){
Node<K,V>[]dTab=table;
intdCa=(dTab==nl)?0:dTab.length;
intdThr=thshd;
新的容量和阈值
intnewCa,newThr=0;
if(dCa>0){
进行扩容。如果超过最大容量，那么不变，阈值变为最大
if(dCa>=MAXIMUM_CAPACITY){
thshd=Integer.MAX_VALUE;
turndTab;
}
如果扩容后满足条件，那么新阈值等于旧阈值翻倍
elseif((newCa=dCa<<1)<MAXIMUM_CAPACITY&am;&am;
dCa>=DEFAULT_INITIAL_CAPACITY)
newThr=dThr<<1;doublethshd
}
通过阈值的方式来创建HashMa
elseif(dThr>0)initialcaacitywaslacedinthshd
newCa=dThr;
else{zeroinitialthshdsignifiesusingdefats
阈值为零，那么使用默认值
newCa=DEFAULT_INITIAL_CAPACITY;
newThr=(int)(DEFAULT_LOAD_FACTOR*DEFAULT_INITIAL_CAPACITY);
}
扩容超界或者旧容量小于默认容量
if(newThr==0){
floatft=(float)newCa*loadFactor;
newThr=(newCa<MAXIMUM_CAPACITY&am;&am;ft<(float)MAXIMUM_CAPACITY?
(int)ft:Integer.MAX_VALUE);
}
thshd=newThr;
@SussWarnings({"rawtyes","unchecked"})
重新创建数组
Node<K,V>[]newTab=(Node<K,V>[])newNode[newCa];
table=newTab;
if(dTab!=nl){
将旧数组的数组放到新数组里
for(intj=0;j<dCa;++j){
Node<K,V>e;
if((e=dTab[j])!=nl){
dTab[j]=nl;
if(e.next==nl)
newTab[e.hash&am;(newCa-1)]=e;
elseif(einstanceofTeNode)
树节点建树
((TeNode<K,V>)e).st(this,newTab,j,dCa);
else{serveorder
链表复制
Node<K,V>loHead=nl,loTail=nl;
Node<K,V>hiHead=nl,hiTail=nl;
Node<K,V>next;
do{
next=e.next;
变化的高位为0
if((e.hash&am;dCa)==0){
if(loTail==nl)
loHead=e;
else
loTail.next=e;
loTail=e;
}
else{
高位变为1
if(hiTail==nl)
hiHead=e;
else
hiTail.next=e;
hiTail=e;
}
}while((e=next)!=nl);
if(loTail!=nl){
loTail.next=nl;
将结点放在原位置
newTab[j]=loHead;
}
if(hiTail!=nl){
hiTail.next=nl;
将节点放在原位置+旧容量的地方
newTab[j+dCa]=hiHead;
}
}
}
}
}
turnnewTab;
}
在扩容时，不需要重新计算hash，只需要看原来的hash新增的那个高位bit是1还是0.0索引不变
1变成”原索引+dCa“HashMa问题整理设置初始化参数如果要存储7个元素。那么初始化值最好设置为70.75+1.0f=10补充，链表的头插法和尾插法：
头插法：（Jdk1.7）相当于将其他结点往后移，然后从首部插入结点–考虑到新插入的节点可能会被优先访问到
voidaddEntry(inthash,Kkey,Vvalue,intbucketIndex){
if((size>=thshd)&am;&am;(nl!=table[bucketIndex])){
size(2*table.length);
hash=(nl!=key)?hash(key):0;
bucketIndex=indexFor(hash,table.length);
}cateEntry(hash,key,value,bucketIndex);
}voidcateEntry(inthash,Kkey,Vvalue,intbucketIndex){
Entry<K,V>e=table[bucketIndex];
table[bucketIndex]=newEntry<>(hash,key,value,e);
size++;
}头插法的问题：在多线程的情况下，在扩容的时候，会导致环形链表的出现，最终导致线程死锁尾插法：（jdk1.8）遍历到链表尾部添加结点。
这是utVal方法中的一段：
for(intbinCount=0;;++binCount){
其实就是遍历到尾部进行插入，保证链表的顺序
if((e=.next)==nl){
.next=newNode(hash,key,value,nl);
if(binCount>=TREEIFY_THRESHOLD-1)-1for1st
teifyBin(tab,hash);
eak;
}
if(e.hash==hash&am;&am;
((k=e.key)==key||(key!=nl&am;&am;key.equals(k))))
eak;
=e;
}