java集合HashMap源码解析（基于JDK1。8）

　　一、Hashmap简介
　　类继承关系图如下：
　　HashMap实现了三个接口，一个抽象类。主要的方法都在Map接口中，AbstractMap抽象类实现了Map方法中的公共方法，例如：size（），containsKey（），clear（）等，主要方法由子类自己实现。
　　HashMap结构如下图：
　　HashMap的主要结构由数组、链表红黑树组成，当数组中某个节点大于等于8个并且数组长度大于等于64时，链表会转换为红黑树。二、HashMap的主要属性publicclassHashMapK，VextendsAbstractMapK，VimplementsMapK，V，Cloneable，Serializable｛privatestaticfinallongserialVersionUID362498820763181265L；默认值默认初始化大小，必须是二的次幂staticfinalintDEFAULTINITIALCAPACITY14；aka16数组最大值，当大于该值时使用该值staticfinalintMAXIMUMCAPACITY130；默认负载因子staticfinalfloatDEFAULTLOADFACTOR0。75f；某个节点由链表转为红黑树时候的阈值staticfinalintTREEIFYTHRESHOLD8；节点由红黑树转为链表时的阈值staticfinalintUNTREEIFYTHRESHOLD6；节点转为红黑树时数组的阈值staticfinalintMINTREEIFYCAPACITY64；字段HashMap的数组（划重点，主要结构）HashMap的由数组链表红黑树组成，数组指的就是这个数组，链表和红黑树则是由Node结构组成transientNodeK，V〔〕table；保存缓存的set。AbstractMap字段用于实现keySet（）和values（）。transientSetMap。EntryK，VentrySet；HashMap中数据量大小。transientintsize；HashMap的修改次数transientintmodCount；阈值，当HashMap中数据大于该值时将进行扩容intthreshold；加载因子finalfloatloadFactor；Node结构HashMap的基础节点staticclassNodeK，VimplementsMap。EntryK，V｛当前节点的hash值finalinthash；当前节点的keyfinalKkey；当前节点的valueVvalue；指向下一个节点的引用NodeK，Vnext；node的构造函数Node（inthash，Kkey，Vvalue，NodeK，Vnext）｛this。hashhash；this。keykey；this。valuevalue；this。nextnext；｝。。。其他方法省略｝复制代码三、源码解析1、初始化方法
　　HashMap共有四个构造函数，参数分别是1、初始化数组大小、加载因子。2、初始化数组大小。3、无参。4、HashMap结构。
　　其中1、2、3三个参数的构造函数性质相同，都是传入初始化数组大小或加载因子，没传的使用默认值。构造函数4使用默认的初始化大小和加载因子，并且是将传入的HashMap添加到新的结构中。
　　具体代码如下：有初始化大小和加载因子大小的构造函数paraminitialCapacity初始化大小paramloadFactor加载因子throwsIllegalArgumentException非法参数异常publicHashMap（intinitialCapacity，floatloadFactor）｛如果初始化大小小于0，抛出异常if（initialCapacity0）thrownewIllegalArgumentException（Illegalinitialcapacity：initialCapacity）；如果初始化大小大于最大值，那么就把初始化大小设置为最大值if（initialCapacityMAXIMUMCAPACITY）initialCapacityMAXIMUMCAPACITY；如果加载因子小于等于0或者是非法的float类型，则抛出异常if（loadFactor0Float。isNaN（loadFactor））thrownewIllegalArgumentException（Illegalloadfactor：loadFactor）；设置加载因子this。loadFactorloadFactor；设置下一次扩容阈值this。thresholdtableSizeFor（initialCapacity）；｝有初始化大小的构造函数加载因子使用默认值（0。75）param初始化大小throwsIllegalArgumentException非法参数异常publicHashMap（intinitialCapacity）｛调用第一个构造函数，加载因子使用默认值DEFAULTLOADFACTOR（0。75）this（initialCapacity，DEFAULTLOADFACTOR）；｝无参构造函数，使用默认大小（16）和默认加载因子（0。75）publicHashMap（）｛设计加载因子为默认值，其他所有值都是要默认值this。loadFactorDEFAULTLOADFACTOR；allotherfieldsdefaulted｝使用一个HashMap为参数的构造函数，加载因子使用默认（0。75）param一个HashMap数据throwsNullPointerException空指针异常publicHashMap（Maplt；？extendsK，？extendsVm）｛加载因子为默认值this。loadFactorDEFAULTLOADFACTOR；将传入的HashMap数据放入当前结构中putMapEntries（m，false）；｝复制代码2、get方法
　　先看源码，再做总结，源码：HashMap的get方法param要查找的keypublicVget（Objectkey）｛定义一个nodeNodeK，Ve；通过getNode（）方法获取node，getNode返回null则get方法返回null，否则返回node的valuereturn（egetNode（hash（key），key））null？null：e。value；｝实现Map。get和相关方法paramkey的hash值paramkeyreturn结构中的node或者nullfinalNodeK，VgetNode（inthash，Objectkey）｛定义说明tab：数组，first：该数组节点中的第一个值，n：数组大小，k：first的keyNodeK，V〔〕tab；NodeK，Vfirst，e；intn；Kk；如果数组不为null、数组大小大于0、通过hash获取到的数组中的节点不为nullif（（tabtable）！null（ntab。length）0（firsttab〔（n1）hash〕）！null）｛该节点的hash等于要查找的hash值（始终检查第一个节点）、该节点的key与要查找的key相等（为true或者equals为true）if（first。hashhashalwayscheckfirstnode（（kfirst。key）key（key！nullkey。equals（k））））returnfirst；如果第first节点不为null并且first节点不是要查找的节点（上面的if判断，如果是要查找的接口则上一步就返回了）if（（efirst。next）！null）｛如果是红黑树类型if（firstinstanceofTreeNode）遍历红黑树return（（TreeNodeK，V）first）。getTreeNode（hash，key）；循环遍历链表do｛当hash值相同、该节点的key与要查找的key相等（为true或者equals为true）if（e。hashhash（（ke。key）key（key！nullkey。equals（k））））returne；｝while（（ee。next）！null）；｝｝如果hash值对应的数组为null，则返回nullreturnnull；｝复制代码
　　get方法总结：根据key的hash值找到数组中对应的位置。判断该位置上的值和要查找的值是否相等（或者equals），如果是则返回如果不是则判断该节点的下一个节点是否为空，为空则返回null。判断结构是否是红黑树，如果是，遍历树。如果不是树，则遍历链表。如果不符合上面的条件则返回null。3、put方法
　　先看源码：添加keyvalue，如果key已经对应value，则替换，返回之前的值paramkeyparamvaluereturn返回之前的valuepublicVput（Kkey，Vvalue）｛returnputVal（hash（key），key，value，false，true）；｝实现Map。put和相关方法paramhash值paramkeyparamvalueparamonlyIfAbsent是否只在不存在的时候修改值，true不修改，false修改paramevict如果为false，则为创建模式return返回之前的value，如果没有则为nullfinalVputVal（inthash，Kkey，Vvalue，booleanonlyIfAbsent，booleanevict）｛变量说明tab：当前数组，p：当前节点，n：数组大小，i：要插入的数据在数组中的位置NodeK，V〔〕tab；NodeK，Vp；intn，i；数组为空或者数组大小为0初始化数组（resize（）扩容函数，也包括初始化数组，后面扩容会分析）if（（tabtable）null（ntab。length）0）n（tabresize（））。length；如果对应数组中的位置为null，将当前数据构造成Node放入该节点if（（ptab〔i（n1）hash〕）null）tab〔i〕newNode（hash，key，value，null）；else｛NodeK，Ve；Kk；当hash值相同、该节点的key与要插入的key相等（为true或者equals为true），则替换该valueif（p。hashhash（（kp。key）key（key！nullkey。equals（k））））ep；如果是树结构，插入树节点elseif（pinstanceofTreeNode）e（（TreeNodeK，V）p）。putTreeVal（this，tab，hash，key，value）；else｛遍历链表节点for（intbinCount0；；binCount）｛如果没有遍历到与该key相同的数据，则在链表最后添加该数据节点if（（ep。next）null）｛p。nextnewNode（hash，key，value，null）；如果该链表长度大于等于8，则将链表转换为树if（binCountTREEIFYTHRESHOLD1）1for1sttreeifyBin（tab，hash）；break；｝如果key相同，则跳出循环if（e。hashhash（（ke。key）key（key！nullkey。equals（k））））break；pe；｝｝如果存在key对应的数据，替换数据，返回之前的数据if（e！null）｛existingmappingforkeyVoldValuee。value；if（！onlyIfAbsentoldValuenull）e。valuevalue；LinkedHashMap使用，HashMap中方法体为空afterNodeAccess（e）；returnoldValue；｝｝modCount；如果数组中的值大于阈值，则扩容if（sizethreshold）resize（）；afterNodeInsertion（evict）；returnnull；｝复制代码
　　put方法总结：判断HashMap中的数组是否为空或者大小为0，如果是则初始化数组。如果该hash值对应的数组中的位置为空，则将该数据组成的节点直接插入到该位置中。如果数组对应位置数据不为空，判断该位置节点的key与要插入的key是否相等，如果是设置e（局部变量）等于该节点。如果Node结构为树结构，则遍历树结构找到key对应的节点，设置为e。如果Node结构为链表，遍历链表，如果链表中没有找到对应的key，将数据构造成Node节点插入链表最后，如果链表长度大于等于8，则将结构转为树。如果在链表中找到对应的key，则将该节点设置为e。如果e（上面遍历找到的节点）不为null，则设置新的value，返回旧的value。如果e为null，说明是新增，HashMap大小加一，判断是否大于阈值，如果大于，则扩容。4、扩容
　　先看源码：初始化或者扩容returnthetablefinalNodeK，V〔〕resize（）｛旧的数组NodeK，V〔〕oldTabtable；旧的数组大小intoldCap（oldTabnull）？0：oldTab。length；旧的阈值intoldThrthreshold；新的数组大小和阈值intnewCap，newThr0；如果旧的数组大小大于0（只要初始化过就都会大于0）if（oldCap0）｛旧的数组大小已经达到最大，那么设置阈值为最大值if（oldCapMAXIMUMCAPACITY）｛thresholdInteger。MAXVALUE；returnoldTab；｝如果旧的数组扩大两倍小鱼最大值并且旧的数组大于等于初始化值，那么设置新的阈值为旧的阈值的两倍elseif（（newCapoldCap1）MAXIMUMCAPACITYoldCapDEFAULTINITIALCAPACITY）newThroldThr1；doublethreshold｝如果数组大小为0，阈值大小大于0，则设置新的初始化大小为阈值，否则全部使用默认值elseif（oldThr0）初始容量设置为阈值newCapoldThr；else｛zeroinitialthresholdsignifiesusingdefaultsnewCapDEFAULTINITIALCAPACITY；newThr（int）（DEFAULTLOADFACTORDEFAULTINITIALCAPACITY）；｝如果新的阈值等于0，那么设置新的阈值为新的数组大小加载因子if（newThr0）｛floatft（float）newCaploadFactor；newThr（newCapMAXIMUMCAPACITYft（float）MAXIMUMCAPACITY？（int）ft：Integer。MAXVALUE）；｝阈值等于新的阈值thresholdnewThr；新的数组SuppressWarnings（｛rawtypes，unchecked｝）NodeK，V〔〕newTab（NodeK，V〔〕）newNode〔newCap〕；tablenewTab；旧的数组不为null，说明不是初始化，需要扩容if（oldTab！null）｛遍历旧得数组for（intj0；joldCap；j）｛NodeK，Ve；如果该位置的节点不为null，那么遍历链表或者树放入新的数组中if（（eoldTab〔j〕）！null）｛oldTab〔j〕null；如果只有一个节点，直接放入新数组中对应的位置if（e。nextnull）newTab〔e。hash（newCap1）〕e；如果是树结构，拆分树elseif（einstanceofTreeNode）（（TreeNodeK，V）e）。split（this，newTab，j，oldCap）；链表结构，拆分链表else｛保持之前的顺序低位头、尾节点NodeK，VloHeadnull，loTailnull；高位头、尾节点NodeK，VhiHeadnull，hiTailnull；NodeK，Vnext；do｛nexte。next；如果hash值旧的数组大小为0，说明放到新数组后还是之前的位置，否则为（当前位置旧数组大小）的位置遍历第一个节点时，头、尾都设置为该节点，之后的节点添加到该节点之后，并设置尾节点为后添加的节点if（（e。hasholdCap）0）｛if（loTailnull）loHeade；elseloTail。nexte；loTaile；｝else｛if（hiTailnull）hiHeade；elsehiTail。nexte；hiTaile；｝｝while（（enext）！null）；设置新数组的节点if（loTail！null）｛loTail。nextnull；newTab〔j〕loHead；｝if（hiTail！null）｛hiTail。nextnull；newTab〔joldCap〕hiHead；｝｝｝｝｝returnnewTab；｝复制代码
　　扩容方法总结：数组是否已经达到最大值，如果已经最大，设置阈值也为最大值，否则数组大小和阈值都改为之前的两倍。数组是否已经初始化，如果没有则初始化数组和阈值。旧数组不为null，遍历旧数组，将对应位置的链表树分为成两个链表数组，一个在原先的位置上，一个在原先的位置原先数组大小的位置上，将两个链表树放入新数组的对应位置。