Java集合类的整体结构比较重要。集合类图如下：OrderedNo允许元素重复NoCollectionNoListYesSetAbstractSetNoHashSetTreeSetYes(二叉树排序)MapAbstractMap是否使用key-value来映射映射和存储数据，Key必须唯一，value可以重复HashMapTreeMap是（按二叉树排序的）HashMap详解HashMap和HashSet是JavaCollectionFramework的两个重要成员，其中HashMap是CollectionFramework的常用实现类Map接口，而HashSet是Set接口的实现类常用的实现类HashMap和HashSet虽然实现的接口规范不同，但是它们底层的Hash存储机制是完全一样的，甚至HashSet本身也是使用HashMap实现的（使用HashMap的key用来存放HashSet的value，value是一个无意义的对象。）。通过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时，以如下代码片段为例：HashMapmap=newHashMap();map.put("高数",60.0);map.put("大营",89.0);map.put("大对象",78.2);HashMap使用一种所谓的“Hash算法”来确定每个元素的存储位置。当程序执行map.put("HighNumber",60.0);时，系统会调用"HighNumber"的hashCode()方法获取它的hashCode值——每个Java对象都有一个hashCode()方法，可以用于获取其hashCode值的方法。系统得到这个对象的hashCode值后，会根据hashCode值确定元素的存储位置。我们可以看看HashMap类的put(Kkey,Vvalue)方法的源码：publicVput(Kkey,Vvalue){//如果key为null，调用putForNullKey方法进行处理if(key==null)returnputForNullKey(值);//根据key的keyCode计算Hash值inthash=hash(key.hashCode());//在对应表中查找指定hash值的索引inti=indexFor(hash,table.length);//如果第i个Entry处的索引不为null，则通过循环不断遍历e元素的下一个元素for(Entrye=table[i];e!=null;e=e.next){Objectk;//找到指定的key和需要放入的key相等（hash值相同//相等比较放回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，则表示没有EntrymodCount++;//将key和value添加到indexiAddEntry(hash,key,value,i);returnnull;}上面程序中用到了一个重要的内部接口：Map.Entry，每个Map.Entry其实就是键值对。从上面的程序可以看出，系统在决定将key-value对存储到HashMap中时，根本没有考虑Entry中的value，只是根据钥匙。这也说明了之前的结论：我们完全可以把Map集合中的value看成是key的附属。当系统确定了键的存储位置后，就可以将值存储在那里。上面的方法提供了一种根据hashCode()的返回值计算Hash码的方法：hash()，该方法是纯数学计算，方法如下：staticinthash(inth){h^=(h>>>20)^(h>>>12);returnh^(h>>>7)^(h>>>4);}对于任何给定的对象，只要它的hashCode()返回相同的值，那么程序调用hash(inth)方法计算出的Hash码值始终不变。接下来，程序会调用indexFor(inth,intlength)方法来计算对象应该存储在表数组中的哪个索引处。indexFor(inth,intlength)方法的代码如下：staticintindexFor(inth,intlength){returnh&(length-1);}这个方法很巧妙，总是通过h&(table.length获取对象-1)HashMap的存储位置——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方法的源码，当程序试图将一个键值对放入HashMap时，程序首先根据key的hashCode()返回值来确定Entry的存储位置：如果key为两个Entry的hashCode()返回相同的值，则它们的存储位置相同。如果两个Entry的key通过equals比较返回true，则新添加的Entry的值会覆盖集合中原有Entry的值，但key不会。如果两个Entry的key通过equals比较返回false，则新添加的Entry会和集合中原来的Entry组成一个Entry链，新添加的Entry位于Entry链的头部——继续看addEntry()方法的详细说明。在HashMap中添加键值对时，键值对（即Entry对象）的存储位置由键的hashCode()的返回值决定。当两个Entry对象的key的hashCode()返回值相同时，key会通过eqauls()比较value，决定是采用覆盖行为（returntrue）还是生成一个Entry链（returnfalse).上面的程序还调用了addEntry(hash,key,value,i);code，其中addEntry是HashMap提供的包访问方法，只用于添加键值对。下面是该方法的代码：voidaddEntry(inthash,Kkey,Vvalue,intbucketIndex){//获取指定bucketIndex索引处的EntryEntrye=table[bucketIndex];//①//把新的创建的Entry输入bucketIndex索引，并让新的Entry指向原来的Entrytable[bucketIndex]=newEntry(hash,key,value,e);//如果Map中键值对的个数exceedsthelimitif(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中包含的源代码没有像上面这样的中文注释，这些注释是作者自己添加的。哈希算法性能选项根据上面的代码可以看出，在同一个桶中存放Entry链的情况下，新放入的Entry总是位于桶中，最早放入桶中的Entry位于入口链的末端。结尾。上面程序中还有两个变量：*size：这个变量保存了HashMap包含的键值对的个数。*threshold：这个变量包含了HashMap所能容纳的键值对的限制，它的值等于HashMap的容量乘以负载因子（loadfactor）。从上面程序中的代码②可以看出，当size++>=threshold时，HashMap会自动调用resize方法对HashMap进行扩容。每扩容一次，HashMap的容量就增加一倍。上面程序中使用的表其实就是一个普通的数组，每个数组的长度都是固定的，这个数组的长度就是HashMap的容量。HashMap包含以下构造函数：*HashMap()：构造一个初始容量为16，负载因子为0.75的HashMap。*HashMap(intinitialCapacity)：构造一个初始容量为initialCapacity、加载因子为0.75的HashMap。*HashMap(intinitialCapacity,floatloadFactor)：创建一个指定初始容量和指定加载因子的HashMap。在创建HashMap时，系统会自动创建一个表数组来保存HashMap中的Entry。下面是HashMap中一个构造函数的代码：//创建一个指定初始容量和加载因子的HashMap容量不能为负if(initialCapacity<0)thrownewIllegalArgumentException("Illegalinitialcapacity:"+initialCapacity);//如果初始容量大于最大容量，让显示容量if(initialCapacity>MAXIMUM_CAPACITY)initialCapacity=MAXIMUM_CAPACITY;//负载因子必须大于0的值if(loadFactor<=0||Float.isNaN(loadFactor))thrownewIllegalArgumentException(loadFactor);//计算大于initialCapacity的最小2次方值。intcapacity=1;while(capacitye=table[indexFor(hash,table.length)];e!=null;//寻找Entry的下一个Entrechain=e.next)//①{Objectk;//如果Entry的key与searchedkeyif(e.hash==hash&&((k=e.key)==key||key.equals(k)))return.value;}returnnull;}从上面的代码可以看出ifHashMap的每个bucket中只有一个Entry，HashMap可以很快发生“Hash冲突”，单个bucket中存储的不是一个Entry，而是一个Entry链，系统必须依次遍历每个Entry，直到找到TheEntryyouwanttosearchforSofar-如果要搜索的Entry恰好在E的末尾ntry链（先将Entry放入桶中），则系统必须循环到***找到元素。简单总结一下，HashMap在底层把key-value当成一个整体，这个整体就是一个Entry对象。HashMap的底层使用一个Entry[]数组来存储所有的键值对。当需要存储一个Entry对象时，会根据Hash算法确定其存储位置；当需要取出一个Entry时，也会根据Hash算法找到它的存储位置。位置，直接取出Entry。由此可见，HashMap之所以能够快速存储和检索其包含的Entry，完全类似于我们妈妈在现实生活中教给我们的：不同的东西应该放在不同的位置，需要的时候可以快速找到.在创建HashMap时，有一个默认的加载因子（loadfactor），默认值为0.75，这是时间和空间成本的权衡：增加加载因子可以减少Hash表（即Entry数组）占用内存空间，但会增加查询数据的时间开销，而查询是最频繁的操作（HashMap的get()和put()方法都使用query）；降低负载因子会提高数据查询的性能，但会增加哈希表占用的内存空间。掌握了以上知识后，我们在创建HashMap时就可以根据实际需要适当调整loadfactor的取值；如果程序比较在意空间开销，内存紧张，可以适当增加负载因子；如果程序比较在意时间开销，memoryAmple可以适当降低loadfactor。通常，程序员不需要改变负载因子的值。如果一开始就知道HashMap会保存多个键值对，那么在创建的时候可以使用更大的初始容量。如果HashMap的条目数永远不会超过限制容量（容量*负载因子），HashMap就不需要调用resize()方法重新分配表数组，从而保证更好的性能。当然，一开始将初始容量设置过大可能会浪费空间（系统需要创建一个长度为容量的Entry数组），所以创建HashMap时的初始容量设置也需要慎重对待。
