HashMap详解

　　讲解步骤基础知识工作原理关键代码核心方法基础知识
　　数组结构数组接口，在查询数据方面，具备优势
　　链表结构链表结构，在增删数据方面，具备优势
　　红黑树结构红黑树结构，在查询数据方面，数据量较大的时候，具备一定的优势
　　什么是散列（哈希）表散列表，顾名思义，就是将数据分布在不同的列但是散列表并不是完全将数据分散在不同的列，而是按照某种规则，将具备同样规则的数据存储在同一列。即具备相同规则的数据存储在同一列，规则不同的数据分布在不同的列。这种规则最终的产生与哈希值有关。这里需要注意的事，哈希值只是确定最后存储列的因素，也就是说不同的哈希值可能会存在同一列。
　　什么是哈希值哈希值简单的说，就是hashCode方法产生的值。默认的hashCode方法是由其地址值最终产生一个哈希值。由于HashMap中的元素是否存储是由键来决定，所以如果自定义的类需要存储在键，且想遵循自己的存储规则，需要重写HashCode方法又因为Map集合的键是不能重复的，所以需要重写equals方法，定义去重规则。工作原理存储结构
　　HashMap基于散列法，又称哈希法：数组链表红黑树。HashMap需要同时存储一对键和值。Map集合中提供了put（key，value）方法，所有的键和值会被封装到一个Entry实现类（Node）对象，存储到集合中。在存储的过程中，会先通过hashCode（）方法获取一个哈希值，并通过这个哈希值，与数组的长度进行一定的运算，得到一个索引值（存储的列）在通过equals方法来判断这个元素是否已存在，不存在则存储在该列，若存储，则保留原来的数据。存储在一列的数据，将以链表的形式，前后关联，这样有利于将来进行删除的时候提高效率。但是如果一列的桶结构数据过多，就会导致查询的效率降低。为了优化桶结构带来的问题，HashMap中会去检查，当一列的桶结构数据达到8个以上，就降这一列树化（转变为树结构）名词理解所有的数据都是以Node节点为单位。hash值：哈希值，该方法内部提供了一个扰动函数inthashCode（）扰动函数：用于产生哈希值，前16位与后16位做异或运算，提高低位随机性。hkey。hashCode（））（h16）路由寻址：由数组长度与哈希值产进行与操作，产生最终的存储列（索引位置）：（table。length1）node。hashHash碰撞：哈希值如果相同，就会存储到相同的列。链化：哈希值相同，就会存储在同系列，产生桶状结构，桶结构过长，查询数据低效。红黑树：jdk8引入，类似于二叉树，可以避免过长的桶状结构扩容原理扩容：增加数组长度。目的在于解决数据过多，链化严重，默认以两倍的长度扩容。一列添加第8个元素，且数组长度小于64，会优先扩容。一列添加第8个元素，且数组长度达到64个，会优先树化。添加元素后，若哈希表中元素总个数超过阈值（一个指定的值），会进行扩容。扩容后，会重新根据数组长度和哈希值计算存储位置。关键代码核心字段staticfinalintDEFAULTINITIALCAPACITY14；默认数组大小staticfinalintMAXIMUMCAPACITY130；数组最大长度staticfinalfloatDEFAULTLOADFACTOR0。75f；默认负载因子staticfinalintTREEIFYTHRESHOLD8；树化阈值staticfinalintUNTREEIFYTHRESHOLD6；树降级阈值staticfinalintMINTREEIFYCAPACITY64；树化阈值transientNodeK，V〔〕table；哈希表transientSetMap。EntryK，VentrySet；键值对对象集合transientintsize；元素长度transientintmodCount；增删元素次数intthreshold；扩容阈值扩容阈值loadFactorcapacityfinalfloatloadFactor；负载因子核心方法
　　putputVal（存储数据）finalVputVal（inthash，Kkey，Vvalue，booleanonlyIfAbsent，booleanevict）｛NodeK，V〔〕tab；NodeK，Vp；intn，i；判断表是否为空或长度为0，若满足条件，则初始化表（体现了延迟加载）if（（tabtable）null（ntab。length）0）n（tabresize（））。length；判断要添加的元素对应的列是否为空，若满足条件，则直接插入if（（ptab〔i（n1）hash〕）null）tab〔i〕newNode（hash，key，value，null）；else｛NodeK，Ve；Kk；判断元素的哈希值与要存储列的键相同，则替换键对应的值if（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）｛遍历当前列的节点，判断如果当前节点超过8个节点，则将当前列转为树结构。if（（ep。next）null）｛p。nextnewNode（hash，key，value，null）；if（binCountTREEIFYTHRESHOLD1）1for1sttreeifyBin（tab，hash）；break；｝if（e。hashhash（（ke。key）key（key！nullkey。equals（k））））break；pe；｝｝存在相同键，就值替换新值if（e！null）｛existingmappingforkeyVoldValuee。value；if（！onlyIfAbsentoldValuenull）e。valuevalue；afterNodeAccess（e）；returnoldValue；｝｝记录操作次数modCount；判断元素个数达到指定的阈值，则进行扩容操作。if（sizethreshold）resize（）；afterNodeInsertion（evict）；returnnull；｝
　　resize（扩容）finalNodeK，V〔〕resize（）｛NodeK，V〔〕oldTabtable；intoldCap（oldTabnull）？0：oldTab。length；intoldThrthreshold；intnewCap，newThr0；if（oldCap0）｛if（oldCapMAXIMUMCAPACITY）｛thresholdInteger。MAXVALUE；returnoldTab；｝elseif（（newCapoldCap1）MAXIMUMCAPACITYoldCapDEFAULTINITIALCAPACITY）修改新表的长度为旧表的两倍newThroldThr1；doublethreshold｝elseif（oldThr0）initialcapacitywasplacedinthresholdnewCapoldThr；else｛zeroinitialthresholdsignifiesusingdefaultsnewCapDEFAULTINITIALCAPACITY；newThr（int）（DEFAULTLOADFACTORDEFAULTINITIALCAPACITY）；｝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；将新表内容，重新计算位置后，放入新表if（oldTab！null）｛for（intj0；joldCap；j）｛NodeK，Ve；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｛preserveorderNodeK，VloHeadnull，loTailnull；NodeK，VhiHeadnull，hiTailnull；NodeK，Vnext；do｛nexte。next；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；｝
　　tableSizeFor（数组长度初始化）二进制位运算右移：二进制数据向右移动一位，最高位补原最高位值，原最低位舍弃。41结果等于221结果等于1无符号右移：二进制数据向右移动一位，最高位补0，原最低位舍弃。41结果等于221结果等于1无符号右移动，会确保移动后一定是一个正数。左移：二进制数据向左移动一位，最低位补0，原最高位舍弃。举例：41结果等于881结果等于16或：有1则11001100结果为1100（12）staticfinalinttableSizeFor（intcap）｛下列操作的最终目的保证了，最终的n值一定比cap大，且最接近满足1后数组长度定义的数值（0，3，7，15，31，63。。。）1001100intncap1；nn1；nn2；nn4；nn8；nn16；return（n0）？1：（nMAXIMUMCAPACITY）？MAXIMUMCAPACITY：n1；｝