HashMap底层实现原理

　　HashMap采用NodeK，V数组来存储keyvalue对，每一个键值对组成了一个Node实体，Node类实际上是一个单向的链表结构，它具有Next指针，可以连接下一个Node实体。HashMap在JDK1。8之前和之后的区别
　　JDK1。8之前，数组链表存储结构
　　缺点就是哈希函数很难使元素百分百的均匀分布，这会产生一种极端的可能，就是大量的元素存在一个桶里
　　JDK1。8之后：数组链表红黑树添加元素时：链表长度大于8的时候，转换为红黑树删除元素、扩容时，同上，数量大于8时，也是采用红黑树形式存储，但是在数量较少时，即数量小于6时，会将红黑树转换回链表遍历、查找时，使用红黑树，他的时间复杂度O（logn），便于性能的提高。数据结构
　　存储结构
　　staticclassNodeK，VimplementsMap。EntryK，V｛finalinthash；finalKkey；Vvalue；NodeK，Vnext；Node（inthash，Kkey，Vvalue，NodeK，Vnext）｛this。hashhash；this。keykey；this。valuevalue；this。nextnext；｝publicfinalKgetKey（）｛returnkey；｝publicfinalVgetValue（）｛returnvalue；｝publicfinalStringtoString（）｛returnkeyvalue；｝publicfinalinthashCode（）｛returnObjects。hashCode（key）Objects。hashCode（value）；｝publicfinalVsetValue（VnewValue）｛VoldValuevalue；valuenewValue；returnoldValue；｝publicfinalbooleanequals（Objecto）｛if（othis）returntrue；if（oinstanceofMap。Entry）｛Map。Entrylt；？，？e（Map。Entrylt；？，？）o；if（Objects。equals（key，e。getKey（））Objects。equals（value，e。getValue（）））returntrue；｝returnfalse；｝｝
　　NodeK，V数组transientNodeK，V〔〕table；加载因子finalfloatloadFactor；默认加载因子，容量达到这个比例时自动扩容staticfinalfloatDEFAULTLOADFACTOR0。75f；数量大于8时，链表转换为红黑树形式存储staticfinalintTREEIFYTHRESHOLD8；即数量小于6时，会将红黑树转换回链表，删除元素时removestaticfinalintUNTREEIFYTHRESHOLD6；PUT时每次都做hashpublicVput（Kkey，Vvalue）｛returnputVal（hash（key），key，value，false，true）；｝put函数核心算法finalVputVal（inthash，Kkey，Vvalue，booleanonlyIfAbsent，booleanevict）｛NodeK，V〔〕tab；NodeK，Vp；intn，i；if（（tabtable）null（ntab。length）0）n（tabresize（））。length；if（（ptab〔i（n1）hash〕）null）这里的n表示数组的长度。hashtab〔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）｛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；modCount是java集合中FailFast的底层实现原理if（sizethreshold）扩容resize（）；afterNodeInsertion（evict）；空实现returnnull；｝CallbackstoallowLinkedHashMappostactionsvoidafterNodeAccess（NodeK，Vp）｛｝voidafterNodeInsertion（booleanevict）｛｝voidafterNodeRemoval（NodeK，Vp）｛｝思考
　　java集合中的快速失败：modCount
　　快速失败是Java集合的一种错误检测机制，当多个线程对集合进行结构上的改变的操作时，有可能会产生failfast。
　　举个例子：假设存在两个线程（线程1、线程2），线程1通过Iterator在遍历集合A中的元素，在某个时候线程2修改了集合A的结构（是结构上面的修改，而不是简单的修改集合元素的内容），那么这个时候程序就可能会抛出ConcurrentModificationException异常，从而产生fastfail快速失败。
　　HashMap中遍历算法如下：finalclassKeySetextendsAbstractSetK｛publicfinalintsize（）｛returnsize；｝publicfinalvoidclear（）｛HashMap。this。clear（）；｝publicfinalIteratorKiterator（）｛returnnewKeyIterator（）；｝publicfinalbooleancontains（Objecto）｛returncontainsKey（o）；｝publicfinalbooleanremove（Objectkey）｛returnremoveNode（hash（key），key，null，false，true）！null；｝publicfinalSpliteratorKspliterator（）｛returnnewKeySpliterator（HashMap。this，0，1，0，0）；｝publicfinalvoidforEach（Consumerlt；？superKaction）｛NodeK，V〔〕tab；if（actionnull）thrownewNullPointerException（）；if（size0（tabtable）！null）｛intmcmodCount；for（inti0；itab。length；i）｛for（NodeK，Vetab〔i〕；e！null；ee。next）action。accept（e。key）；｝if（modCount！mc）抛出异常，FailFastthrownewConcurrentModificationException（）；｝｝｝优化hash算法
　　JDK1。8中，是通过hashCode（）的高16位异或低16位实现的：（hk。hashCode（））（h16），主要是从速度，功效和质量来考虑的，减少系统的开销，也不会造成因为高位没有参与下标的计算，从而引起的碰撞。扰动函数：促使元素位置分布均匀，减少碰撞几率staticfinalinthash（Objectkey）｛inth；如果keynull返回的值是0如果key！null首先计算key的hashcode值赋值给h，然后与h无符号右移16位后的二进制按位异或预算得到最后hash值return（keynull）？0：（hkey。hashCode（））（h16）；｝hash具体实现过程如下图所示：
　　hash计算过程与putval函数的应用key。hashCode（）；返回散列值也就是hashcode，假设随便生成的一个值。n表示数组初始化的长度是16。（按位与运算）：运算规则：相同的二进制数位上，都是1的时候，结果为1，否则为零。（按位异或运算）：运算规则：相同的二进制数位上，数字相同，结果为0，不同为1。
　　高16bit不变，低16bit和高16bit做了一个异或（得到的hashCode转化为32位二进制，前16位和后16位低16bit和高16bit做了一个异或）为什么这样实现呢？
　　如果当n即数组长度很小，假设是16的话，那么n1即为1111，这样的值和hashCode直接做按位与操作，实际上只使用了哈希值的后4位。如果当哈希值的高位变化很大，低位变化很小，这样就很容易造成哈希冲突了，所以这里把高低位都利用起来，从而解决了这个问题。降低了Hash冲突的概率为什么要用异或运算符
　　保证了对象的hashCode的32位值只要有一位发生改变，整个hash（）返回值就会改变。尽可能的减少碰撞。
　　工作原理
　　存储对象时，将KV键值传给put（）方法：调用hash（K）方法计算K的hash值，然后结合数组长度，计算得数组下标；调整数组大小（当容器中的元素个数大于capacityloadfactor时，容器会进行扩容resize为2n）；hash碰撞
　　i。如果K的hash值在HashMap中不存在，则执行插入，若存在，则发生碰撞；
　　ii。如果K的hash值在HashMap中存在，且它们两者equals返回true，则更新键值对；
　　iii。如果K的hash值在HashMap中存在，且它们两者equals返回false，则插入链表的尾部（尾插法）或者红黑树中（树的添加方式）。（JDK1。7之前使用头插法、JDK1。8使用尾插法）
　　get实现publicVget（Objectkey）｛NodeK，Ve；return（egetNode（hash（key），key））null？null：e。value；｝ImplementsMap。getandrelatedmethodsparamhashhashforkeyparamkeythekeyreturnthenode，ornullifnonefinalNodeK，VgetNode（inthash，Objectkey）｛NodeK，V〔〕tab；NodeK，Vfirst，e；intn；Kk；if（（tabtable）！null（ntab。length）0（firsttab〔（n1）hash〕）！null）｛if（first。hashhashalwayscheckfirstnode（（kfirst。key）key（key！nullkey。equals（k））））returnfirst；if（（efirst。next）！null）｛if（firstinstanceofTreeNode）return（（TreeNodeK，V）first）。getTreeNode（hash，key）；do｛if（e。hashhash（（ke。key）key（key！nullkey。equals（k））））returne；｝while（（ee。next）！null）；｝｝returnnull；｝
　　问题思考？
　　Q：默认初始化大小是多少？为啥是这么多？为啥大小都是2的幂？
　　A：hash运算的过程其实就是对目标元素的Key进行hashcode，再对Map的容量进行取模，而JDK的工程师为了提升取模的效率，使用位运算代替了取模运算，这就要求Map的容量一定得是2的幂。HashMap的容量为什么是2的n次幂，和这个putval方法中（n1）hash的计算方法有着千丝万缕的关系，符号是按位与的计算，这是位运算，计算机能直接运算，特别高效，按位与的计算方法是，只有当对应位置的数据都为1时，运算结果也为1，当HashMap的容量是2的n次幂时，（n1）的2进制也就是1111111111这样形式的，这样与添加元素的hash值进行位运算时，能够（充分的散列），使得添加的元素均匀分布在HashMap的每个位置上，减少hash碰撞。
　　Q：HashMap如何有效减少碰撞？
　　A：扰动函数：促使元素位置分布均匀，减少碰撞几率、使用final对象，并采用合适的equals（）和hashCode（）方法