HashMap源码学习-阿里云开发者社区

首先实现map的子类：HashMap、HashTable、TreeMap、LinkedHashMap。

这几个类中HashMap与HashTable的区别：

线程上：HashMap是线程不安全的，而HashTable是安全的。key、value的支持：HashMap的key、balue可以为空，而HashTable是key、value不可以为空的。底层数据结构：HashMap采用数组+链表+红黑树，当链表的长度>=8的时候会考虑是否转成红黑树，而HashTable则没有。初始化容量上：HashTable的初始化容量是11，同时扩容变为原来的2n+1，HashMap的初始化容量是16，同时扩容扩容成原来的2倍。而当给定初始化容量时，HashTable是直接给定初始化容量，而HashMap是将给定的初始化容量变成2的次幂。

jdk7和jdk8之间，jdk8引入了红黑树，同时jdk7中的transform( )方法变成了resize( )方法。什么是红黑树，同时数组什么时候会加入链表，链表和数组满足什么条件时，链表会变成红黑树，什么时候红黑树又会变成链表。同时如果给定初始化容量，给成怎样会才合理。

一、HashMap相关变量

//默认初始化容量2^4 =16，做左移位运算staticfinalintDEFAULT_INITIAL_CAPACITY=1<<4;
//最大容量 2^30staticfinalintMAXIMUM_CAPACITY=1<<30;
//默认加载因子 0.75staticfinalfloatDEFAULT_LOAD_FACTOR=0.75f;
//需要变成红黑树的链表阀值 8staticfinalintTREEIFY_THRESHOLD=8;
//将红黑树变成链表的阀值 6staticfinalintUNTREEIFY_THRESHOLD=6;
//变成红黑树除了满足链表达到8，而且数组需要//达到64，最小转成红黑树的数组长度64staticfinalintMIN_TREEIFY_CAPACITY=64;
//数组，又称为bucket，桶，2的次幂transientNode<K,V>[] table;
//entrySet：k、v对的集合transientSet<Map.Entry<K,V>>entrySet;
//map的长度transientintsize;
//修改次数transientintmodCount;
//阀值  threshold = capacity*loadFactorintthreshold;
//加载因子finalfloatloadFactor;

二、构造函数

//构造函数,对传入的加载因子和初始化容量校验publicHashMap(intinitialCapacity,floatloadFactor){//如果初始容量<0，则抛异常if (initialCapacity<0)
thrownewIllegalArgumentException(
"Illegal initial capacity: "+initialCapacity);
//如果初始容量>最大容量，则将最大容量赋值给初始化容量if (initialCapacity>MAXIMUM_CAPACITY)
initialCapacity=MAXIMUM_CAPACITY;
//加载因子如果小于0或者加载因子为空，则抛异常if (loadFactor<=0||Float.isNaN(loadFactor))
thrownewIllegalArgumentException(
"Illegal load factor: "+loadFactor);
this.loadFactor=loadFactor;
this.threshold=tableSizeFor(initialCapacity);
}
//将传入的容量变成2的n次幂staticfinalinttableSizeFor(intcap) {
//向减去1，比如避免16变成32intn=cap-1;
n|=n>>>1;
n|=n>>>2;
n|=n>>>4;
n|=n>>>8;
n|=n>>>16;
//之后判断如果大于最大值，变成最大值，//否者变成n+1,也即变成2的次幂的形式return (n<0) ?1 : (
n>=MAXIMUM_CAPACITY) ?MAXIMUM_CAPACITY:n+1;
}
//构造hashMap,传入初始化容量，默认的加载因子publicHashMap(intinitialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//构造hash，加载因子默认，容量默认publicHashMap() {
this.loadFactor=DEFAULT_LOAD_FACTOR;
}
//构造一个HashMap：加载因子为默认加载因子publicHashMap(Map<?extendsK, ?extendsV>m) {
this.loadFactor=DEFAULT_LOAD_FACTOR;
//放入传入的map信息、putMapEntries(m, false);
}
finalvoidputMapEntries(Map<?extendsK, ?extendsV>m, booleanevict) {
//拿到map为m的长度ints=m.size();
//如果长度>0,则判断是否为空if (s>0) {
if (table==null) { // pre-size//拿到ft=长度/加载因子+1floatft= ((float)s/loadFactor)+1.0F;
//如果ft<最大容量，则为ft合理的长度intt= ((ft< (float)MAXIMUM_CAPACITY) ?                   (int)ft : MAXIMUM_CAPACITY);
//如果t>阀值，则需要进行初始化，变成2的次幂，// 类似于扩容，考虑到为变成16的情况if (t>threshold)
threshold=tableSizeFor(t);
         }
//否者，s>阀值，则会进行扩容操作elseif (s>threshold)
resize();
//拿到key、value的值，执行put操作for (Map.Entry<?extendsK, ?extendsV>e : m.entrySet()) {
Kkey=e.getKey();
Vvalue=e.getValue();
//进行put操作,添加元素信息putVal(hash(key), key, value,false,evict);
            }
        }
    }

