HashMap和HashSet是JavaCollectionFramework的两个重要成员，其中HashMap是Map接口的常用实现类，HashSet是Set接口的常用实现类。虽然HashMap和HashSet实现的接口规范不同，但它们底层的Hash存储机制完全一样，甚至HashSet本身就采用HashMap来实现的。

　　通过HashMap、HashSet的源代码分析其Hash存储机制

　　实际上，HashSet和HashMap之间有很多相似之处，对于HashSet而言，系统采用Hash算法决定集合元素的存储位置，这样可以保证能快速存、取集合元素；对于HashMap而言，系统key-value当成一个整体进行处理，系统总是根据Hash算法来计算key-value的存储位置，这样可以保证能快速存、取Map的key-value对。

　　在介绍集合存储之前需要指出一点：虽然集合号称存储的是Java对象，但实际上并不会真正将Java对象放入Set集合中，只是在Set集合中保留这些对象的引用而言。也就是说：Java集合实际上是多个引用变量所组成的集合，这些引用变量指向实际的Java对象。

　　集合和引用

　　就像引用类型的数组一样，当我们把Java对象放入数组之时，并不是真正的把Java对象放入数组中，只是把对象的引用放入数组中，每个数组元素都是一个引用变量。

　　 HashMap的存储实现

　　当程序试图将多个key-value放入HashMap中时，以如下代码片段为例：

　　 Java代码

　　 HashMapmap=newHashMap（）；

　　 map.put（"语文",80.0）；

　　 map.put（"数学",89.0）；

　　 map.put（"英语",78.2）；

　　 HashMap采用一种所谓的“Hash算法”来决定每个元素的存储位置。

　　当程序执行map.put（"语文",80.0）；时，系统将调用"语文"的hashCode（）方法得到其hashCode值——每个Java对象都有hashCode（）方法，都可通过该方法获得它的hashCode值。得到这个对象的hashCode值之后，系统会根据该hashCode值来决定该元素的存储位置。

　　我们可以看HashMap类的put（Kkey,Vvalue）方法的源代码：

　　 Java代码

　　 publicVput（Kkey,Vvalue）

　　 {

　　 //如果key为null，调用putForNullKey方法进行处理

　　 if（key==null）

　　 returnputForNullKey（value）；

　　 //根据key的keyCode计算Hash值

　　 inthash=hash（key.hashCode（））；

　　 //搜索指定hash值在对应table中的索引

　　 inti=indexFor（hash,table.length）；

　　 //如果i索引处的Entry不为null，通过循环不断遍历e元素的下一个元素

　　 for（Entrye=table[i];e!=null;e=e.next）

　　 {

　　 Objectk;

　　 //找到指定key与需要放入的key相等（hash值相同

　　 //通过equals比较放回true）

　　 if（e.hash==hash&&（（k=e.key）==key

　　 ||key.equals（k）））

　　 {

　　 VoldValue=e.value;

　　 e.value=value;

　　 e.recordAccess（this）；

　　 returnoldValue;

　　 }

　　 }

　　 //如果i索引处的Entry为null，表明此处还没有Entry

　　 modCount++;

　　 //将key、value添加到i索引处

　　 addEntry（hash,key,value,i）；

　　 returnnull;

　　 }

　　上面程序中用到了一个重要的内部接口：Map.Entry，每个Map.Entry其实就是一个key-value对。从上面程序中可以看出：当系统决定存储HashMap中的key-value对时，完全没有考虑Entry中的value，仅仅只是根据key来计算并决定每个Entry的存储位置。这也说明了前面的结论：我们完全可以把Map集合中的value当成key的附属，当系统决定了key的存储位置之后，value随之保存在那里即可。

　　上面方法提供了一个根据hashCode（）返回值来计算Hash码的方法：hash（），这个方法是一个纯粹的数学计算，其方法如下：

　　 Java代码

　　 staticinthash（inth）

　　 {

　　 h^=（h>>>20）^（h>>>12）；

　　 returnh^（h>>>7）^（h>>>4）；

　　 }

