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

关于HashMap的实现原理的详细讲解，看这篇文章就够了。HashMap在Java集合中的重要性不亚于Volatile在并发编程中的重要性（可见性和顺序）。我会重点介绍以下9点：HashMap数据结构HashMap核心成员HashMap节点数组HashMap数据存储HashMap哈希函数Hash碰撞：链式哈希表HashMapget方法：哈希函数HashMapput方法为什么槽数一定要用2^n？HashMap的数据结构首先从数据结构的角度来看：HashMap是：数组+链表+红黑树（JDK1.8增加了红黑树部分）的数据结构，如下注：需要两道题这里需要澄清的是：数据底层究竟存储了什么？这种存储方式有什么优点？1、核心成员默认初始容量（数组默认大小）：16，2的整数次方staticfinalintDEFAULT_INITIAL_CAPACITY=1<<4；最大容量staticfinalintMAXIMUM_CAPACITY=1<<30;默认负载因子staticfinalfloatDEFAULT_LOAD_FACTOR=0.75f；负载因子用于衡量HashMap的充实度，表示当map集合中存储的数据达到当前数组大小的75%时需要扩充链表到红黑树边界staticfinalintTREEIFY_THRESHOLD=8;红黑树移离链表边界staticfinalintUNTREEIFY_THRESHOLD=6;哈希桶数组瞬态Node[]表；实际存储的元素Numbertransientintsize；当map中的数据大于这个阈值时，会扩容intthresholdthreshold=table.length*loadFactor2.Nodearray从源码上看，HashMap类中有一个很重要的字段，就是Node[]table.即hashbucket数组，显然是Node的数组。staticclassNodeimplementsMap.Entry{finalinthash;//用于定位数组索引位置finalKkey;Vvalue;Nodeext;//链表的下一个Node节点Node(inthash,Kkey,Vvalue,Nodeext){this.hash=hash;this.key=key;this.value=value;this.next=next;}publicfinalKgetKey(){returnkey;}publicfinalVgetValue(){returnvalue;}publicfinalStringtoString(){returnkey+"="+value;}publicfinalinthashCode(){returnObjects.hashCode(key)^Objects.hashCode(value);}publicfinalVsetValue(VnewValue){VoldValue=value;value=newValue;returnoldValue;}publicfinalbooleanequals(Objecto){if(o==this)returntrue;if(oinstanceofMap.Entry){Map.Entrye=(Map.Entry)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为参数，通过一定的函数关系（称为哈希函数）计算出的值就是该元素的存储地址。表示为：Addr=H(key)，如下图所示：哈希表中哈希函数的设计非常重要，这也是构建哈希表过程中的关键问题之一。3.核心问题在构建哈希表之前，主要需要解决两个问题：构造一个合适的哈希函数，均匀性H(key)的值均匀分布在哈希表中冲突处理冲突：在哈希表中，不同的关键字值对应同一个存储位置的现象。4.哈希冲突：链式哈希表哈希表为了解决冲突可以使用地址法和链式地址法来解决问题。Java中的HashMap使用链地址方式。链地址法，简单来说就是数组和链表的组合，如下图所示：HashMap的哈希函数/***重新计算哈希值*/staticfinalinthash(Objectkey){inth;//h=key.hashCode()是第一步取hashCode值//h^(h>>>16)是第二步参与高位运算return(key==null)?0:(h=key.hashCode())^(h>>>16);}//计算数组slot(n-1)&hash对key进行hashCode运算得到一个32位的int值h，然后用h与h异或>>>16位。在JDK1.8的实现中，优化了高位运算的算法，通过hashCode()的高16位和低16位实现：(h=k.hashCode())^(h>>>16).这样做的好处是可以将hashcode的高位值和低位值混合进行异或运算，混合后将高位信息加入到低位信息中，从而使高位的-订单信息被伪装保存。这意味着哈希的高16位也参与了下标的计算。掺杂的元素越多，生成的哈希值的随机性就会增加，哈希碰撞就会减少。说明：^XOR：不同则为1，相同则为0>>>：无符号右移：右补0&运算：两位同时为“1”，结果为“1”，否则为0h&(table.length-1)获取对象的存储位，HashMap底层数组的长度永远是2的n次方。为什么槽数必须是2^n？1、为了让hash后的结果更加统一，如果slot的个数不是16，而是17，那么slot的计算公式就变成了：(17-1)&hash从上面可以看出，计算结果会大同小异。结果只剩下0和16两种，对hashmap来说简直是灾难。2、等价于长度模数当长度始终为2的n次方时，h&(length-1)运算等价于长度模数，即h%length，但&比%更高效。位运算的运算效率高于算术运算，因为算术运算还是会转化为位运算。最终目的是让散列的结果更加平均，减少散列冲突，提高hashmap的运行效率。分析HashMap的put方法：finalVputVal(inthash,Kkey,Vvalue,booleanonlyIfAbsent,booleanevict){Node[]tab;Nodep;intn,i;//当前对象的数组为null或者数组长度为0时，需要初始化数组if((tab=table)==null||(n=tab.length)==0){n=(tab=resize()).length;}//用Hash和数组length减一的值异或得到散乱的数组下标，表示根据计算，当前key会存放在这个位置。如果这个位置没有值，那么直接新建一个k-v节点，在里面存放//长度n是2的幂if((p=tab[i=(n-1)&hash])==null){tab[i]=newNode(hash,key,value,null);}//如果转到else步骤，说明key索引的数组内容已经存在，即发生碰撞//这个时候需要更复杂的方式来处理碰撞，比如链表和树else{Nodee;Kk;//节点key存在，直接覆盖valueif(p.hash==hash&&((k=p.key)==key||(key!=null&&key.equals(k)))){e=p;}//判断链是红黑树elseif(pinstanceofTreeNode){//这里代表当前的HashMap，tab是map中的数组e=((TreeNode)p).putTreeVal(this,tab,hash,key,value);}else{//判断该链为链表for(intbinCount=0;;++binCount){//如果当前碰撞的节点没有后续节点，直接新建一个节点，加上if((e=p.next)==null){p.next=newNode(hash,key,value,null);//TREEIFY_THRESHOLD=8//从0开始，如果是到了7，就说明满了8，这个时候需要Turn//重新判断是扩容还是切换到红黑树if(binCount>=TREEIFY_THRESHOLD-1)//-1for1sttreeifyBin(tab,hash);break;}//在碰撞节点中找到一个key完全相同的节点，用新节点替换旧节点if(e.hash==hash&&((k=e.key)==key||(key!=null&&key.equals(k))))break;p=e;}}//此时e为碰撞保存的节点，即老节点if(e!=null){//existingmappingforkeyVoldValue=e.value;//onlyIfAbsent是方法的调用参数，表示是否替换已有的值，//在默认的put方法中，这个值为false，所以旧值将被替换为新值if(!onlyIfAbsent||oldValue==null)e.value=value;//CallbackstoallowLinkedHashMappost-actionsafterNodeAccess(e);returnoldValue;}}//map变化操作计数器//如map结构化变化比如contentincreaseordecreaseorrehash，这会直接导致外部map的并发//迭代导致fail-fast问题，这个值是比较的基础++modCount;//size是k-v包含的个数地图//扩展maximumcapacityandexpandif(++size>threshold)resize();//CallbackstoallowLinkedHashMapppost-actionsafterNodeInsertion(evict);returnnull;}HashMap的put方法执行过程如下：判断键值对数组表是否[i]为空或null，否则执行resize()扩容；根据键值计算哈希值得到插入的数组索引i。如果table[i]==null，直接新建一个节点加入，判断table[i]的第一个元素是否和key相同。如果相同则直接覆盖value判断table[i]是否为treeNode，即table[i]是否为红黑树，如果为红黑树则直接insertkey-valuepairsintotree遍历table[i]，判断链表长度是否大于8，如果大于8，就把链表转成红黑树，插入在红黑树中进行操作，否则进行链表的插入操作；经过如果日历过程中发现key已经存在，可以直接覆盖value；插入成功后，判断实际键值对大小是否超过最大容量阈值，超过则扩容HashMap，总结HashMap底层结构？基于Map接口实现，数组+链表结构，JDK1.8增加了红黑树，链表长度>8变为红黑树，<6改变链表如果两个对象的hashcode相同会怎样？哈希冲突，HashMap使用链表解决哈希冲突HashMap中equals()和hashCode()的作用是什么？添加和获取HashMap时，需要通过key的hashCode()进行hash()，然后计算下标(n-1&hash)，从而获取相同的Location。当发生冲突（collision）时，使用key.equals()方法在链表或树中找到对应的节点。HashMap什么时候扩容？当put元素达到容量乘以加载因子时，是否默认实现16*0.75hash？h=key.hashCode())^(h>>>16)，hashCode进行16位无符号右移，然后按位异或得到这个key的哈希值，因为哈希表的容量是2目前元素的hashCode()往往低位相同，会造成冲突（collisions），所以1.8之后做了一个移位操作：右移元素的hashCode()与自身是16位或HashMap线程安全后的结果差异？HashMap读写效率更高，但是由于是异步的，即读写等操作没有锁保护，所以在多线程场景下并不安全。容易出现数据不一致，在单线程场景下强烈推荐。以上就是HashMap的介绍，希望对大家有所收获！