三、方法

put方法

publicVput(Kkey, Vvalue) {
returnputVal(hash(key),
key, value, false, true);
}
//注意到onlyIfAbsent为false，则可以进行值的替换，// 如果设置为true，则不可以进行修改value的值finalVputVal(inthash, Kkey, Vvalue,
booleanonlyIfAbsent,booleanevict){
//定义变量Node<K,V>[] tab; Node<K,V>p; intn, i;
//如果table(数组)为空，则进行resize()进行初始化if ((tab=table) ==null|| (n=tab.length)==0)
n= (tab=resize()).length;
//(n-1)&hash，相当于对其进行取模，放入到哪个数组中if ((p=tab[i= (n-1) &hash]) ==null)
//放入到数组中tab[i] =newNode(hash, key, value, null);
//如果不为空else {
Node<K,V>e; Kk;
//如果key存在同时hash值相同，//也即数组中已经有元素存在时，//则更新value的值if (p.hash==hash&&    ((k=p.key)==key||(key!=null&&key.equals(k))))
e=p;
//如果元素属于树节点，则进行红黑树的判断，执//行红黑树操作elseif (pinstanceofTreeNode)
e=((TreeNode<K,V>)p).putTreeVal(this,tab, 
hash, key, value);
//否者执行链表操作，元素在链表中else {
//遍历链表for (intbinCount=0; ; ++binCount){
//遍历到链表尾部if ((e=p.next) ==null) {
//为元素创建信息节点p.next=newNode(hash, key, value, null);
//如果binCount个数，也即//链表个数>=8时，则进行红黑树操作if (binCount>=TREEIFY_THRESHOLD-1)
//执行红黑树操作，首先会去判断数组的// 长度是否>=64,执行完进行断开treeifyBin(tab, hash);
break;
                }
//如果待插入的key在链表中找到，则退出循环if (e.hash==hash&&                 ((k=e.key) ==key|| (key!=null&&key.equals(k))))
break;
//与前面的e = p.next构成循环p=e;
            }
        }
//如果e存在，则将新值替换旧值if (e!=null) {
VoldValue=e.value;
//判断是否替换成新值if(!onlyIfAbsent||oldValue==null)
//替换旧值为新值e.value=value;
//回调函数，留给LInkedHashMap实现afterNodeAccess(e);
returnoldValue;
        }
    }
