点击上方“架构技术精选”，选择“置顶或者星标”
你Float.isNaN(loadFactor))thrownewIllegalArgumentException("Illegalloadfactor:"+loadFactor);this.loadFactor=loadFactor;threshold=initialCapacity;
init();//init方法在HashMap中没有实际实现，不过在其子类如linkedHashMap中就会有对应实现}
从上面这段代码我们可以看出，在常规构造器中，没有为数组table分配内存空间（有一个入参为指定Map的构造器例外），而是在执行put操作的时候才真正构建table数组
OK,接下来我们来看看put操作的实现
publicVput(Kkey,Vvalue){//如果table数组为空数组{}，进行数组填充（为table分配实际内存空间），入参为threshold，//此时threshold为initialCapacity默认是14(24=16)if(table==EMPTY_TABLE){inflateTable(threshold);}//如果key为null，存储位置为table[0]或table[0]的冲突链上if(key==null)returnputForNullKey(value);inthash=hash(key);//对key的hashcode进一步计算，确保散列均匀inti=indexFor(hash,table.length);//获取在table中的实际位置for(EntryK,Ve=table;e!=null;e=e.next){//如果该对应数据已存在，执行覆盖操作。用新value替换旧value，并返回旧valueObjectk;if(e.hash==hash((k=e.key)==key
key.equals(k))){VoldValue=e.value;e.value=value;e.recordAccess(this);returnoldValue;}}modCount++;//保证并发访问时，若HashMap内部结构发生变化，快速响应失败addEntry(hash,key,value,i);//新增一个entryreturnnull;}
inflateTable这个方法用于为主干数组table在内存中分配存储空间，通过roundUpToPowerOf2(toSize)可以确保capacity为大于或等于toSize的最接近toSize的二次幂，比如toSize=13,则capacity=16;to_size=16,capacity=16;to_size=17,capacity=32.
privatevoidinflateTable(inttoSize){intcapacity=roundUpToPowerOf2(toSize);//capacity一定是2的次幂/**此处为threshold赋值，取capacity*loadFactor和MAXIMUM_CAPACITY+1的最小值，capaticy一定不会超过MAXIMUM_CAPACITY，除非loadFactor大于1*/threshold=(int)Math.min(capacity*loadFactor,MAXIMUM_CAPACITY+1);table=newEntry[capacity];initHashSeedAsNeeded(capacity);}
roundUpToPowerOf2中的这段处理使得数组长度一定为2的次幂，Integer.highestOneBit是用来获取最左边的bit（其他bit位为0）所代表的数值.
privatestaticintroundUpToPowerOf2(intnumber){//assertnumber=0:"numbermustbenon-negative";returnnumber=MAXIMUM_CAPACITY?MAXIMUM_CAPACITY:(number1)?Integer.highestOneBit((number-1)1):1;}
hash函数
/**这是一个神奇的函数，用了很多的异或，移位等运算对key的hashcode进一步进行计算以及二进制位的调整等来保证最终获取的存储位置尽量分布均匀*/finalinthash(Objectk){inth=hashSeed;if(0!=hkinstanceofString){returnsun.misc.Hashing.stringHash32((String)k);}h^=k.hashCode();h^=(h20)^(h12);returnh^(h7)^(h4);}
以上hash函数计算出的值，通过indexFor进一步处理来获取实际的存储位置
/***返回数组下标*/staticintindexFor(inth,intlength){returnh(length-1);}
h（length-1）保证获取的index一定在数组范围内，举个例子，默认容量16，length-1=15，h=18,转换成二进制计算为index=2。位运算对计算机来说，性能更高一些（HashMap中有大量位运算）
所以最终存储位置的确定流程是这样的：
再来看看addEntry的实现：
voidaddEntry(inthash,Kkey,Vvalue,intbucketIndex){if((size=threshold)(null!=table[bucketIndex])){resize(2*table.length);//当size超过临界阈值threshold，并且即将发生哈希冲突时进行扩容hash=(null!=key)?hash(key):0;bucketIndex=indexFor(hash,table.length);}createEntry(hash,key,value,bucketIndex);}
通过以上代码能够得知，当发生哈希冲突并且size大于阈值的时候，需要进行数组扩容，扩容时，需要新建一个长度为之前数组2倍的新的数组，然后将当前的Entry数组中的元素全部传输过去，扩容后的新数组长度为之前的2倍，所以扩容相对来说是个耗资源的操作。
三、为何HashMap的数组长度一定是2的次幂？
我们来继续看上面提到的resize方法
voidresize(intnewCapacity){Entry[]oldTable=table;intoldCapacity=oldTable.length;if(oldCapacity==MAXIMUM_CAPACITY){threshold=Integer.MAX_VALUE;return;}Entry[]newTable=newEntry[newCapacity];transfer(newTable,initHashSeedAsNeeded(newCapacity));table=newTable;threshold=(int)Math.min(newCapacity*loadFactor,MAXIMUM_CAPACITY+1);}
如果数组进行扩容，数组长度发生变化，而存储位置index=h(length-1),index也可能会发生变化，需要重新计算index，我们先来看看transfer这个方法
voidtransfer(Entry[]newTable,booleanrehash){intnewCapacity=newTable.length;
//for循环中的代码，逐个遍历链表，重新计算索引位置，将老数组数据复制到新数组中去（数组不存储实际数据，所以仅仅是拷贝引用而已）for(EntryK,Ve:table){while(null!=e){EntryK,Vnext=e.next;if(rehash){e.hash=null==e.key?0:hash(e.key);}inti=indexFor(e.hash,newCapacity);//将当前entry的next链指向新的索引位置,newTable有可能为空，有可能也是个entry链，如果是entry链，直接在链表头部插入。e.next=newTable;newTable=e;e=next;}}}
这个方法将老数组中的数据逐个链表地遍历，扔到新的扩容后的数组中，我们的数组索引位置的计算是通过对key值的hashcode进行hash扰乱运算后，再通过和length-1进行位运算得到最终数组索引位置。
HashMap的数组长度一定保持2的次幂，比如16的二进制表示为，那么length-1就是15，二进制为，同理扩容后的数组长度为32，二进制表示为0，length-1为31，二进制表示为1。从下图可以我们也能看到这样会保证低位全为1，而扩容后只有一位差异，也就是多出了最左位的1，这样在通过h(length-1)的时候，只要h对应的最左边的那一个差异位为0，就能保证得到的新的数组索引和老数组索引一致(大大减少了之前已经散列良好的老数组的数据位置重新调换)，个人理解。
还有，数组长度保持2的次幂，length-1的低位都为1，会使得获得的数组索引index更加均匀
我们看到，上面的运算，高位是不会对结果产生影响的（hash函数采用各种位运算可能也是为了使得低位更加散列），我们只
//如果key为null,则直接去table[0]处去检索即可。if(key==null)returngetForNullKey();EntryK,Ventry=getEntry(key);returnnull==entry?null:entry.getValue();}
get方法通过key值返回对应value，如果key为null，直接去table[0]处检索。我们再看一下getEntry这个方法
finalEntryK,VgetEntry(Objectkey){if(size==0){returnnull;}//通过key的hashcode值计算hash值inthash=(key==null)?0:hash(key);//indexFor(hashlength-1)获取最终数组索引，然后遍历链表，通过equals方法比对找出对应记录for(EntryK,Ve=table[indexFor(hash,table.length)];e!=null;e=e.next){Objectk;if(e.hash==hash((k=e.key)==key
(key!=nullkey.equals(k))))returne;}returnnull;}
可以看出，get方法的实现相对简单，key(hashcode)–hash–indexFor–最终索引位置，找到对应位置table，再查看是否有链表，遍历链表，通过key的equals方法比对查找对应的记录。要注意的是，有人觉得上面在定位到数组位置之后然后遍历链表的时候，e.hash==hash这个判断没必要，仅通过equals判断就可以。其实不然，试想一下，如果传入的key对象重写了equals方法却没有重写hashCode，而恰巧此对象定位到这个数组位置，如果仅仅用equals判断可能是相等的，但其hashCode和当前对象不一致，这种情况，根据Object的hashCode的约定，不能返回当前对象，而应该返回null，后面的例子会做出进一步解释。
四、重写equals方法需同时重写hashCode方法
最后我们再聊聊老生常谈的一个问题，各种资料上都会提到，“重写equals时也要同时覆盖hashcode”，我们举个小例子来看看，如果重写了equals而不重写hashcode会发生什么样的问题
publicclassMyTest{privatestaticclassPerson{intidCard;Stringname;publicPerson(intidCard,Stringname){this.idCard=idCard;this.name=name;}
Overridepublicbooleanequals(Objecto){if(this==o){returntrue;}if(o==nullgetClass()!=o.getClass()){returnfalse;}Personperson=(Person)o;//两个对象是否等值，通过idCard来确定returnthis.idCard==person.idCard;}}publicstaticvoidmain(String[]args){HashMapPerson,Stringmap=newHashMapPerson,String();Personperson=newPerson(,"乔峰");//put到hashmap中去map.put(person,"天龙八部");//get取出，从逻辑上讲应该能输出“天龙八部”System.out.println("结果:"+map.get(newPerson(,"萧峰")));}}实际输出结果：null
如果我们已经对HashMap的原理有了一定了解，这个结果就不难理解了。尽管我们在进行get和put操作的时候，使用的key从逻辑上讲是等值的（通过equals比较是相等的），但由于没有重写hashCode方法，所以put操作时，key(hashcode1)–hash–indexFor–最终索引位置，而通过key取出value的时候key(hashcode1)–hash–indexFor–最终索引位置，由于hashcode1不等于hashcode2，导致没有定位到一个数组位置而返回逻辑上错误的值null（也有可能碰巧定位到一个数组位置，但是也会判断其entry的hash值是否相等，上面get方法中有提到。）
所以，在重写equals的方法的时候，必须注意重写hashCode方法，同时还要保证通过equals判断相等的两个对象，调用hashCode方法要返回同样的整数值。而如果equals判断不相等的两个对象，其hashCode可以相同（只不过会发生哈希冲突，应尽量避免）。
五、JDK1.8中HashMap的性能优化
假如一个数组槽位上链上数据过多（即拉链过长的情况）导致性能下降该怎么办？JDK1.8在JDK1.7的基础上针对增加了红黑树来进行优化。即当链表超过8时，链表就转换为红黑树，利用红黑树快速增删改查的特点提高HashMap的性能，其中会用到红黑树的插入、删除、查找等算法。关于这方面的探讨我们以后的文章再做说明。附：HashMapput方法逻辑图（JDK1.8）
手写HashMap1.8v1.0版本定义统一接口
packageday03;importjava.util.HashMap;importjava.util.LinkedHashMap;importjava.util.Set;/***
since/11/28**/publicinterfaceIHashMapK,V{/***put()**paramkey*paramvalue*return*/Vput(Kkey,Vvalue);/***size()**return*/intsize();/***entrySet()**return*/SetIHashMap.EntryK,VentrySet();/***get()*paramkey*return*/Vget(Objectkey);/***Entry*paramK*paramV*/interfaceEntryK,V{KgetKey();VgetValue();VsetValue(Vvalue);}}实现类
packageday03;importjava.util.Set;/***p*IHashMap接口实现类*/p*
since/11/28**/publicclassIHashMapImplK,VimplementsIHashMapK,V{/***Theloadfactorforthehashtable.*哈希表的加载因子*serial*/finalfloatloadFactor;/***Theloadfactorusedwhennonespecifiedinconstructor.*构造函数中未指定时的加载因子*/staticfinalfloatDEFAULT_LOAD_FACTOR=0.75f;/***存储元素的数组*第一次使用时初始化的表，大小调整为必要的。分配时，长度总是2的幂*/transientNodeK,V[]table;/***转红黑树的阈值*/staticfinalintTREEIFY_THRESHOLD=8;/***此哈希映射在结构上被修改的次数*此字段用于对的集合视图生成迭代器*哈希映射失败得很快*/transientintmodCount;/***键值映射数（存储元素的个数）*/transientintsize;/***临界值，当实际大小（容量*加载因子）超过临界值时，会进行扩容*/intthreshold;/***最大容量*/staticfinalintMAXIMUM_CAPACITY=;/***默认初始化大小为16*/staticfinalintDEFAULT_INITIAL_CAPACITY=14;/***构造函数1*paraminitialCapacity：自定义初始化容量大小*paramloadFactor：自定义哈希表加载因子大小*/publicIHashMapImpl(intinitialCapacity,floatloadFactor){//限制指定的初始容量为非负if(initialCapacity0){thrownewIllegalArgumentException("Illegalinitialcapacity:"+initialCapacity);}//如果指定的初始容量大于最大容量，那么就设置为最大容量if(initialCapacityMAXIMUM_CAPACITY){initialCapacity=MAXIMUM_CAPACITY;}//限制哈希表的加载因子为正if(loadFactor=0Float.isNaN(loadFactor)){thrownewIllegalArgumentException("Illegalloadfactor:"+loadFactor);}//给加载因子赋值（自定义加载因子大小）this.loadFactor=loadFactor;//新的扩容临界值this.threshold=tableSizeFor(initialCapacity);}/***Returnsapoweroftwosizeforthegiventargetcapacity.*使得给定容量为（2^n）*/staticfinalinttableSizeFor(intcap){intn=cap-1;n
=n1;n
=n2;n
=n4;n
=n8;n
=n16;return(n0)?1:(n=MAXIMUM_CAPACITY)?MAXIMUM_CAPACITY:n+1;}/***构造函数2*
paraminitialCapacity：自定义哈希表的加载因子大小*/publicIHashMapImpl(intinitialCapacity){this(initialCapacity,DEFAULT_LOAD_FACTOR);}/***构造函数3（默认属性值）*/publicIHashMapImpl(){this.loadFactor=DEFAULT_LOAD_FACTOR;}/***构造函数4：用m的元素初始化散列映射*paramm*/publicIHashMapImpl(IHashMap?extendsK,?extendsVm){this.loadFactor=DEFAULT_LOAD_FACTOR;putMapEntries(m,false);}/***把IHashMap作为参数传入*paramm*paramevict*/finalvoidputMapEntries(IHashMap?extendsK,?extendsVm,booleanevict){ints=m.size();if(s0){if(table==null){floatft=((float)s/loadFactor)+1.0F;intt=((ft(float)MAXIMUM_CAPACITY)?(int)ft:MAXIMUM_CAPACITY);if(tthreshold){threshold=tableSizeFor(t);}}elseif(sthreshold){resize();}for(IHashMap.Entry?extendsK,?extendsVe:m.entrySet()){Kkey=e.getKey();Vvalue=e.getValue();putVal(hash(key),key,value,false,evict);}}}/***put()逻辑处理：*下面简单说下添加键值对put(key,value)的过程：*1，判断键值对数组tab[]是否为空或为null，否则以默认大小resize()；*2，根据键值key计算hash值得到插入的数组索引i，如果tab==null，直接新建节点添加，否则转入3*3，判断当前数组中处理hash冲突的方式为链表还是红黑树(check第一个节点类型即可),分别处理*paramkey*paramvalue*return*/OverridepublicVput(Kkey,Vvalue){returnputVal(hash(key),key,value,false,true);}Overridepublicintsize(){return0;}OverridepublicSetEntryK,VentrySet(){returnnull;}/***get()处理逻辑:*get(key)方法时获取key的hash值，计算hash(n-1)得到在链表数组中的位置*first=tab[hash(n-1)],先判断first的key是否与参数key相等，*不等就遍历后面的链表找到相同的key值返回对应的Value值即可*paramkey*return*/OverridepublicVget(Objectkey){NodeK,Ve;return(e=getNode(hash(key),key))==null?null:e.value;}/***getNode()具体实现*paramhash*paramkey*return*/finalNodeK,VgetNode(inthash,Objectkey){//Entry数组对象NodeK,V[]tab;//在tab数组中经过散列的第一个位置NodeK,Vfirst;NodeK,Ve;intn;Kk;//找到插入的第一个Node，方法是hash值和n-1相与，也就是说在一条链上的hash值相同if((tab=table)!=null(n=tab.length)0(first=tab[(n-1)hash])!=null){//检查第一个node是不是要找到的node，判断条件是hash值要相同，key值要相同if(first.hash==hash((k=first.key)==key(key!=nullkey.equals(k)))){returnfirst;}//检查first后面的nodeif((e=first.next)!=null){if(1==2){//TODO:红黑树处理逻辑}//遍历后面的链表，找到key值和hash值都相同的keydo{if(e.hash==hash((k=e.key)==key
(key!=nullkey.equals(k)))){returne;}}while((e=e.next)!=null);}}returnnull;}/***计算hash*
paramkey*return*/staticfinalinthash(Objectkey){inth;return(key==null)?0:(h=key.hashCode())^(h16);}/***put()方法具体业务逻辑实现*paramhash*paramkey*paramvalue*paramonlyIfAbsent*paramevict*return*/finalVputVal(inthash,Kkey,Vvalue,booleanonlyIfAbsent,booleanevict){NodeK,V[]tab;NodeK,Vp;intn,i;//1.如果tab为空或者tab的长度为0if((tab=table)==null(n=tab.length)==0){n=(tab=resize()).length;}//2.如果table在计算出的index下标对应的tab数组Node节点未初始化，就新创建一个Node节点插入到该位置if((p=tab[i=(n-1)hash])==null){tab=newNode(hash,key,value,null);}//3.这个分支说明计算出index值在tab数组中找到已经初始化的Node节点，就开始处理index冲突else{NodeK,Ve=null;Kk;//检查第一个Node，p是不是要找的值if(p.hash==hash((k=p.key)==key
(key!=nullkey.equals(k)))){//如果是，则把Nodee指向Nodepe=p;//如果不是则判断Nodep是否是红黑树类型}elseif(1==2){//TODO条件判断转红黑树的操作}else{//如果前面两种情况都不满足，则循环单链表for(intbinCount=0;;++binCount){//如果Nodep的下一个节点为空就挂在后面if((e=p.next)==null){p.next=newNode(hash,key,value,null);//如果链表长度大于等于8，看是否需要转为红黑树进行处理if(binCount=TREEIFY_THRESHOLD-1){//treeifyBin首先判断当前hashMap的长度，如果不足64，只进行//resize，扩容table，如果达到64，那么将冲突的存储结构为红黑树treeifyBin(tab,hash);}//终止循环条件break;}//如果Nodep的下一个节点不为空，检查下一个Node节点是否是我们要找的值if(e.hash==hash((k=e.key)==key
(key!=nullkey.equals(k)))){//如果找到了相同的key就结束遍历break;}//将Nodep节点指向Nodeep=e;}}//走到这个分支，说明链表上有相同的key值if(e!=null){VoldValue=e.value;if(!onlyIfAbsent
oldValue==null){e.value=value;}afterNodeAccess(e);//返回存在的value值returnoldValue;}}//安全，便与并发下的快速失败++modCount;//如果当前node节点个数大于临界值（初始容量*0.75）if(++sizethreshold){//扩容两倍resize();}afterNodeInsertion(evict);returnnull;}privatevoidafterNodeInsertion(booleanevict){}privatevoidtreeifyBin(NodeK,V[]tab,inthash){}privatevoidafterNodeAccess(NodeK,Ve){}privateNodeK,VnewNode(inthash,Kkey,Vvalue,Nodenext){returnnewNode(hash,key,value,next);}/***扩容机制*
return*/privateNodeK,V[]resize(){NodeK,V[]oldTab=table;intoldCap=(oldTab==null)?0:oldTab.length;//扩容临界值intoldThr=threshold;intnewCap;intnewThr=0;//1.如果旧表的长度大于0if(oldCap0){//如果扩容临界值大于等于最大容量，直接赋值为最大容量if(oldCap=MAXIMUM_CAPACITY){threshold=Integer.MAX_VALUE;returnoldTab;}//把新表的长度扩容为旧表长度的2倍elseif((newCap=oldCap1)MAXIMUM_CAPACITYoldCap=DEFAULT_INITIAL_CAPACITY){newThr=oldThr1;}}//2.如果旧表的长度为0，则说明是第一次初始化表elseif(oldThr0){newCap=oldThr;}else{newCap=DEFAULT_INITIAL_CAPACITY;newThr=(int)(DEFAULT_LOAD_FACTOR*DEFAULT_INITIAL_CAPACITY);}if(newThr==0){//新表长度乘以加载因子floatft=(float)newCap*loadFactor;newThr=(newCapMAXIMUM_CAPACITYft(float)MAXIMUM_CAPACITY?(int)ft:Integer.MAX_VALUE);}threshold=newThr;SuppressWarnings({"rawtypes","unchecked"})/**下面开始构造新表，初始化表中数据**/NodeK,V[]newTab=(NodeK,V[])newNode[newCap];//把新表赋值给tabletable=newTab;//原表不为空，把原表中的数据移到新表中if(oldTab!=null){/**遍历原来的旧表**/for(intj=0;joldCap;++j){NodeK,Ve;if((e=oldTab[j])!=null){oldTab[j]=null;if(e.next==null){newTab[e.hash(newCap-1)]=e;}elseif(1==2){//TODO:红黑树处理业务逻辑代码//如果e后边有链表，到这里表示e后面带着单个链表，需要遍历链表}else{NodeK,VloHead=null,loTail=null;NodeK,VhiHead=null,hiTail=null;NodeK,Vnext;//重新计算在新表中的位置，并进行搬运do{//记录下一个节点next=e.next;//新表是旧表的两倍容量，实例上就把单链表拆分为两队，//e.hasholdCap为偶数一队，e.hasholdCap为奇数一对if((e.hasholdCap)==0){if(loTail==null){loHead=e;}else{loTail.next=e;}loTail=e;}else{//lo队不为null，放在新表原位置if(hiTail==null){hiHead=e;//hi队不为null，放在新表j+oldCap位置}else{hiTail.next=e;}hiTail=e;}}while((e=next)!=null);if(loTail!=null){loTail.next=null;newTab[j]=loHead;}if(hiTail!=null){hiTail.next=null;newTab[j+oldCap]=hiHead;}}}}}returnnewTab;}/***Basichashbinnode,usedformostentries.(Seebelowfor*TreeNodesubclass,andinLinkedHashMapforitsEntrysubclass.)*/staticclassNodeK,VimplementsIHashMap.EntryK,V{finalinthash;finalKkey;Vvalue;NodeK,Vnext;Node(inthash,Kkey,Vvalue,NodeK,Vnext){this.hash=hash;this.key=key;this.value=value;this.next=next;}OverridepublicfinalKgetKey(){returnkey;}OverridepublicfinalVgetValue(){returnvalue;}OverridepublicfinalStringtoString(){returnkey+"="+value;}OverridepublicfinalVsetValue(VnewValue){VoldValue=value;value=newValue;returnoldValue;}}}未完待续....
热门技术内容：
01、浅谈Java代理设计模式，看完这篇文章瞬间秒懂了
02、RabbitMQ的应用总结，看完这篇文章，基本该有的都能搞懂~
03、Redis详解布隆过滤器和缓存穿透解决方案，你能知道有多少？
04、如何利用模板+工厂设计模式来实现异步回调
05、深度Mybatis源码分析，谈谈SqlSessionFactoryBuilder，Mapper接口绑定原理
06、深入分布式缓存从原理到实战之无处不在的缓存，你知道有多少？
07、SpringBoot2.0源码分析，虽然内容有点多，但是你将受益匪浅
08、源码分析，常用设计模式白话文总结，面试都问它
09、Mybatis深入源码分析之基于装饰模式纯手写一级，二级，三级缓存
10、Java中Integer基本数据类型，你真正了解有多少？
11、RedisRDB与AOF持久化机制的区别，你是否知道？
12、一篇文章带你读懂MyBatis源码，让你更接近技术底层，学完源码涨薪资~
13、ELK分布式日志收集搭建和使用，你可能想象不到有些技术点，你竟然不知道！
14、Java中Synchronize深入，你了解多少锁？看完这篇你就知道了，仅需5分钟！
15、架构技术必学：分布式链路监控与追踪系统Zipkin，看完多少会有点收获~
长按