介绍HashMap常用于键值对存储，那么它是如何实现键值存储的呢？1EntryEntry是Map接口中的一个内部接口，是实现键值对存储的关键。在HashMap中，有一个Entry的实现类，叫做Entry。Entry类很简单，里面包含了从外部引入的key，value，hash，以及下一个Entry对象的引用，很像数据结构中学里链表中的note节点。Entry类的属性和构造函数：finalKkey;Vvalue;Entrynext;inthash;/***Createsnewentry.*/Entry(inth,Kk,Vv,Entryn){value=v;next=n;key=k;hash=h;}二次HashMap初始化//HashMap构造方法publicHashMap(ininitialCapacity,floatloadFactor){if(initialCapacity<0)thrownewIllegalArgumentException("Illegalinitialcapacity:"+initialCapacity);if(initialCapacity>MAXIMUM_CAPACITY)initialCapacity=MAXIMUM_CAPACITY;if(loadFactor<=0||Float.isNaN(loadFactor))thrownewIllegalArgumentException("Illegalloadfactor:"+loadFactor);this.loadFactor=loadFactor;threshold=initialCapacity;init();}这是HashMap之一构造函数，其他构造函数引用这个构造函数进行初始化。参数InitialCapacity是指HashMap中表数组的初始大小，参数loadFactory是指HashMap所能容纳的键值对占数组长度的比例（例如：默认值数组长度为16，loadFactory默认值为0.75，如果HashMap存储的键值对超过12个，即Entry，会扩容，扩容后的大小是长度的两倍当前数组）。数组不会在构造函数中初始化，只有在put等操作方法中才会判断是初始化还是展开。三表数组在HashMap中有一个概念叫阈值（实际容量）。实际容量是指HashMap中允许的最大条目数，由HashMap中内置数组表的长度*loadFactory(loadfactor)来决定。它的作用是保证HashMap的效率。表数组是HashMap实现键值对存储的另一个key。具体的键值对是如何存储的？请看下图。图中的[key,value]是由Entry对象实现的，表数组用于存储Entry对象。//数组的初始化：privatestaticinroundUpToPowerOf2(intnumber){returnnumber>=MAXIMUM_CAPACITY?MAXIMUM_CAPACITY:(number>1)?Integer.highestOneBit((number-1)<<1):1;}privatevoidinflateTable(inttoSize){//Findapowerof2>=toSizeintcapacity=roundUpToPowerOf2(toSize);threshold=(int)Math.min(capacity*loadFactor,MAXIMUM_CAPACITY+1);table=newEntry[capacity];initHashSeedAsNeeded(capacity);}put方法中未初始化数组时会调用InflateTable方法进行初始化，入参为初始设置的InitialCapacity。实际上，它会调用roundUpToPowerOf2方法返回一个比初始容量大的最小2的幂（其中一个原因是方便获取Entry的数组位置）。四放方法publicVput(Kkey,Vvalue){if(table==EMPTY_TABLE){inflateTable(threshold);}if(key==null)returnputForNullKey(value);inthash=hash(key);inti=indexFor(hash,table.length);for(Entrye=table[i];e!=null;e=e.next){Objectk;if(e.hash==hash&&((k=e.key)==key||key.equals(k))){VoldValue=e.value;e.value=value;e.recordAccess(this);returnoldValue;}}modCount++;addEntry(hash,key,value,i);returnnull;}privateVputForNullKey(Vvalue){for(Entrye=table[0];e!=null;e=e.next){if(e.key==null){VoldValue=e.value;e.value=value;e.recordAccess(this);returnoldValue;}}modCount++;addEntry(0,null,value,0);returnnull;}voidaddEntry(inthash,Kkey,Vvalue,intbucketIndex){if((size>=阈值)&&(null!=table[bucketIndex])){resize(2*table.length);hash=(null!=key)?hash(key):0;bucketIndex=indexFor(hash,table.length);}createEntry(hash,key,value,bucketIndex);}voidcreateEntry(inthash,Kkey,Vvalue,intbucketIndex){Entrye=table[bucketIndex];table[bucketIndex]=newEntry<>(hash,key,value,e);size++;}在put方法中1.首先会判断数组是否为空，如果为空则初始化数组2.接下来，判断key是否为null，如果为null，使用第二种方法放入键值对。3、接下来对key进行hash得到一个value，再对value进行处理（IndexFor方法）得到在数组中的位置。4、接下来会在数组的位置遍历链表。如果key的hash与传入key的hash相同（key内存地址相等或equals方法相等），则表示更新链表中的值，返回旧值.价值价值。5.如果以上方法都不行，会调用第三个方法创建一个新的Entry对象。在putForNullKey方法中，我们看到它是专门为NULL值设置的，而NULL值的hash始终为0，所以key为NULL的Entry对象一定在数组的第0位。再次，找到就更新，找不到就添加。调用addEntry方法就是在数组链表中添加一个Entry，所以一开始会判断现有Entry的个数是否超过实际容量。如果超过，就会调用resize方法将数组扩容两次。注意，存储的Entry在扩容后会重新排列，因为IndexFor方法跟原来存储时数组的长度有关系。然后调用第四个方法。createEntry方法非常简单。就是把原来存放在数组中的链表的表头放入新的Entry中，再将新的Entry放入数组中。从这里可以看出HashMap不保证顺序的问题。get方法和contains方法的原理和put方法是一样的，就是通过key的hash得到数组中value所在链表头的位置，以及然后该值由equals方法确定。五其他//hash方法finalinthash(Objectk){inth=hashSeed;if(0!=h&&kinstanceofString){returnssun.misc.Hashing.stringHash32((String)k);}h^=k.hashCode();//此函数确保哈希代码仅通过//constantmultiplesateachbitpositionhaveabounded//numberofcollisions(approximately8atdefaultloadfactor).h^=(h>>>20)^(h>>>12);returnh^(h>>>7)^(h>>>4);}hashmethod最终的返回值与key的hashCode方法有关。总结最终的数组初始化大小会大于等于你传入的初始容量的最小2次方，key为null或者value为null之所以可以存储在HashMap中，是因为单独的操作会对空值执行。table数组中链表中每个Entry的共同点是key的hash(key.hashCode)部分是相同的。两个键映射一个对象时要注意键的hashCode和equals方法的重写，因为判断键是否相等的条件是（hashCode等于+（内存等于或等于等于））。最早存储的键值对将在链表的末尾。当数组中没有链表时，HashMap的性能至少是O(1)。最差的是O(threshould)。