//修改次数自增++modCount;
//size>阀值，进行扩容操作if (++size>threshold)
resize();
//回调函数，留给LinkedHashMap实现afterNodeInsertion(evict);
returnnull;
}
/*** Tree version of putVal.*///红黑树的put放入方法finalTreeNode<K,V>putTreeVal(HashMap<K,V>map, 
Node<K,V>[] tab,inth, Kk, Vv){
Class<?>kc=null;
booleansearched=false;
//获取根节点TreeNode<K,V>root=(parent!=null)?root():this;
//从根节点进行遍历for (TreeNode<K,V>p=root;;) {
intdir, ph; Kpk;
//hash值下小于父节点的hash值，则取左节点if ((ph=p.hash) >h)
dir=-1;
//如果hash值大于父节点hash值，则取右节点elseif (ph<h)
dir=1;
//如果hash相等，继续比较键值是否相等，//如果相等则说明存在相同的键值，则直接返回//当前节点的值elseif((pk=p.key)==k||(k!=null&&k.equals(pk)))
returnp;
//如果hash值相等，但是key不相等elseif ((kc==null&&//key没有实现Comparable比较接口      (kc=comparableClassFor(k)) ==null) ||//或者已经实现Comparable//比较接口，同时等于0//则不能进行key的顺序判断，//因此无法判断，会产生hash碰撞    (dir=compareComparables(kc, k, pk)) ==0){
//判断是否执行过查找方法if (!searched) {
TreeNode<K,V>q, ch;
//如果执行过，则分别查找左//右树，查看是否有相同的对象，//如果找不到，则说明确实//没有找到相同对象存在searched=true;
if (((ch=p.left) !=null&&              (q=ch.find(h, k, kc)) !=null)||               ((ch=p.right) !=null&&               (q=ch.find(h, k, kc)) !=null))
returnq;
            }
//hash相同，key不相等，//并且key没有实现Comparable接口，//保持一致的处理规则，//以便进行排序，从而进行遍历dir=tieBreakOrder(k, pk);
        }
//备份当前节点TreeNode<K,V>xp=p;
//如果遍历完之后还是没有//找到相同的key的节点，则进行新的插入操作if((p=(dir<=0) ?p.left : p.right)==null){
Node<K,V>xpn=xp.next;
TreeNode<K,V>x=map.newTreeNode(h,k,v,xpn);
//备份当前节点的下一个//节点；给LinkedHashMap预留的if (dir<=0)
xp.left=x;
elsexp.right=x;
//将当前节点的next节点指向新节点xp.next=x;
//设置新的父节点和当前节点为当前节点x.parent=x.prev=xp;
//如果当前节点还是后继节点，// 则将新节点作为当前节点的前驱节点if (xpn!=null)
                ((TreeNode<K,V>)xpn).prev=x;
//实现红黑树重排实现重平衡moveRootToFront(tab, balanceInsertion(root, x));
returnnull;
        }
    }
}
//进行数组长度64的判断，如果成立，则将链表转换为红黑树finalvoidtreeifyBin(Node<K,V>[] tab, inthash) {
intn, index; Node<K,V>e;
//如果数组长度<64，则进行扩容操作if(tab==null||(n=tab.length)<MIN_TREEIFY_CAPACITY)
resize();
//否者进行红黑树操作elseif((e=tab[index=(n-1) &hash]) !=null){
TreeNode<K,V>hd=null, tl=null;
do {
//创建红黑树节点TreeNode<K,V>p=replacementTreeNode(e,null);
//将第一个节点作为头结点，并取出原//链表的元素，重排成双向链表if (tl==null)
hd=p;
else {
//否者进行前驱和后继操作p.prev=tl;
tl.next=p;
            }
tl=p;
        } while ((e=e.next) !=null);
