上面HashMap源码解析详解（上）从整体上介绍了HashMap，介绍了数据结构、主要属性字段、获取数组的索引下标、几种构造方法.本文主要介绍添加、查找、扩展元素的主要方法。添加元素put(Kkey,Vvalue)publicVput(Kkey,Vvalue){returnputVal(hash(key),key,value,false,true);}先计算key的哈希码，调用hash方法，获取哈希值。CallputVal()/***@paramhashhashforkeyhashvalue*@paramkeythekeykeyvalue*@paramvaluethevaluetoputvaluevalue*@paramonlyIfAbsentiftrue,don'tchangeexistingvalueonly不exist，以免更改其值*@paramevict如果为false，则该表处于创建模式。*@returnpreviousvalue,ornullifnone返回上一个值，如果不存在returnnull*/finalVputVal(inthash,Kkey,Vvalue,booleanonlyIfAbsent,booleanevict){//声明一个节点数组选项卡，节点节点Node[]选项卡；节点p;诠释n,我;//如果table为null或者tab的长度为0，||双方都需要判断，表为空，或者表的长度为0if((tab=table)==null||(n=tab.length)==0)//表初始化n=(tab=resize()).length;//不存在，直接新建一个Node节点if((p=tab[i=(n-1)&hash])==null)//新建一个节点tab[i]=newNode(hash,key,值,空);else{//存在节点Node;e;Kk;//哈希值与p节点的哈希值一致，(key值的地址)或(key的值)，直接替换if(p.hash==hash&&((k=p.key)==key||(key!=null&&key.equals(k))))e=p;//节点是红黑树elseif(pinstanceofTreeNode)e=((TreeNode)p).putTreeVal(this,tab,hash,key,value);else{//该节点为链表，从前向后遍历for(intbinCount=0;;++binCount){//遍历链表的最后一个节点if((e=p.next)==空）{p.next=newNode（散列，键，值，空）;//链表的个数大于等于8，因为是从0开始的，所以需要减1if(binCount>=TREEIFY_THRESHOLD-1)//-1for1st//变成红色-blacktreetreeifyBin(tab,hash);休息;}//哈希一致或者值一致if(e.hash==hash&&((k=e.key)==key||(key!=null&&key.equals(k))))中断；p=e;}}//e不为空，直接替换赋值if(e!=null){//key的现有映射VoldValue=e.value;if(!onlyIfAbsent||oldValue==null)//原值为空，赋值e.value=value;节点访问后（e）；返回旧值；}}++模数；如果（++大小>阈值）调整大小（）；节点插入后（逐出）；返回空值；}首先判断hash数组表是否为null，如果为null则展开(n-1)&hash对应的下标中是否有结点。如果没有节点，则创建一个新节点并赋值。如果有节点，节点键值是否相等，如果相等则替换值。是否是红黑树，向红黑树添加数据。以上都不匹配，是普通链表，遍历链表，如果链表中存在相同的key则替换，否则在链表尾部添加数据。流程图：putAll(Mapm)putAll是将所有集合元素添加到HashMap中，putAll调用putMapEntries方法，putMapEntries先判断是否需要扩容，然后遍历元素，调用putVal添加元素，下面是添加元素的代码：for(Map.Entrye:m.entrySet()){Kkey=e.getKey();V值=e.getValue();putVal(hash(key),key,value,false,evict);}获取数据get(Objectkey)通过key在哈希表中找到Node节点的值。//返回map映射对应的值publicVget(Objectkey){Nodee;返回（e=getNode（哈希（键），键））==空？null:e.value;}先用hash方法计算hash值，然后调用getNode()获取数据：finalNodegetNode(inthash,Objectkey){Node[]选项卡；节点先，e；诠释n;Kk;//判断tab有数据，对应下标有数据if((tab=table)!=null&&(n=tab.length)>0&&(first=tab[(n-1)&hash])!=null){//hash和key相等（key地址相等或key值相等），找到第一个元素if(first.hash==hash&&//总是检查第一个节点((k=first.key)==key||(key!=null&&key.equals(k))))先返回；//遍历链表if((e=first.next)!=null){//红黑树找到当前key的节点位置if(firstinstanceofTreeNode)return((TreeNode)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;}判断hash数组是否不为null且数组下标(n-1)&hash不为null。如果有所有value，则先查询第一个节点，否则返回null，找到第一个节点并匹配Equalhash和key，返回第一个节点。链表有多个元素，无论是红黑树还是红黑树，如果在红黑树中查找不是红黑树，则遍历普通链表，直到相同的hash和键值匹配。流程图：resize扩容当hash数组为null，或者元素个数超过阈值时，调用resize扩容方法：finalNode[]resize(){//记录原数组Node[]oldTab=table;//原始数组长度intoldCap=(oldTab==null)?0:旧标签长度；//原始阈值（数组长度达到阈值）intoldThr=threshold;//新容量，新阈值intnewCap,newThr=0;if(oldCap>0){//如果数组长度大于等于MAXIMUM_CAPACITY(1>>30)，则不进行扩容。如果(oldCap>=MAXIMUM_CAPACITY){threshold=Integer.MAX_VALUE;返回旧标签；}//扩容后长度小于MAXIMUM_CAPACITY(1>>30)且数组原长度大于16//阈值和新容量都翻倍elseif((newCap=oldCap<<1)=DEFAULT_INITIAL_CAPACITY)newThr=oldThr<<1;//双阈值}//阈值大于零，用新容量替换旧阈值elseif(oldThr>0)//初始容量被放置在阈值中newCap=oldThr;else{//零初始阈值表示使用默认值//oldCap和oldThr都小于等于0，表示调用无参数构造方法，默认容量为16，默认阈值为12。newCap=DEFAULT_INITIAL_CAPACITY；newThr=(int)(DEFAULT_LOAD_FACTOR*DEFAULT_INITIAL_CAPACITY);}if(newThr==0){//新阈值为零，计算阈值floatft=(float)newCap*loadFactor;newThr=(newCap[]newTab=(节点[])新节点[newCap];表=新标签；//原数组不为空，将原数组的元素重新赋值到新数组中//如果是第一次调用resize方法，不需要重新分配数组。if(oldTab!=null){//旧数组遍历for(intj=0;je;//存在下标下的第一个元素if((e=oldTab[j])!=null){oldTab[j]=null;//当前元素后面的元素为空，说明这里只有一个元素，直接用元素的哈希值和新数组的容量取模，得到新下标的位置if(e.next==null)newTab[e.hash&(newCap-1)]=e;//红黑树，分裂红黑树，必要时可能退化为链表elseif(einstanceofTreeNode)((TreeNode)e).split(this,newTab,j,oldCap);//长度大于1的普通链表else{//保留顺序//loHead和loTail分别代表旧位置的头节点和尾节点NodeloHead=null,loTail=null;//hiHead和hiTail分别表示新位置的头节点和尾节点NodehiHead=null,hiTail=null;下一个节点；//遍历链表do{next=e.next;//&运算，都为1，结果为1//元素的hash值与oldCapAND运算为0，原位置不变if((e.hash&oldCap)==0){if(loTail==null)loHead=e;否则loTail.next=e;loTail=e;}//移动到原始位置+oldCapelse{if(hiTail==null)hiHead=e;否则hiTail.next=e;高尾=e;}}while((e=next)!=null);if(loTail!=null){loTail.next=null;newTab[j]=loHead;}如果（hiTail！=null）{hiTail.next=null;newTab[j+oldCap]=hiHead;}}}}}returnnewTab;}原容量是否为空，是否大于最大容量，大于最大容量，小于最大容量不扩容，大于均默认容量16门槛和容量翻倍。如果为空，则原阈值大于零，将阈值分配给新的容量。原始容量和原始阈值均小于等于0，分配默认容量16和默认阈值12。分配完阈值和容量后，遍历数组。如果有值，是否只有一个元素，如果有，则放入新数组n-1&hash下标。如果是红黑树，就分裂红黑树。如果以上两个都不匹配，就是一个普通的链表。遍历链表，如果hash&数组原长度为0，则放在数组原下标处。如果不为零，则放在原位置+原数组长度。Flowchart:Summary本文主要讲解添加、查找、扩展元素的主要方法。其中，添加和查询都需要先获取数组的下标，然后再进行相应的操作。putadd第一次添加数据需要扩充数组。对应的下标是否有值，直接给同一个key赋值，替换value。Key不一致是红黑树，数据加入到红黑树中。要么是红黑树，要么是链表，遍历链表，找到相同的节点key，替换掉。否则，它被添加到链表的末尾。get查询下标是否有值，有值则返回null*如果hash和key相等，则返回节点。是否为多链表。否，返回空值。如果是，是否是红黑树。红黑树，在红黑树中查找，否则就是普通链表，遍历链表直到匹配到相同的hash和key。resize扩容容量大于零且大于最大容量值，不再扩容。在最大容量和默认容量之间，阈值和容量都加倍。初始化时，设置默认容量和默认阈值。遍历原数组节点有值，只有一个值，赋给新数组n-1&hash。如果是红黑树，就分裂红黑树。如果以上都不匹配，则为普通链表，遍历链表。因为数组的长度是2的次方，展开后元素的位置要么在原来的位置，要么在原来的位置移动到2的次方。hash&AND运算中原数组长度为0，存在于原位置。如果不等于0，则存储在下标原位置+原数组长度的位置。
