HashMap的实现原理详解（看这篇就够了）

　　一线资深java工程师明确了需要精通集合容器，尤其是今天我谈到的HashMap。
　　HashMap在Java集合的重要性不亚于Volatile在并发编程的重要性（可见性与有序性）。
　　我会重点讲解以下9点：1。HashMap的数据结构
　　2。HashMap核心成员
　　3。HashMapd的Node数组
　　4。HashMap的数据存储
　　5。HashMap的哈希函数
　　6。哈希冲突：链式哈希表
　　7。HashMap的get方法：哈希函数
　　8。HashMap的put方法
　　9。为什么槽位数必须使用2n？HashMap的数据结构
　　首先我们从数据结构的角度来看：HashMap是：数组链表红黑树（JDK1。8增加了红黑树部分）的数据结构，如下所示：
　　这里需要搞明白两个问题：数据底层具体存储的是什么？这样的存储方式有什么优点呢？1。核心成员默认初始容量（数组默认大小）：16，2的整数次方staticfinalintDEFAULTINITIALCAPACITY14；最大容量staticfinalintMAXIMUMCAPACITY130；默认负载因子staticfinalfloatDEFAULTLOADFACTOR0。75f；装载因子用来衡量HashMap满的程度，表示当map集合中存储的数据达到当前数组大小的75则需要进行扩容链表转红黑树边界staticfinalintTREEIFYTHRESHOLD8；红黑树转离链表边界staticfinalintUNTREEIFYTHRESHOLD6；哈希桶数组transientNodeK，V〔〕table；实际存储的元素个数transientintsize；当map里面的数据大于这个threshold就会进行扩容intthreshold阈值table。lengthloadFactor2。Node数组
　　从源码可知，HashMap类中有一个非常重要的字段，就是Node〔〕table，即哈希桶数组，明显它是一个Node的数组。staticclassNodeK，VimplementsMap。EntryK，V｛finalinthash；用来定位数组索引位置finalKkey；Vvalue；NodeK，Vnext；链表的下一个Node节点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；｝｝
　　Node是HashMap的一个内部类，实现了Map。Entry接口，本质是就是一个映射（键值对）。HashMap的数据存储1。哈希表来存储
　　HashMap采用哈希表来存储数据。
　　哈希表（Hashtable，也叫散列表），是根据关键码值（Keyvalue）而直接进行访问的数据结构，只要输入待查找的值即key，即可查找到其对应的值。
　　哈希表其实就是数组的一种扩展，由数组演化而来。可以说，如果没有数组，就没有散列表。2。哈希函数
　　哈希表中元素是由哈希函数确定的，将数据元素的关键字Key作为自变量，通过一定的函数关系（称为哈希函数），计算出的值，即为该元素的存储地址。
　　表示为：AddrH（key），如下图所示：
　　哈希表中哈希函数的设计是相当重要的，这也是建哈希表过程中的关键问题之一。3。核心问题
　　建立一个哈希表之前需要解决两个主要问题：
　　1）构造一个合适的哈希函数，均匀性H（key）的值均匀分布在哈希表中
　　2）冲突的处理
　　冲突：在哈希表中，不同的关键字值对应到同一个存储位置的现象。4。哈希冲突：链式哈希表
　　哈希表为解决冲突，可以采用地址法和链地址法等来解决问题，Java中HashMap采用了链地址法。
　　链地址法，简单来说，就是数组加链表的结合，如下图所示：
　　HashMap的哈希函数重新计算哈希值staticfinalinthash（Objectkey）｛inth；hkey。hashCode（）为第一步取hashCode值h（h16）为第二步高位参与运算return（keynull）？0：（hkey。hashCode（））（h16）；｝
　　计算数组槽位（n1）hash
　　对key进行了hashCode运算，得到一个32位的int值h，然后用h异或h16位。在JDK1。8的实现中，优化了高位运算的算法，通过hashCode（）的高16位异或低16位实现的：（hk。hashCode（））（h16）。
　　这样做的好处是，可以将hashcode高位和低位的值进行混合做异或运算，而且混合后，低位的信息中加入了高位的信息，这样高位的信息被变相的保留了下来。
　　等于说计算下标时把hash的高16位也参与进来了，掺杂的元素多了，那么生成的hash值的随机性会增大，减少了hash碰撞。
　　备注：异或：不同为1，相同为0：无符号右移：右边补0运算：两位同时为1，结果才为1，否则为0
　　h（table。length1）来得到该对象的保存位，而HashMap底层数组的长度总是2的n次方。为什么槽位数必须使用2n？1。为了让哈希后的结果更加均匀
　　假如槽位数不是16，而是17，则槽位计算公式变成：（171）hash
　　从上文可以看出，计算结果将会大大趋同，hashcode参加运算后被更多位的0屏蔽，计算结果只剩下两种0和16，这对于hashmap来说是一种灾难。2。等价于length取模
　　当length总是2的n次方时，h（length1）运算等价于对length取模，也就是hlength，但是比具有更高的效率。
　　位运算的运算效率高于算术运算，原因是算术运算还是会被转化为位运算。
　　最终目的还是为了让哈希后的结果更均匀的分布，减少哈希碰撞，提升hashmap的运行效率。分析HashMap的put方法：finalVputVal（inthash，Kkey，Vvalue，booleanonlyIfAbsent，booleanevict）｛NodeK，V〔〕tab；NodeK，Vp；intn，i；当前对象的数组是null或者数组长度时0时，则需要初始化数组if（（tabtable）null（ntab。length）0）｛n（tabresize（））。length；｝使用hash与数组长度减一的值进行异或得到分散的数组下标，预示着按照计算现在的key会存放到这个位置上，如果这个位置上没有值，那么直接新建kv节点存放其中长度n是一个2的幂次数if（（ptab〔i（n1）hash〕）null）｛tab〔i〕newNode（hash，key，value，null）；｝如果走到else这一步，说明key索引到的数组位置上已经存在内容，即出现了碰撞这个时候需要更为复杂处理碰撞的方式来处理，如链表和树else｛NodeK，Ve；Kk；节点key存在，直接覆盖valueif（p。hashhash（（kp。key）key（key！nullkey。equals（k））））｛ep；｝判断该链为红黑树elseif（pinstanceofTreeNode）｛其中this表示当前HashMap，tab为map中的数组e（（TreeNodeK，V）p）。putTreeVal（this，tab，hash，key，value）；｝else｛判断该链为链表for（intbinCount0；；binCount）｛如果当前碰撞到的节点没有后续节点，则直接新建节点并追加if（（ep。next）null）｛p。nextnewNode（hash，key，value，null）；TREEIFYTHRESHOLD8从0开始的，如果到了7则说明满8了，这个时候就需要转重新确定是否是扩容还是转用红黑树了if（binCountTREEIFYTHRESHOLD1）1for1sttreeifyBin（tab，hash）；break；｝找到了碰撞节点中，key完全相等的节点，则用新节点替换老节点if（e。hashhash（（ke。key）key（key！nullkey。equals（k））））break；pe；｝｝此时的e是保存的被碰撞的那个节点，即老节点if（e！null）｛existingmappingforkeyVoldValuee。value；onlyIfAbsent是方法的调用参数，表示是否替换已存在的值，在默认的put方法中这个值是false，所以这里会用新值替换旧值if（！onlyIfAbsentoldValuenull）e。valuevalue；CallbackstoallowLinkedHashMappostactionsafterNodeAccess（e）；returnoldValue；｝｝map变更性操作计数器比如map结构化的变更像内容增减或者rehash，这将直接导致外部map的并发迭代引起failfast问题，该值就是比较的基础modCount；size即map中包括kv数量的多少超过最大容量就扩容if（sizethreshold）resize（）；CallbackstoallowLinkedHashMappostactionsafterNodeInsertion（evict）；returnnull；｝
　　HashMap的put方法执行过程整体如下：
　　。判断键值对数组table〔i〕是否为空或为null，否则执行resize（）进行扩容；
　　。根据键值key计算hash值得到插入的数组索引i，如果table〔i〕null，直接新建节点添加
　　。判断table〔i〕的首个元素是否和key一样，如果相同直接覆盖value
　　。判断table〔i〕是否为treeNode，即table〔i〕是否是红黑树，如果是红黑树，则直接在树中插入键值对
　　。遍历table〔i〕，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；
　　。插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容。HashMap总结
　　HashMap底层结构？基于Map接口的实现，数组链表的结构，JDK1。8后加入了红黑树，链表长度8变红黑树，6变链表
　　两个对象的hashcode相同会发生什么？Hash冲突，HashMap通过链表来解决hash冲突
　　HashMap中equals（）和hashCode（）有什么作用？HashMap的添加、获取时需要通过key的hashCode（）进行hash（），然后计算下标（n1hash），从而获得要找的同的位置。当发生冲突（碰撞）时，利用key。equals（）方法去链表或树中去查找对应的节点
　　HashMap何时扩容？put的元素达到容量乘负载因子的时候，默认160。75
　　hash的实现吗？hkey。hashCode（））（h16），hashCode进行无符号右移16位，然后进行按位异或，得到这个键的哈希值，由于哈希表的容量都是2的N次方，在当前，元素的hashCode（）在很多时候下低位是相同的，这将导致冲突（碰撞），因此1。8以后做了个移位操作：将元素的hashCode（）和自己右移16位后的结果求异或
　　HashMap线程安全吗？HashMap读写效率较高，但是因为其是非同步的，即读写等操作都是没有锁保护的，所以在多线程场景下是不安全的，容易出现数据不一致的问题，在单线程场景下非常推荐使用。
　　以上就是HashMap的介绍，希望对你有所收获！
　　如果不满足于文章详解，私信【架构】获取HashMap的视频详解！