//如果根节点不为空，则进行红黑树的重平衡操作if ((tab[index] =hd) !=null)
hd.treeify(tab);
    }
}
/*** Forms tree of the nodes linked from this node.* @return root of tree*///进行重平衡操作finalvoidtreeify(Node<K,V>[] tab) {
TreeNode<K,V>root=null;
for (TreeNode<K,V>x=this, next; x!=null; x=next) {
next= (TreeNode<K,V>)x.next;
x.left=x.right=null;
if (root==null) {
x.parent=null;
x.red=false;
root=x;
        }
else {
Kk=x.key;
inth=x.hash;
Class<?>kc=null;
for (TreeNode<K,V>p=root;;) {
intdir, ph;
Kpk=p.key;
if ((ph=p.hash) >h)
dir=-1;
elseif (ph<h)
dir=1;
elseif ((kc==null&&          (kc=comparableClassFor(k))==null)||          (dir=compareComparables(kc,k,pk))==0)
dir=tieBreakOrder(k, pk);
TreeNode<K,V>xp=p;
if ((p=(dir<=0)?p.left:p.right)==null){
x.parent=xp;
if (dir<=0)
xp.left=x;
elsexp.right=x;
root=balanceInsertion(root,x);
break;
                }
            }
        }
    }
moveRootToFront(tab, root);
}
//将root节点放到哈希表的首元素static<K,V>voidmoveRootToFront(Node<K,V>[]tab,  
TreeNode<K,V>root) {
intn;
if(root!=null&&tab!=null&& (n=tab.length)>0){
intindex= (n-1) &root.hash;
TreeNode<K,V>first=(TreeNode<K,V>)tab[index];
if (root!=first) {
Node<K,V>rn;
tab[index] =root;
TreeNode<K,V>rp=root.prev;
if ((rn=root.next) !=null)
                ((TreeNode<K,V>)rn).prev=rp;
if (rp!=null)
rp.next=rn;
if (first!=null)
first.prev=root;
root.next=first;
root.prev=null;
        }
assertcheckInvariants(root);
    }
}
//树节点查找finalTreeNode<K,V>find(inth,Objectk,
Class<?>kc){
TreeNode<K,V>p=this;
//进行do-while循环找到相要的元素do {
intph, dir; Kpk;
TreeNode<K,V>pl=p.left, pr=p.right, q;
//hash值小于当前节点，则在左节点进行比较，否者在右节点比较if ((ph=p.hash) >h)
p=pl;
elseif (ph<h)
p=pr;
//否者是当前的节点，直接返回elseif((pk=p.key)==k||(k!=null&&k.equals(pk)))
returnp;
//左节点为空，则遍历右节点elseif (pl==null)
p=pr;
//右节点为空，则遍历左节点elseif (pr==null)
p=pl;
//如果实现了Comparable接口，//则更加compareTo比较出来的大小获取顺序elseif ((kc!=null||         (kc=comparableClassFor(k))!=null) &&         (dir=compareComparables(kc, k, pk))!=0)
p= (dir<0) ?pl : pr;
//如果没有则采用find()放到进行返回elseif ((q=pr.find(h, k, kc))!=null)
returnq;
elsep=pl;
    } while (p!=null);
returnnull;
}

扩容操作

//进行扩容操作finalNode<K,V>[] resize() {
//老的数组Node<K,V>[] oldTab=table;
intoldCap=(oldTab==null)?0:oldTab.length;
intoldThr=threshold;
intnewCap, newThr=0;
//首先老的容量是否大于0，如果大于0，//则进行最大容量判断，如果最大容量判断不为空，// 则将阀值设置为最大容量，返回老容量if (oldCap>0) {
if (oldCap>=MAXIMUM_CAPACITY) {
threshold=Integer.MAX_VALUE;
returnoldTab;
        }
//否者对新容量进行做位运算左移一位，扩容2倍//如果小于最大容量，同时老容量大于默认初始化容量，//则阀值扩容成原来的2倍elseif((newCap=oldCap<<1<MAXIMUM_CAPACITY&&oldCap>=DEFAULT_INITIAL_CAPACITY)
newThr=oldThr<<1; //double threshold    }
//如果老阀值大于0，则新容量等于老阀值elseif (oldThr>0)
newCap=oldThr;
else {//否者没有进行初始容量，则//采用默认容量16，新的阀值为16*0.75newCap=DEFAULT_INITIAL_CAPACITY;
newThr=(int)(DEFAULT_LOAD_FACTOR*DEFAULT_INITIAL_CAPACITY);
    }