　　对于任意给定的对象，只要它的hashCode（）返回值相同，那么程序调用hash（inth）方法所计算得到的Hash码值总是相同的。接下来程序会调用indexFor（inth,intlength）方法来计算该对象应该保存在table数组的哪个索引处。indexFor（inth,intlength）方法的代码如下：

　　 Java代码

　　 staticintindexFor（inth,intlength）

　　 {

　　 returnh&（length-1）；

　　 }

　　这个方法非常巧妙，它总是通过h&（table.length-1）来得到该对象的保存位置——而HashMap底层数组的长度总是2的n次方，这一点可参看后面关于HashMap构造器的介绍。

　　当length总是2的倍数时，h&（length-1）将是一个非常巧妙的设计：假设h=5,length=16,那么h&length-1将得到5；如果h=6,length=16,那么h&length-1将得到6……如果h=15,length=16,那么h&length-1将得到15；但是当h=16时,length=16时，那么h&length-1将得到0了；当h=17时,length=16时，那么h&length-1将得到1了……这样保证计算得到的索引值总是位于table数组的索引之内。

　　根据上面put方法的源代码可以看出，当程序试图将一个key-value对放入HashMap中时，程序首先根据该key的hashCode（）返回值决定该Entry的存储位置：如果两个Entry的key的hashCode（）返回值相同，那它们的存储位置相同。如果这两个Entry的key通过equals比较返回true，新添加Entry的value将覆盖集合中原有Entry的value，但key不会覆盖。如果这两个Entry的key通过equals比较返回false，新添加的Entry将与集合中原有Entry形成Entry链，而且新添加的Entry位于Entry链的头部——具体说明继续看addEntry（）方法的说明。

　　当向HashMap中添加key-value对，由其key的hashCode（）返回值决定该key-value对（就是Entry对象）的存储位置。当两个Entry对象的key的hashCode（）返回值相同时，将由key通过eqauls（）比较值决定是采用覆盖行为（返回true），还是产生Entry链（返回false）。

　　上面程序中还调用了addEntry（hash,key,value,i）；代码，其中addEntry是HashMap提供的一个包访问权限的方法，该方法仅用于添加一个key-value对。下面是该方法的代码：

　　 Java代码

　　 voidaddEntry（inthash,Kkey,Vvalue,intbucketIndex）

　　 {

　　 //获取指定bucketIndex索引处的Entry

　　 Entrye=table[bucketIndex];//①

　　 //将新创建的Entry放入bucketIndex索引处，并让新的Entry指向原来的Entry

　　 table[bucketIndex]=newEntry（hash,key,value,e）；

　　 //如果Map中的key-value对的数量超过了极限

　　 if（size++>=threshold）

　　 //把table对象的长度扩充到2倍。

　　 resize（2*table.length）；//②

　　 }

　　上面方法的代码很简单，但其中包含了一个非常优雅的设计：系统总是将新添加的Entry对象放入table数组的bucketIndex索引处——如果bucketIndex索引处已经有了一个Entry对象，那新添加的Entry对象指向原有的Entry对象（产生一个Entry链），如果bucketIndex索引处没有Entry对象，也就是上面程序①号代码的e变量是null，也就是新放入的Entry对象指向null，也就是没有产生Entry链。

　　 JDK源码

　　在JDK安装目录下可以找到一个src.zip压缩文件，该文件里包含了Java基础类库的所有源文件。只要读者有学习兴趣，随时可以打开这份压缩文件来阅读Java类库的源代码，这对提高读者的编程能力是非常有帮助的。需要指出的是：src.zip中包含的源代码并没有包含像上文中的中文注释，这些注释是笔者自己添加进去的。

　　 Hash算法的性能选项

　　根据上面代码可以看出，在同一个bucket存储Entry链的情况下，新放入的Entry总是位于bucket中，而最早放入该bucket中的Entry则位于这个Entry链的最末端。

　　上面程序中还有这样两个变量：

　　 *size：该变量保存了该HashMap中所包含的key-value对的数量。

　　 *threshold：该变量包含了HashMap能容纳的key-value对的极限，它的值等于HashMap的容量乘以负载因子（loadfactor）。

　　从上面程序中②号代码可以看出，当size++>=threshold时，HashMap会自动调用resize方法扩充HashMap的容量。每扩充一次，HashMap的容量就增大一倍。