HashMap也是我们用的比较多的一个集合。它是Map接口基于哈希表的一种实现，以key-value的形式存在。在HashMap中，key-value总是会被当作一个整体，系统会根据hash算法计算出key-value的存储位置。我们总是可以通过键快速存储和检索值。下面分析一下HashMap的访问。1、定义HashMap实现了Map接口，继承于AbstractMap。其中，Map接口定义了键到值的映射规则，AbstractMap类提供了Map接口的主干实现，最大限度地减少了实现该接口所需的工作量。实际上，AbstractMap类已经实现了Map。在这里，地图LZ觉得应该更清楚些！复制代码publicclassHashMapextendsAbstractMapimplementsMap,Cloneable,Serializable{/***默认初始容量-必须是2的幂。*/staticfinalintDEFAULT_INITIAL_CAPACITY=1<<4;//aka16/***最大容量，如果更高的值被隐式指定*由带参数的构造函数中的任何一个使用。*必须是二的幂<=1<<30。*/staticfinalintMAXIMUM_CAPACITY=1<<30;/***构造函数中未指定时使用的加载因子。*/staticfinalfloatDEFAULT_LOAD_FACTOR=0.75f;/***表未膨胀时要共享的空表实例。*/staticfinalEntry[]EMPTY_TABLE={};/***表格，根据需要调整大小。长度必须始终是2的幂。*/transientEntry[]table=(Entry[])EMPTY_TABLE;/***此映射中包含的键值映射的数量。*/transientintsize;/***调整大小的下一个大小值（容量*负载因子）。*@serial*///如果table==EMPTY_TABLE那么这是初始容量，//在膨胀时将创建该表。intthreshold;/***哈希表的负载因子。**@serial*/finalfloatloadFactor;/***这个HashMap被结构修改的次数*结构修改是那些改变*HashMap中的映射数量或以其他方式修改其内部结构（例如，*rehash).该字段用于使HashMap的集合视图上的迭代器快速失败。（请参阅并发修改异常）。*/transientintmodCount;/***映射容量的默认阈值，超过该阈值的替代哈希*用于字符串键。由于String键的散列码计算较弱，替代散列减少了*冲突的发生率。**这个值可以通过定义系统属性来覆盖*{@codejdk.map.althashing.threshold}。{@code1}*的属性值强制始终使用替代哈希，而*{@code-1}值确保永远不会使用替代哈希。*/staticfinalintALTERNATIVE_HASHING_THRESHOLD_DEFAULT=Integer.MAX_VALUE;}复制代码2.构造函数HashMap提供了三个构造函数：HashMap():构造一个具有默认初始容量的哈希(16)EmptyHashMapwithdefaultloadfactor(0.75)HashMap(intinitialCapacity):构造一个具有指定初始容量和默认加载因子(0.75)的空HashMap。HashMap(intinitialCapacity,floatloadFactor)：构造一个具有指定初始容量和loadfactor的空HashMap。这里提到两个参数：初始容量，加载因子。这两个参数是影响HashMap性能的重要参数，其中容量表示哈希表的桶数，初始容量是哈希表创建时的容量，负载因子是哈希表能装多满在其容量自动增加之前衡量哈希表的空间使用情况。负载因子越大，哈希表的填充程度越高，反之亦然。对于使用链表方法的哈希表，平均查找一个元素的时间为O(1+a)，所以如果负载因子越大，空间利用得越充分，但带来的后果是查找效率降低;如果负载因子过大过小，那么哈希表中的数据就会过于稀疏，造成空间的严重浪费。系统默认的负载因子是0.75，一般我们不需要修改。HashMap是一种支持快速访问的数据结构。要了解它的性能，就必须了解它的数据结构。3、数据结构我们知道Java中最常用的两种结构是数组和模拟指针（引用）。几乎所有的数据结构都可以使用这两种组合来实现，HashMap也是如此。HashMap其实是一个“链表hash”，它的数据结构如下：HashMap数据结构图_thumb[13]从上图我们可以看出HashMap的底层实现仍然是一个数组，但是每一项数组是一个链。参数initialCapacity表示数组的长度。下面是HashMap构造函数的源码：if(initialCapacity>MAXIMUM_CAPACITY)initialCapacity=MAXIMUM;_CAPif(loadFactor<=0||Float.isNaN(loadFactor))thrownewIllegalArgumentException("非法加载因子："+loadFactor);this.loadFactor=loadFactor;阈值=初始容量；init();}可以看出，每创建一个新的HashMap，都会初始化一个表数组。表数组的元素是入口节点。静态类Entry实现Map.Entry{finalKkey;V值；接下来是条目；inthash;}其中Entry是HashMap的内部类，包含键key、值value、下一个节点next、hash值，这些都很重要。正是因为有了Entry，表格数组的项才形成了一个链表。上面简单分析了HashMap的数据结构，下面将讨论HashMap是如何实现快速访问的。4.存储实现：put(key,vlaue)首先看源码copycodepublicVput(Kkey,Vvalue){//当key为null时，调用putForNullKey方法保存null和第一个表的位置，这就是HashMap允许null的原因if(key==null)returnputForNullKey(value);//计算key的hash值inthash=hash(key.hashCode());------(1)//计算key哈希值在表数组中的位置inti=indexFor(hash,table.length);------(2)//从i开始迭代e，找到key保存的位置for(Entrye=table[i];e!=null;e=e.next){对象k;//判断这条链上是否有相同的hash值（相同的key）//如果相同则直接Overwritevalue返回旧值if(e.hash==hash&&((k=e.key)==key||key.equals(k))){VoldValue=e.value;//旧值=新值e.value=value;e.recordAccess(这个);返回旧值；//返回旧值}}//修改次数增加1modCount++;//将key和value添加到位置iaddEntry(hash,key,value,i);returnnull;}复制代码通过源码我们可以清楚的看到HashMap中保存数据的过程如下：首先判断key是否为null，如果为null则直接调用putForNullKey方法如果方法不为空，则先计算key的hash值，然后根据hash值在表数组中查找索引位置。如果table数组在这个位置有元素，比较是否存在相同的key，如果存在则覆盖原来key的值，否则保存链头元素（第一个保存的元素在末尾链）。如果表格那里没有元素，它会直接保存。这个过程看似比较简单，实则大有内幕。有以下几点：1.首先看迭代。这里之所以进行迭代，是为了防止存在相同的键值。如果发现两个哈希值（key）相同，HashMap的处理方式是用新值替换旧值。这里不处理key，说明没有两个相同的key。2.看（1）和（2）。HashMap的本质就在这里。第一种是哈希法，是一种纯数学计算，就是计算h的哈希值。复制代码finalinthash(Objectk){inth=hashSeed;if(0!=h&&kinstanceofString){returnsun.misc.Hashing.stringHash32((String)k);}h^=k.hashCode();//此函数确保每个位位置仅相差//常量倍数的hashCode具有有限的//冲突数（在默认加载因子下约为8）。h^=(h>>>20)^(h>>>12);returnh^(h>>>7)^(h>>>4);}复制代码HashMap底层数组长度永远是2的n次方，存在于构造函数中：capacity<<=1;这样做总能保证HashMap的底层数组长度是2的n次方。当length为2的n次方时，h&(length-1)相当于取模length，速度比直接取模快很多，是HashMap在速度上的一种优化。至于为什么是2的n次方，下面会解释。再回到indexFor方法，它只有一条语句：h&(length-1)，这条语句除了上面的取模运算之外，还有一个很重要的职责：均匀分布表数据，充分利用空间。这里我们假设length为16(2^n)和15，h为5,6,7。table1_thumb[3]当n=15时，6和7的结果是一样的，也就是说它们的存储位置在表相同，即发生碰撞，6和7会在一个位置形成链表，导致查询速度降低。的确，这里只分析三个数字，也不算多，所以我们来看0-15。table2_thumb[16]从上图我们可以看到一共发生了8次碰撞，发现浪费的空间非常大，1、3、5、7、9、11、13、15处都没有记录，也就是说，没有存储数据。这是因为当他们对14进行&运算时，结果的最后一位总是0，即0001、0011、0101、0111、1001、1011、1101、1111位置不可能存储数据，而空间减少，进一步增加了碰撞概率，这将导致查询速度变慢。而当length=16时，length-1=15为1111，那么在进行低位&运算时，其值始终与原来的hash值相同，而在进行高位运算时，其值为等于它的低阶值。因此，当length=2^n时，不同hash值发生碰撞的概率比较小，会使得表数组中的数据均匀分布，查询速度会更快。这里我们再回顾一下put的过程：当我们要向一个HashMap中添加一对key-value时，系统会先计算key的hash值，然后根据hash值确定在表中的存储位置.如果该位置没有元素，则直接插入。否则，遍历元素链表并相应地比较其键的哈希值。如果两个哈希值相等且键值相等（e.hash==hash&&((k=e.key)==key||key.equals(k))），则覆盖具有新Entry值的值的原始节点。如果两个哈希值相等但键值不相等，则将该节点插入到链表的头部。具体实现过程见addEntry方法，如下：{调整大小(2*table.length);散列=（空！=键）？散列（键）：0；bucketIndex=indexFor(hash,table.length);}createEntry(hash,key,value,bucketIndex);}复制代码this方法中有两点需要注意：一是链的生成。这是一个非常优雅的设计。系统总是将新的Entry对象添加到bucketIndex中。如果bucketIndex处已经有对象，那么新添加的Entry对象会指向原来的Entry对象，形成一个Entry链，但是如果bucketIndex处没有Entry对象，即e==null，那么新添加的Entry对象会指向null，不会生成Entry链。二是扩容问题。随着HashMap中元素个数的增加，发生碰撞的概率增加，得到的链表长度也越来越长，势必会影响HashMap的速度。为了保证HashMap的效率，系统必须在某个临界点进行扩容。临界点是当HashMap中的元素个数等于表数组长度*加载因子时。但是扩容是一个非常耗时的过程，因为需要重新计算这些数据在新表数组中的位置，并进行复制处理。所以如果我们对HashMap中的元素个数进行了预测，那么预置元素个数可以有效的提高HashMap的性能。5、读取实现：get(key)相对于HashMap的存储，读取相对简单。通过key的哈希值在table数组中找到索引处的Entry，然后返回key对应的value。复制代码publicVget(Objectkey){if(key==null)returngetForNullKey();条目条目=getEntry(键);返回null==条目？null:entry.getValue();}finalEntrygetEntry(Objectkey){if(size==0){返回null;}inthash=(key==null)?0：散列（键）；for(Entrye=table[indexFor(hash,table.length)];e!=null;e=e.next){对象k;如果(e.hash==hash&&((k=e.key)==key||(key!=null&&key.equals(k))))returne;}returnnull;}复制代码到这里，可以根据key快速获取value。除了离不开HashMap的数据结构之外，还与Entry有很大的关系，前面说过，HashMap在存储过程中并没有将key和value分开存储，而是将其作为一个整体的key-value来对待，这是条目对象。同时，value只相当于key的附属。在存储过程中，系统根据key的hashcode确定Entry在表数组中的存储位置，在检索过程中根据key的hashcode取出对应的Entry对象。