//如果新的阀值为0，则采用默认的if (newThr==0) {
floatft= (float)newCap*loadFactor;
newThr= (newCap<MAXIMUM_CAPACITY&&ft< (float)MAXIMUM_CAPACITY?                (int)ft : Integer.MAX_VALUE);
    }
//采用新的阀值threshold=newThr;
//创建一个新的数组,同时 newCap = 0,方便扩容使用@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab=(Node<K,V>[])newNode[newCap];
//数组等于新的tabtable=newTab;
//原来的hash表不为空时，将原来的元素复制//到新的hash表中if (oldTab!=null) {
for (intj=0; j<oldCap; ++j) {
Node<K,V>e;
if ((e=oldTab[j]) !=null) {
//将原来的元素置空oldTab[j] =null;
//如果当前元素的后继为空，将e放//入到取模的新数组中if (e.next==null)
newTab[e.hash&(newCap-1)]=e;
//如果为树节点，则进行//红黑树的扩容操作elseif(einstanceofTreeNode)
                 ((TreeNode<K,V>)e).split(this                 ,newTab, j, oldCap);
//保持顺序else { // preserve order//lohead指low的低位的头//结点，loTail表示低位的尾节点Node<K,V>loHead=null, loTail=null;
//hihead指low的高位的头结点，//hiTail表示高位的尾节点Node<K,V>hiHead=null,hiTail=null;
//下一个节点Node<K,V>next;
//取模只可能出现0或者1的情况do {
//e元素的前驱节点next=e.next;
//如hash值对老容量取余为0//，则放入到低位的链表中if((e.hash&oldCap)==0){
if (loTail==null)
loHead=e;
elseloTail.next=e;
loTail=e;
                        }
//否者则说明hash值对老容量取模不为0，//也就是为1的情况，放在高位的链表中else {
if (hiTail==null)
hiHead=e;
elsehiTail.next=e;
hiTail=e;
                        }
                    } while ((e=next) !=null);
if (loTail!=null) {
//遍历完成分化两个链表//低位链表在新的哈希表//中的位置与旧哈希表一样loTail.next=null;
newTab[j] =loHead;
                    }
//高位链表在新哈希表中//的位置为原来的位置+oldcapif (hiTail!=null) {
hiTail.next=null;
newTab[j+oldCap]=hiHead;
                    }
                }
            }
        }
    }
returnnewTab;
}
//将树中的节点拆分为较高和较低的树，//如果现在太小，则取消树化。仅从调整//大小调用。也即进行树变链表和链表转成树的操作finalvoidsplit(HashMap<K,V>map,
Node<K,V>[] tab, intindex, intbit) {
//获取当前元素TreeNode<K,V>b=this;
//低位、高位的头结点和尾节点TreeNode<K,V>loHead=null, loTail=null;
TreeNode<K,V>hiHead=null, hiTail=null;
intlc=0, hc=0;
//从根节点开始遍历红黑树，//统计出需要放到低位和需要移动到高位的元素个数//进行红黑树操作或者红黑树转链表操作for (TreeNode<K,V>e=b, next; e!=null; 
e=next) {
next= (TreeNode<K,V>)e.next;
e.next=null;
if ((e.hash&bit) ==0) {
if ((e.prev=loTail) ==null)
loHead=e;
elseloTail.next=e;
loTail=e;
++lc;
        }
else {
if ((e.prev=hiTail) ==null)
hiHead=e;
elsehiTail.next=e;
hiTail=e;
++hc;
        }
    }
//如果低位头结点不为//空，则进行低位操作if (loHead!=null) {
//小于红黑树阀值时，//则不满足红黑树操作，转链表if (lc<=UNTREEIFY_THRESHOLD)
tab[index] =loHead.untreeify(map);
//否者进行红黑树操作，//将低位头结点放入到hash表中else {
tab[index] =loHead;
//如果高位头结点不为//空，则进行重平衡操作if (hiHead!=null) 
loHead.treeify(tab);
        }
    }
