java中HashMap详解
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的容量就增大一倍。