Java的HashMap用的多，但是你了解过它的内部实现原理吗？数据是如何存储的？如何处理哈希冲突？本文将带大家深入源码，一探HashMap的实现原理。DocumentationNoteHashMap是Map接口的一个实现类，它实现了所有的可选操作，并允许nullkey和nullvalue。（可以简单理解为与HashTable功能相同，只是它是异步的，支持空值。）访问效率：当存储的元素均匀分布在桶中时，获取和放入元素的时间不变。遍历的效率与capacity有关，所以如果注重遍历的效率，capacity的初始值不要设置太大，loadfactor也不要设置的太小。异步：不要使用多个线程同时修改。1.类定义publicclassHashMapextendsAbstractMapimplementsMap,Cloneable,Serializable{继承自AbstractMap，实现Map,Cloneable,Serializable接口。1）实现的接口Cloneable和Serializabel都是标识接口，里面没有方法定义。实现这个接口只是用来标识这个类应该有这个功能。Map接口中定义了要实现的方法，给出了部分方法的实现。https://blog.csdn.net/weixin_44203158/article/details/109340113问：方法可以在接口中实现吗？答：是的！这个函数是从Java8开始加入的。主要考虑的是，如果接口改变了，所有的实现类都要做相应的修改。但是接口可以实现方法后，实现类就不用再改了。Q：接口中的实现方法有default和static两种修改方式？A：用default修饰的方法称为默认方法，用static修饰的方法称为静态方法。default可以被覆盖，但static不能。Q：多个接口默认方法冲突怎么办？A：在实现类中重写，在接口中调用默认方法。问：那为什么不使用抽象类呢？A：抽象类不能继承多个。2）继承类AbstractMap提供了Map接口的基本实现，减少了实现Map接口的工作量。对于不可变的Map实现类，只需要实现entrySet()方法即可。对于可变的Map实现类，还需要实现put()、remove()等方法。二、成员变量/***默认初始容量-必须是二的幂。*/staticfinalintDEFAULT_INITIAL_CAPACITY=1<<4;//aka16/***最大容量，如果更高的值被隐式指定*由带参数的构造函数中的任何一个使用。*必须是二的幂<=1<<30。*/staticfinalintMAXIMUM_CAPACITY=1<<30;/***构造函数中未指定时使用的加载因子。*/staticfinalfloatDEFAULT_LOAD_FACTOR=0.75f;/***使用树而不是列表的bin计数阈值*bin。将元素添加到至少具有这么多节点的容器时，容器将转换为树。该值必须大于*2，并且至少应为8，以符合*树木移除中关于在收缩时转换回普通垃圾箱的假设。*/staticfinalintTREEIFY_THRESHOLD=8;/***bin计数threeshold用于在*resize操作期间取消树化（拆分）bin。应小于TREEIFY_THRESHOLD，并且至多6以在移除下使用收缩检测进行网格划分。*/staticfinalintUNTREEIFY_THRESHOLD=6;/***可将bin树化的最小表容量。*（否则，如果bin中的节点太多，则调整表的大小。）*应至少为4*TREEIFY_THRESHOLD以避免冲突*调整大小和树化阈值之间。*/staticfinalintMIN_TREEIFY_CAPACITY=6从变量和注释可以看出HashMap类的一些特性定义了容量需要是2的幂所以在表达的时候，也是通过位运算来定义的。当默认负载达到75%时，会扩容单个bucket。如果单个桶存储的元素个数大于8，就会变成树存储。如果小于6，则改回列存。只有容量大于64才会触发。为什么单个节点的树变换容量使用2的幂？HashMap中采用取余法，即table[hash%length]是现代CPU中最慢的运算，于是人们想到了一个巧妙的优化方法，即当length为2的指数次方时，hash%length=hash&(length-1)是怎么做到的呢？https://www.cnblogs.com/sanzao/p/10245212.htmlhttps://blog.csdn.net/u014540814/article/details/88354793//下面的代码是用来调整容量到下一个2幂数//简单的说，位运算就是把这个数的第一个1之后的所有位都替换成1staticfinalinttableSizeFor(intcap){intn=cap-1;n|=n>>>1;n|=n>>>2;n|=n>>>4;n|=n>>>8;n|=n>>>16；返回（n<0）？1:(n>=MAXIMUM_CAPACITY)?MAXIMUM_CAPACITY:n+1;}标记为transient的变量问：transient关键字有什么作用？A：防止属性被序列化Q：为什么要使用瞬态修改？A：出于安全考虑，考虑transientNode[]表；3、重要的内部类1）Node最重要的内部类Node，定义了HashMap中的节点。/***基本哈希bin节点，用于大多数条目。（参见下面的*TreeNode子类，以及LinkedHashMap的Entry子类。）*/staticclassNodeimplementsMap.Entry{finalinthash;最后的K键；V值；下一个节点；Node(inthash,Kkey,Vvalue,Nodenext){this.hash=hash;this.key=键；this.value=值；这个.下一个=下一个；}//......}注意泛型类的使用https://segmentfault.com/a/1190000002646193问：什么是泛型类？A：类名+一对尖括号。人。在JDK5中出现。问：为什么要使用泛型类？A：其中一个重要的原因是创建容器类。假设没有泛型，为了支持不同类型的容器，可能需要定义多个类来支持。但是对于泛型，您只能定义一个。减少编码冗余。问：通用定义写在哪里？A：泛型类写在类名之后，泛型方法写在返回类型之前。Q：什么时候确定泛型类型？A：应该在编译时确定。有4个成员变量finalinthash;finalKkey;Vvalue;Nodenext;hashCode()计算方式有点奇怪？publicfinalinthashCode(){returnObjects.hashCode(key)^Objects.hashCode(value);//为什么要使用XOR运算符？}4。重要函数hash()staticfinalinthash(Objectkey){inth;返回（键==空）？0:(h=key.hashCode())^(h>>>16);}getNode()这个体现了很多设计思想first=tab[(n-1)&hash]从这里我们可以猜测hash的底层是放在一个数组中，数组的容量设计为索引为2，其中n-1个二进制全为1，便于&运算。当节点发生冲突时，有两种方法可以检索冲突。先判断是否是树节点，然后依次遍历finalNodegetNode(inthash,Objectkey){Node[]tab;节点先，e；诠释n;Kk;if((tab=table)!=null&&(n=tab.length)>0&&(first=tab[(n-1)&hash])!=null){if(first.hash==hash&&//始终检查第一个节点((k=first.key)==key||(key!=null&&key.equals(k))))首先返回；if((e=first.next)!=null){if(firstinstanceofTreeNode)return((TreeNode)first).getTreeNode(hash,key);}做{if(e.hash==hash&&((k=e.key)==key||(key!=null&&key.equals(k))))returne;}while((e=e.next)!=null);}}返回空值；如果容量判断桶中没有元素，直接新建一个桶。如果桶中有元素，先判断key值是否存在。如果存在，该值将被替换。如果是树结构，按照树的方法处理。是一个链表结构，遍历看是否有相同的key。如果需要新建一个Node节点树转换计数+1表存储容量+1，如果大于阈值，则resize()finalVputVal(inthash,Kkey,Vvalue,booleanonlyIfAbsent,booleanevict){节点[]选项卡；节点p;诠释n,我;如果((tab=table)==null||(n=tab.length)==0)n=(tab=resize()).length;如果((p=tab[i=(n-1)&hash])==null)tab[i]=newNode(hash,key,value,null);else{节点e;Kk;if(p.hash==hash&&((k=p.key)==key||(key!=null&&key.equals(k))))e=p;elseif(pinstanceofTreeNode)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);如果（binCount>=TREEIFY_THRESHOLD-1)//-1表示第一个treeifyBin(tab,hash);休息;}if(e.hash==hash&&((k=e.key)==key||(key!=null&&key.equals(k))))中断；p=e;}}if(e!=null){//键VoldValue=e.value的现有映射；如果(!onlyIfAbsent||oldValue==null)e.value=value;节点访问后（e）；返回旧值；}}++模数；如果（++大小>阈值）调整大小（）；节点插入后（逐出）；返回空值；扩容时容量翻倍elseif((newCap=oldCap<<1)=DEFAULT_INITIAL_CAPACITY)newThr=oldThr<<1;//双阈值//重新排列数据(intj=0;je;如果((e=oldTab[j])!=null){oldTab[j]=null;if(e.next==null)//如果节点没有hash冲突，则转到原位置或两倍位置newTab[e.hash&(newCap-1)]=e;elseif(einstanceofTreeNode)//如果存在hash冲突，且冲突较多（使用树存储），则拆除Split((TreeNode)e).split(this,newTab,j,老帽);else{//preserveorder//如果存在hash冲突，则存入list，整体放入[j+oldCap]NodeloHead=null,loTail=null;NodehiHead=null,hiTail=null;下一个节点；做{next=e.next;if((e.hash&oldCap)==0){if(loTail==null)loHead=e;否则loTail.next=e;loTail=e;}else{if(hiTail==null)hiHead=e;否则hiTail.n分机=电子；高尾=e;}}while((e=next)!=null);if(loTail!=null){loTail.next=null;newTab[j]=loHead;}if(hiTail!=null){hiTail.next=null;newTab[j+oldCap]=hiHead;}}}}treeifyBin()finalvoidtreeifyBin(Node[]tab,inthash){intn,index;节点e;//如果表本身容量还小，先使用扩容if(tab==null||(n=tab.length)hd=null,tl=null;do{//实际上调用了LinkedHashMap的构造方法，TreeNode也是LinkedHashMap的扩展TreeNodep=replacementTreeNode(e,null);//这是一个双向链表if(tl==null)hd=p;else{p.prev=tl;tl.next=p;}tl=p;}while((e=e.next)!=null);if((tab[index]=hd)!=null)//将链??表转为树（红黑树），我没研究过hd.treeify(tab);}}下面的功能类似，大家可以自行探索