//如果高位头结点不为空，则进行高位操作，//如果不满足红黑树阀值，则进行转链表操作//否者进行红黑树重平衡操作if (hiHead!=null) {
if (hc<=UNTREEIFY_THRESHOLD)
tab[index+bit]=hiHead.untreeify(map);
else {
tab[index+bit] =hiHead;
if (loHead!=null)
hiHead.treeify(tab);
        }
    }
}
//将树转成链表finalNode<K,V>untreeify(HashMap<K,V>map) {
Node<K,V>hd=null, tl=null;
for(Node<K,V>q=this; q!=null; q=q.next){
Node<K,V>p=map.replacementNode(q, null);
if (tl==null)
hd=p;
elsetl.next=p;
tl=p;
    }
returnhd;
}

remove操作

//进行删除操作publicVremove(Objectkey) {
Node<K,V>e;
return(e=removeNode(hash(key),key,null,false,
true))==null?null : e.value;
}
//删除节点信息finalNode<K,V>removeNode(inthash, Objectkey,
Objectvalue,booleanmatchValue,booleanmovable){
Node<K,V>[] tab; Node<K,V>p; intn, index;
//如果hash表、表长度不为空，//同时hash取模不为空，则进行移除操作if ((tab=table)!=null&& (n=tab.length)>0&&      (p=tab[index=(n-1) &hash])!=null) {
Node<K,V>node=null, e; Kk; Vv;
//找到该元素进行存放if (p.hash==hash&& ((k=p.key)==key||(key!=null&&key.equals(k))))
node=p;
//如果当前节点的下一个节点不//为空，则有可能为树节点，或者链表elseif ((e=p.next) !=null) {
//树节点，拿到该元素信息if (pinstanceofTreeNode)
node=(TreeNode<K,V>)p).getTreeNode(hash,key);
//链表，拿到该元素else {
do {
if (e.hash==hash&&                   ((k=e.key) ==key||                    (key!=null&&key.equals(k)))) {
node=e;
break;
                    }
p=e;
                } while ((e=e.next) !=null);
            }
        }
//拿到之后，进行删除操作if (node!=null&& (!matchValue|| (
v=node.value) ==value||           (value!=null&&value.equals(v)))){
if (nodeinstanceofTreeNode)
 ((TreeNode<K,V>)node).removeTreeNode(
this, tab,movable);
elseif (node==p)
tab[index] =node.next;
elsep.next=node.next;
++modCount;
--size;
afterNodeRemoval(node);
returnnode;
        }
    }
returnnull;
}
//树节点查找finalTreeNode<K,V>getTreeNode(inth,Objectk){
return ((parent!=null) ?root() : this).find(h, k, null);
}
//树节点查找finalTreeNode<K,V>find(inth,Objectk,
Class<?>kc){
TreeNode<K,V>p=this;
//进行do-while循环找到相要的元素do {
intph, dir; Kpk;
TreeNode<K,V>pl=p.left, pr=p.right,q;
//hash值小于当前节点，//则在左节点进行比较，否者在右节点比较if ((ph=p.hash) >h)
p=pl;
elseif (ph<h)
p=pr;
//否者是当前的节点，直接返回elseif ((pk=p.key) ==k||              (k!=null&&k.equals(pk)))
returnp;
//左节点为空，则遍历右节点elseif (pl==null)
p=pr;
//右节点为空，则遍历左节点elseif (pr==null)
p=pl;
//如果实现了Comparable接口，//则更加compareTo比较出来的大小获取顺序elseif ((kc!=null||         (kc=comparableClassFor(k))!=null) &&         (dir=compareComparables(kc, k, pk))!=0)
p= (dir<0) ?pl : pr;
//如果没有则采用find()放到进行返回elseif ((q=pr.find(h, k, kc))!=null)
returnq;
elsep=pl;
    } while (p!=null);
returnnull;
}
//进行红黑树的删除操作finalvoidremoveTreeNode(HashMap<K,V>map, 
Node<K,V>[] tab,booleanmovable){
intn;
//进行判空操作，如果为空，则直接返回if (tab==null|| (n=tab.length) ==0)
return;
//进行取余操作intindex= (n-1) &hash;
TreeNode<K,V>first=(TreeNode<K,V>)tab[index],
root=first, rl;
//下一个元素 pred = prev为前驱TreeNode<K,V>succ= (TreeNode<K,V>)next, 
pred=prev;
//前驱节点为空，则说明为头结点，执行将位//置指向后元素if (pred==null)
tab[index] =first=succ;
//否者，则说明头结点不为空，//则进行前驱节点的下一个节点指向后节点elsepred.next=succ;
//如果后节点不为空，//将后节点的前一个节点指向前节点if (succ!=null)
succ.prev=pred;
//如果first为空，则说明没有元素，直接返回if (first==null)
return;
//root还有父节点，则说明不是根，拿到根if (root.parent!=null)
root=root.root();
if (root==null||root.right==null||      (rl=root.left)==null||rl.left=null){
//红黑树转链表操作tab[index] =first.untreeify(map);
return;
    }
//p为删除节点，pl为左节点，//pr为有节点，replacement为要移动的子节点TreeNode<K,V>p=this,pl=left,
pr=right,replacement;
//左右节点 不为空if (pl!=null&&pr!=null) {
//s为右节点TreeNode<K,V>s=pr, sl;
//s的右节点的左节点不为空while ((sl=s.left) !=null) 
s=sl;
booleanc=s.red; s.red=p.red;p.red=c;
//交换删除节点和右节点的左节点的颜色，//进行变色操作TreeNode<K,V>sr=s.right;
TreeNode<K,V>pp=p.parent;
if (s==pr) {
p.parent=s;
s.right=p;
        }
else {
TreeNode<K,V>sp=s.parent;
if ((p.parent=sp) !=null) {
if (s==sp.left)
sp.left=p;
elsesp.right=p;
            }
if ((s.right=pr) !=null)
pr.parent=s;
        }
p.left=null;
if ((p.right=sr) !=null)
sr.parent=p;
if ((s.left=pl) !=null)
pl.parent=s;
if ((s.parent=pp) ==null)
root=s;
elseif (p==pp.left)
pp.left=s;
elsepp.right=s;
if (sr!=null)
replacement=sr;
elsereplacement=p;
    }
//pl不为空，则删除节点为左节点elseif (pl!=null)
replacement=pl;
//pr不为空，则删除节点为右节点elseif (pr!=null)
replacement=pr;
//删除元素为叶子节点elsereplacement=p;
//如果删除节点后进行//红黑树处理，使用变色和旋转if (replacement!=p) {
TreeNode<K,V>pp=replacement.parent=p.parent;
if (pp==null)
root=replacement;
elseif (p==pp.left)
pp.left=replacement;
elsepp.right=replacement;
p.left=p.right=p.parent=null;
    }
TreeNode<K,V>r=p.red?root:
balanceDeletion(root,replacement);
//删除节点为叶子节点，//则删除与之关联的节点if (replacement==p) {  // detachTreeNode<K,V>pp=p.parent;
p.parent=null;
if (pp!=null) {
if (p==pp.left)
pp.left=null;
elseif (p==pp.right)
pp.right=null;
        }
    }
//根据标识决定是否//将根节点转移hash表首元素if (movable)
moveRootToFront(tab, r);
}

get操作

//通过key获取value的信息publicVget(Objectkey) {
//节点信息，返回节点的值Node<K,V>e;
//获取value值return (e=getNode(hash(key), key)) 
==null?null : e.value;
}
//通过hash值和key，拿到节点//信息，进一步拿到value值finalNode<K,V>getNode(inthash, Objectkey) {
Node<K,V>[] tab;Node<K,V>first,e;intn;Kk;
//哈希表不为空，同时长度//大于0，hash取模不为空时if((tab=table) !=null&& (n=tab.length)>0&&(first=tab[(n-1) &hash]) !=null){
//进行判断首节点的hash、key是否与之相同if (first.hash==hash&&           ((k=first.key) ==key||(key!=null&&key.equals(k))))
returnfirst;
//如果首节点有后继节点，//则说明有链表或者红黑树，此时需要进行判盘//如果为树节点，则进行树节点//信息的获取，否者为链表，遍历链表获取元素if ((e=first.next) !=null) {
if (firstinstanceofTreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash==hash&&              ((k=e.key) ==key||(key!=null&&key.equals(k))))
returne;
            } while ((e=e.next) !=null);
        }
    }
returnnull;
}
finalTreeNode<K,V>getTreeNode(inth, Objectk){
return ((parent!=null) ?root() : 
this).find(h, k, null);
}
//树节点查找finalTreeNode<K,V>find(inth, Objectk, 
Class<?>kc) {
TreeNode<K,V>p=this;
//进行do-while循环找到相要的元素do {
intph, dir; Kpk;
TreeNode<K,V>pl=p.left, pr=p.right, q;
//hash值小于当前节点，则在//左节点进行比较，否者在右节点比较if ((ph=p.hash) >h)
p=pl;
elseif (ph<h)
p=pr;
//否者是当前的节点，直接返回elseif((pk=p.key)==k||(k!=null&&k.equals(pk)))
returnp;
//左节点为空，则遍历右节点elseif (pl==null)
p=pr;
//右节点为空，则遍历左节点elseif (pr==null)
p=pl;
//如果实现了Comparable接口，//则更加compareTo比较出来的大小获取顺序elseif ((kc!=null||         (kc=comparableClassFor(k))!=null) &&         (dir=compareComparables(kc, k, pk))!=0)
p= (dir<0) ?pl : pr;
//如果没有则采用find()放到进行返回elseif((q=pr.find(h, k, kc))!=null)
returnq;
elsep=pl;
    } while (p!=null);
returnnull;
}
//比较器staticClass<?>comparableClassFor(Objectx){
if (xinstanceofComparable) {
Class<?>c; Type[] ts, as; Typet; 
ParameterizedTypep;
if ((c=x.getClass())==String.class)
returnc;
if((ts=c.getGenericInterfaces())!=null){
for(inti=0; i<ts.length; ++i) {
if (((t=ts[i]) instanceofParameterizedType) &&                 ((p= (ParameterizedType)t).getRawType() ==Comparable.class) &&       (as=p.getActualTypeArguments())!=null&&as.length==1&&as[0] ==c)
returnc;
                }
            }
        }
returnnull;
    }
//比较器@SuppressWarnings({"rawtypes","unchecked"})
staticintcompareComparables(Class<?>kc,Objectk, Objectx) {
return (x==null||x.getClass() !=kc?0 :((Comparable)k).compareTo(x));
    }

从里面可以收获到的一些结论：

HashMap的源码较多，且综合了数组、链表、红黑树的操作，因此不管是get还是remove还是get都需要考虑到三张数据结构的操作。同时红黑树是一种平衡二叉树，节点是黑色或者红色的，根节点为黑色的，每个红色节点的两个叶子节点都是黑色的，从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。同时当key相同时，会出现冲突，此时就需要解决hash冲突，此时就将其放入到链表中。而当链表的长度>=8时，数组长度>=64时，则变成红黑树。给定初始化容量时，给定元素个数/加载因子为最佳初始化容量，可以在源码找到这个代码。

HashMap源码学习

一、HashMap相关变量

二、构造函数

三、方法

put方法

扩容操作

remove操作

get操作

热门文章

最新文章

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

HashMap源码学习

一、HashMap相关变量

二、构造函数

三、方法

put方法

扩容操作

remove操作

get操作

热门文章

最新文章

相关电子书