3.3 Map

Map是一种由多组key-value（键值对）集合在一起的结构，其中，key值是不能重复的，而value值则无此限定。其基本接口为java.util.Map，该接口提供了Map结构的关键方法，比如常见的put和get，下面将分别介绍Map的多种不同的实现类。

3.3.1 HashMap

HashMap是最常用的Map结构，Map的本质是键值对。它使用数组来存放这些键值对，键值对与数组下标的对应关系由key值的hashcode来决定，这种类型的数据结构可以称之为哈希桶。

在Java语言中，hashCode是个int值，虽然int的取值范围是[-232，231-1]，但是Java的数组下标只能是正数，所以该哈希桶能存储[0,231-1]区间的哈希值。这个存储区间可以存储的数据足足有20亿之多，可是在实际应用中，hashCode会倾向于集中在某个区域内，这就导致了大量的hashCode重复，这种重复又被称为哈希冲突。

下面的代码介绍了hashCode在HashMap中的作用：

程序的运行结果为：

从上述运行结果可以观察到三个现象：

1）hashCode一致的HS类并没有发生冲突，两个HS对象都被正常的存入了HashMap；

2）hashCode一致，同时equals返回true的对象发生了冲突，第三个HS对象替代了第一个；

3）重写了hashCode使之不一致，同时equals返回true的对象，也没有发生冲突，被正确的存入了HashMap。

这三个现象说明，当且仅当hashCode一致，且equals比对一致的对象，才会被HashMap认为是同一个对象。

这似乎和之前介绍的哈希冲突的概念有些矛盾，下面将通过对HashMap的源码进行分析，以阐述HashMap的实现原理和哈希冲突的解决方案。

需要注意的是，Java8对HashMap做过重大修改，下面将分别解析两种实现的区别。

3.3.2 Java8之前的HashMap

在Java7及之前的版本中，HashMap的底层实现是数组和链表，结构如3-4所示：

HashMap采用Entry数组来存储key-value对，每一个键值对组成了一个Entry实体，Entry类实际上是一个单向的链表结构，它具有Next指针，可以连接下一个Entry实体，以此来解决Hash冲突的问题，因为HashMap是按照key的hash值来计算Entry在HashMap中存储的位置的，如果hash值相同，而key内容不相等，那么就用链表来解决这种hash冲突。

在HashMap中，数据都是以键值对的形式存在的，其键值所对应的hashcode将会作为其在数组里的下标。例如，字符串“1”的hashcode经过计算得到51，那么，在它被作为键值存入HashMap后，table[51]对应的Entry.key就是“1”。

思考一个问题，如果另一个Object对象对应的hashcode也是51，那么它和上面的字符串同时存入HashMap的时候，会怎么处理？

答案是，它会被存入链表里，和之前的字符串同时存在。当需要查找指定对象的时候，会先找到hashcode对应的下标，然后遍历链表，调用对象的equals方法进行比较从而找到对应的对象。

由于数组的查找比链表要快，于是，可以得出一个结论：

尽可能使键值的hashcode分散，这样可以提高HashMap的查询效率。

当添加键值对的时候，如果键值对将要占用的位置不是null，并且size>=threshold，那么会启动HashMap的扩容方法resize(2*table.length)，扩容之后会重新计算一次hash和下标。

扩容resize()主要完成以下工作：

1）根据新的容量，确定新的扩容阈值（threshold）大小。如果当前的容量已经达到了最大容量（1<<30)，那么把threshold设为Integer最大值；反之，则用新计算出来的容量乘以加载因子（loadFactor），计算结果和最大容量+1比较大小，取较小者为新的扩容阈值。

Integer最大值为0x7fffffff，如果threshold被设置为最大整型数，那么它必然大于size，扩容操作不会再次触发。而容量*加载因子得到的是一个小于容量的数（加载因子必须小于1大于0），以它为阈值则说明，加载因子的大小对HashMap影响很大，太小了会导致HashMap频繁扩容，太大了会导致空间的浪费。0.75是Java提供的建议值。

2）重新计算当前所有结点转移到新table数组后的下标。

通过上面的分析可以得出下面的结论：

1）HashMap执行写操作（put）的时候，比较消耗资源的是遍历链表，扩容数组操作；

2）HashMap执行读操作（get）的时候，比较消耗资源的是遍历链表。

影响遍历链表的因素是链表的长度，在HashMap中，链表的长度由哈希碰撞的频率决定。

哈希碰撞的频率受数组长度所决定，长度越长，则碰撞的概率越小，但长度越长，闲置的内存空间越多。所以，扩容数组操作的结果也会影响哈希碰撞的频率，需要在时间和空间上取得一个平衡点。

哈希碰撞的频率又受key值的hashCode()方法影响，所计算得出的hashCode的独特性越高，哈希碰撞的概率也会变低。

链表的遍历中，需要调用key值的equals方法，不合理的equals实现会导致HashMap效率低下甚至调用异常。

因此，要提高HashMap的使用效率，可以从以下几个方面入手：

1）根据实际的业务需求，测试出合理的loadFactor，否则会始终使用Java建议的0.75；

2）合理的重写键值对象的hashCode和equals方法，equals和hashCode方法的主要特性见表3-1，可以参考《Effective Java中文版》一书中的建议。

3.3.3 Java8提供的HashMap

Java8的HashMap数据结构发生了较大的变化，之前的HashMap使用的数组+链表来实现，新的HashMap里，虽然依然使用的是table数组，但是数据类型发生了变化：Java8里的HashMap使用的是数组+树+链表的结构。如图3-5所示（R表示红色，B表示黑色）：

在添加链表结点后，如果链表深度达到或超过建树阈值（TREEIFY_THRESHOLD-1)，那么会把整个链表重构为树。注意，TREEIFY_THRESHOLD是一个常量，值固定为8。也就是说，当链表长度达到7的时候，会转化为树结构，为什么要这样设计？该树是一棵红黑树，由于链表的查找的时间复杂度是O(n)，而红黑树的查找的时间复杂度是O(log2n)的，数值太小的时候，它们的查找效率相差无几，Java8认为7是一个合适的阈值，因此这个值被用来决定是否要从链表结构转化为树结构。

综上所述，HashMap采用hash算法来决定Map中key的存储，hash表里可以存储元素的位置称为桶，如果通过key计算hash值发生冲突时，那么将采用链表（或树）的形式来存储元素。HashMap的扩容操作是一项很耗时的任务，所以如果能估算Map的容量，最好给它一个默认初始值，避免进行多次扩容。HashMap的线程是不安全的，多线程环境中推荐使用ConcurrentHashMap。

3.3.4 TreeMap

与HashMap组合了数组、链表和红黑树相比，TreeMap是完全由红黑树实现的。HashMap通过hashcode对其内容进行快速查找，而TreeMap中所有的元素都保持着某种固定的顺序，当需要得到一个有序的结果的时候就应该使用TreeMap。下面将简要介绍一下TreeMap的实现原理。

（1）成员变量

TreeMap的主要成员变量包括：

（2）构造方法

TreeMap有四个构造方法：

1）public TreeMap()。无参构造，初始化comparator=null；

2）public TreeMap(Comparator<? super K>comparator)。比较器构造，使用外部传入的比较器；

3）public TreeMap(Map<? extends K, ? extends V>m)。使用传入的Map初始化TreeMap的内容；

4）public TreeMap(SortedMap<K, ? extends V>m)。使用SortedMap初始化TreeMap内容，同时使用SortedMap的比较器来初始化TreeMap比较器。

（3）put方法

put的实现思路非常清晰：

1）如果TreeMap是空的，那么使用指定数据作为根结点；

2）反之，如果comparetor不为空，那么使用comparetor来决定插入位置；如果comparetor为空，那么认为key值实现了Comparable，直接调用compareTo方法来决定插入位置；如果key没有实现Comparable，那么抛出ClassCastException；

3）插入完成后，修复红黑树。

TreeMap的使用示例代码如下：

程序运行结果为：

3.3.5 LinkedhashMap

通过上面的讲解可以看出HashMap中存储元素的位置是根据hashcode来决定的，以此数据的存储是无序的，也就是说迭代HashMap的顺序并不是HashMap放置的顺序。显然，在需要保持顺序的场景中HashMap就不可用了。LinkedHashMap的出现恰好可以解决这个顺序的问题，它虽然增加了时间和空间上的开销，但是通过维护一个额外双向链表，LinkedHashMap保证了元素迭代的顺序。该迭代顺序可以是插入顺序或者是访问顺序。下面简要地介绍它的内部实现原理。

3.3.6 Java8之前的LinkedHashMap

（1）成员变量

除了与HashMap类似的部分实现外，LinkedHashMap有以下两个需要特别注意的成员变量：

LinkedHashMap的存储中包含了一个额外的双向链表结构，header既是头又是尾，可以视作一个环状链表，但它本身只是个表头标记，不包含数据域。其结构如图所示3-6所示。

由图3-6可知，LinkedHashMap可以像HashMap一样的使用，同时它为每个数据结点的引用多维护了一份链表，从而可以达到有序访问的目的。

（2）createEntry(hash,key,value,index)方法

LinkedHashMap和HashMap的第一个主要区别体现在createEntry方法上。

HashMap的createEntry执行的是创建Hash桶里的链表结点，代码如下所示：

LinkedHashMap的createEntry除了完成HashMap的功能外，还把该链表结点的引用插入到了header环形链表里，实现源码如下所示：

（3）如何使用LinkedHashMap

查阅LinkedHashMap的API，可以注意到LinkedHashMap没有提供新的公开方法。那么，它的链表特性怎么体现呢？

参考下面三种方法：

这三种方法分别提供给keySet()、values()和entrySet()使用。

LinkedHashMap通过对这三种方法进行重写使上述三种方法产生的集合可以按照插入顺序排列。

3.3.7 Java8中的LinkedHashMap

关键变量有以下三个：

与历史版本的LinkedHashMap的实现方法不同，head和tail分别维护在了两个引用里，这让LinkedHashMap的结构发生了变化，实现原理如图3-7所示。

由图3-7可以发现，LinkedHashMap新版本的实现与HashMap新版本的实现类似，也是采用了链表与二叉树组合的方式来实现。原理上与历史版本的LinkedHashMap并没有区别。

（1）linkNodeLast方法

newNode方法与newTreeNode方法源自HashMap，是用来新建结点的。在LinkedHashMap中，重写了这两个方法，负责在创建结点的同时插入链表，实现了保存数据结点副本到双向链表里的功能。

在这两个方法的实现中，关键实现是对linkNodeLast方法的调用。

linkNodeLast方法源码如下所示，参数p为新创建的结点：

（2）transferLinks方法

replacementNode方法和replacementTreeNode方法负责替换指定结点，对这两个方法的重写保证了在结点替换时，同时维护好它们在双向链表里的原始插入顺序。

在LinkedHashMap里，它们会额外调用transferLinks方法。该方法源码如下所示：

（3）如何使用LinkedHashMap

得益于Java8的Function包的引入，从Java8开始，LinkedHashMap有了更方便的使用方式，以下是forEach和replaceAll方法源码：

对LinkedHashMap的遍历可以采用更简便的方法实现，示例代码如下所示：

运行结果为：

常见面试笔试真题：

如何用LinkedHashMap实现LRU？

答案：LRU是Least Recently Used的缩写，表示最近最少使用，它是一种缓存策略。当缓存有大小限制而数据量比较大的时候，就无法把所有数据都放在缓存中，因此就需要一种策略来把缓存中的部分数据置换出去。LRU就是其中的一种思路，其主要思路为：

1）新访问的数据插入到缓存队列中；

2）当有新数据要加入到缓存中，但是缓存已满，这时候就淘汰队尾数据；

3）如果缓存中的数据被再次访问，则将数据移到队列首。

LinkedHashMap自身已经实现了顺序存储，而且通过Hash的方法把数据分配到不同的槽中，从而提高了访问效率。正常情况下是按照元素的添加顺序存储，当然也可以指定按照访问的顺序来存储，最近被访问的数据会放在最前面，而且LinkedHashMap还有一个判断是否删除最老数据的方法，默认是返回false，表示不删除数据，可以通过重写这个方法来修改删除策略。下面首先介绍为了实现LRU而需要使用到的两种重要的方法：

从这两个方法的描述可以看出，要通过LinkedHashMap实现LRU，只需要做到下面两点：

1）使用构造方法的时候，第三个参数指定true表示按照访问顺序存储；

2）重写removeEldestEntry方法使得当Map达到LRU的容量的时候返回true从而能删除最老的数据。

示例代码如下：

程序运行结果为：

3.3.8 Hashtable

Hashtable的实现与HashMap很类似，Java8的Hashtable稍有不同，但整体流程是没有变化的。

Hashtable的put过程大致如下所示：

1）计算key值的hashcode；

2）根据hashcode计算下标；

3）如果存在hashcode和key值完全相等的value，那么替换它并返回；

4）反之，如果总数据数超出了扩容阈值，那么对数组扩容，并重新计算所有的数据结点的下标；

5）为新数据创建新结点。

可以看出，Hashtable和HashMap基本put流程是一致的，那么它们的区别在哪里？

下面以put方法为例来介绍Hashtable的实现源码如下所示：

作为对比，看看HashMap的put实现：

从源码可以看出Hashtable的实现方式被synchronized修饰，由此可见Hashtable是线程安全的，而HashMap是线程不安全的；此外Hashtable不能存放null作为key值，HashMap会把null key存放在下标0位置。

虽然Hashtable是“线程安全”的，但在多线程环境下并不推荐使用。因为采用synchronized方式实现的多线程安全的容器在高并发量的情况下效率比较低，Java还引入了专门在高并发量的情况下使用的并发容器，这种容器由于在实现的时候采用了更加细粒度的锁，由此在高并发量的情况下有着更好的性能。在后面的章节中，将会对部分并发容器的详细解析。

3.3.9 WeakHashMap

WeakHashMap是一种弱引用的HashMap，弱引用指的是WeakHashMap中的key值如果没有外部强引用，那么在垃圾回收的时候，WeakHashMap的对应内容也会被移除掉。

在讲解WeakHashMap之前，需要了解Java中与引用相关的类：

ReferenceQueue（引用队列），与某个引用类绑定，当引用死亡后，会进入这个队列。

HardReference（强引用），任何以类似String str=new String()建立起来的引用，都是强引用。在str指向另一个对象或者null之前，该String对象都不会被GC（Garbage Collector垃圾回收器）回收；

WeakReference（弱引用），可以通过java.lang.ref.WeakReference来建立弱引用，当GC要求回收对象时，它不会阻止对象被回收，也就是说即使有弱引用存在，该对象也会立刻被回收；

SoftReference（软引用），可以通过java.lang.ref.SoftReference来建立，与弱引用类似，当GC要求回收时，它不会阻止对象被回收，但不同的是它对回收过程会被延迟，必须要等到JVM heap内存不够用，接近产生OutOfMemory错误时，才会被回收；

PhantomReference（虚引用），可以通过java.lang.ref.PhantomPeference来建立，这种类型的引用很特别，在大多数时间里，无法通过它拿到其引用的对象，但是，当这个对象消失的时候，该引用还是会进入ReferenceQueue队列。

下面提供一个例子来分别说明它们的作用：

在这个例子里，分别创建了弱引用、虚引用和软引用，get()方法用于获取它们引用的Ref对象，可以注意到，Ref对象在外部并没有任何引用，所以，在某个时间点，GC应当会回收对象。来看看代码执行的结果：

可以看到，弱引用和软引用的对象还是可达的，但是虚引用是不可达的。被回收的引用没有内容，说明GC还没有回收它们。

这证实了虚引用的性质：虚引用非常弱，以至于它自己也找不到自己的引用内容。

对之前的代码进行修改，在输出内容前加入代码：

再执行一次，得到结果：

现在可达的引用只剩下Soft了，引用队列里多出了两个引用，说明WeakReference和PhantomReference的对象被回收。

再修改一次代码，让WeakPeference和PhantomReference去引用一个强引用对象：

输出结果如下所示：

这证实了弱引用的性质：弱引用的对象，如果没有被强引用，那么在垃圾回收后，引用对象会不可达。

WeakHashMap的实现方式

WeakHashMap利用了ReferenceQueue和WeakReference来实现它的核心功能：当key值没有强引用的时候，会从WeakHashMap里移除。

在源码实现中，WeakHashMap维护了一个ReferenceQueue，保存了所有存在引用的Key对象。WeakHashMap.Entry<K,V>中并没有保存Key，只是将Key与ReferenceQueue进行了关联。

下面首先介绍WeakHashMap的键值对实体类WeakHashMap.Entry的实现：

对于这个类有以下两个需要注意的方面：

1）Entry继承自WeakReference；

2）Entry本身没有保存key值，而是把key直接交给了父类WeakReference来构造。

参考通常的WeakReference，Entry的key值是一个弱引用，只能通过WeakHashMap#get来获取。获取代码如下所示：

WeakHashMap实现清除无强引用实体的方法是expungStaleEntries()，它会将ReferenceQueue中所有失效的引用从Map中去除。其源码实现如下所示：

这个去除操作的主要原理为：当WeakHashMap中的某个弱引用被GC回收时，被回收的这个弱引用会被添加到WeakHashMap维护了的ReferenceQueue（queue）中。因此，当expungeStaleEntries方法被调用的时候，就可以遍历queue中所有的key，然后在WeakReference的table中找到与key对应的键值对并从table中删除。

expungStaleEntries()方法会在resize、put、get、forEach方法中被调用。

3.3.10 HashMap、HashTable、TreeMap和WeakHashMap的区别

Java为数据结构中的映射定义了一个接口java.util.Map，它有三个主要的实现类：HashMap、Hashtable和TreeMap。Map是用来存储键值对的数据结构，在数组中通过数组下标来对其内容索引的，而在Map中，则是通过对象来进行索引，用来索引的对象称为key，其对应的对象称为value。

HashMap是一个最常用的Map，它根据键的hashCode值存储数据，根据键可以直接获取它的值，具有很快的访问速度。由于HashMap与HashTable都采用了hash方法进行索引，因此二者具有许多相似之处，它们主要有如下的一些区别：

1）HashMap是Hashtable的轻量级实现（非线程安全的实现），它们都完成了Map接口，主要区别在于HashMap允许空（null）键值（key）（但需要注意，最多只允许一条记录的键为null，不允许多条记录的值为null），而Hashtable不允许。

2）HashMap把Hashtable的contains方法去掉了，改成containsvalue和containsKey。因为contains方法容易让人引起误解。Hashtable继承自Dictionary类，而HashMap是Java1.2引进的Map interface的一个实现。

3）Hashtable的方法是线程安全的，而HashMap由于不支持线程的同步，所以它不是线程安全的。在多个线程访问Hashtable时，不需要开发人员对它进行同步，而对于HashMap，开发人员必须提供额外的同步机制。所以，效率上HashMap可能高于Hashtable。

4）HashTable使用Enumeration，HashMap使用Iterator。

5）Hashtable和HashMap采用的hash/rehash算法都几乎一样，所以性能上不会有很大的差异。

6）HashTable中hash数组默认大小是11，增加的方式是old*2+1。在HashMap中，hash数组的默认大小是16，而且一定是2的指数。

7）hash值的使用不同，HashTable直接使用对象的hashCode，而HashMap则在key的hashCode基础上重写计算了一个新的hash值。

以上三种类型中，使用最多的是HashMap。HashMap里面存入的键值对在取出的时候没有固定的顺序，是随机的。一般而言，在Map中插入、删除和定位元素，HashMap是最好的选择。由于TreeMap实现了SortMap接口，能够把它保存的记录按照键排序，所以，取出来的是排序后的键值对，如果需要按自然顺序或自定义顺序遍历键，那么TreeMap会更好。LinkedHashMap是HashMap的一个子类，如果需要输出的顺序和输入的相同，那么用LinkedHashMap可以实现，它还可以按读取顺序来排列。

WeakHashMap与HashMap类似，不同之处在于WeakHashMap中key采用的是“弱引用”的方式，只要WeakHashMap中的key不再被外部引用，它就可以被垃圾回收器回收。而HashMap中key采用的是“强引用的方式”，当HashMap中的key没有被外部引用时，只有在这个key从HashMap中删除后，才可以被垃圾回收器回收。

3.3.11 用自定义类型作为HashMap或Hashtable的key需要注意的问题

HashMap与Hashtble是用来存放键值对的一种容器，在使用这两个容器的时候有个限制：不能用来存储重复的键，也就是说每个键只能唯一映射一个值，当有重复的键出现，则不会创建新的映射关系，而会使用先前的键。示例代码如下。

程序运行结果为：

从上面的例子可以看出，首先向HashMap中添加<"aaa", "bbb">，接着添加<"aaa", "ccc">的时候由于与前面已经添加的数据有相同的key："aaa"，因此会用新的值"ccc"替换"bbb"。

但是当用自定义的类的对象作为HashMap的key的时候，有时候会造成一种假象：key是可以重复的。如下例所示。

程序运行结果为：

从表面上看，向HashMap中添加的两个键值对的key值是相同的，可是为什么在后面添加的键值对没有覆盖前面的value呢？为了说明这个问题，下面首先介绍HashMap添加元素的操作过程。具体而言，在向HashMap中添加键值对<key，value>的时候，需要经过如下几个步骤：首先，调用key的hashCode()方法生成一个哈希值h1，如果这个h1在HashMap中不存在，那么直接将<key，value>添加到HashMap中，如果这个h1已经存在，那么找出HashMap中所有哈希值为h1的key，然后分别调用key的equls()方法判断当前添加的key值是否与已经存在的key值相同，如果equals()方法返回true，说明当前需要添加的key已经存在，那么HashMap会使用新的value值来覆盖掉旧的value值。如果equals()方法返回false，说明新增加的key在HashMap中不存在，因此会在HashMap中创建新的映射关系。当新增加的key的hash值已经在HashMap中存在的时候，就会产生冲突。一般而言，对于不同的key值可能会得到相同的hash值，因此就需要对冲突进行处理。一般而言，处理冲突的方法有开放地址法、再哈希法、链地址法等。HashMap使用的是链地址法来解决冲突（为了容易理解，这里以Java8之前的实现方式为例），具体操作方法如图3-8（一）所示。

向HashMap中添加元素时，当有冲突产生的时候，其实现方式如图3-9（二）所示：

从HashMap中通过key查找value的时候，首先调用的是key的hashCode()方法来获取到key对应的hash值h，这样就可以确定键为key的所有值存储的首地址。如果h对应的key值有多个，那么程序接着会遍历所有的key，通过调用key的equals()方法来判断key的内容是否相等。只有当equals()方法的返回值为true时，对应的value才是正确的结果。

在上例中，由于使用自定义的类作为HashMap的key，而没有重写hashCode()方法和equals()方法，默认使用的是Object类的hashCode()方法和equals()方法。Object类的equals()方法的比较规则为：当参数obj引用的对象与当前对象为同一个对象时，就返回true，否则返回false。hashCode()方法会返回对象存储的内存地址。由于在上例中创建了两个对象，虽然它们拥有相同的内容，但是存储在内存中不同的地址，因此在向HashMap中添加对象的时候，调用equals()方法的返回值为false，HashMap会认为它们是两个不同的对象，会分别创建不同的映射关系。因此为了实现在向HashMap中添加键值对的时候，可以根据对象的内容来判断两个对象是否相等，就需要重写hashCode()方法和equals()方法。如下例所示。

程序输出结果为：

由此可以看出，在使用自定义类作为HashMap的key的时候需要注意以下几个问题：

1）如果想根据对象的相关属性来自定义对象是否相等的逻辑，此时就需要重写equals()方法，一旦重写了equals()方法，那么就必须重写hashCode()方法。

2）当自定义类想作为HashMap(HashTable)的key时，最好把这个类设计为不可变类。

3）从hashMap的工作原理可以看出，如果两个对象相等，那么这两个对象有着相同的hashCode。反之则不成立。

3.3.12 ConcurrentHashMap

ConcurrentHashMap是HashMap中支持高并发、高吞吐量的线程安全的版本。它由Segment数组结构和HashEntry数组结构组成。Segment在ConcurrentHashMap里扮演锁的角色，HashEntry则用于存储键值对数据。一个ConcurrentHashMap里包含一个Segment数组，Segment的结构和HashMap类似，是一种数组和链表结构，一个Segment里包含一个HashEntry数组，每个HashEntry是一个链表结构的元素，每个Segment守护着一个HashEntry数组里的元素，当对HashEntry数组的数据进行修改时，必须首先获得它对应的Segment锁。

Hashtable和ConcurrentHashMap存储的内容为键值对（key-value），且它们都是线程安全的容器，下面通过简要介绍它们的实现方式来对比它们的不同点。

Hashtable所有的方法都是同步的，因此，它是线程安全的。它的定义如下所示：

Hashtable是通过“拉链法”实现的哈希表，因此，它使用数组+链表（或链表+二叉树）的方式来存储实际的元素。这里以“数组+链表”的实现方式为例，如图3-10所示。

在图3-10中，最顶部标数字的部分是一个Entry数组，而Entry又是一个链表。当向Hashtable中插入数据的时候，首先通过键的hashcode和Entry数组的长度来计算这个值应该存放在数组中的位置index，如果index对应的位置没有存放值，那么直接存放到数组的index位置即可，当index有冲突的时候，则采用“拉链法”来解决冲突。假如想往Hashtable中插入"aaa"、"bbb"、"eee"、"fff"，如果"aaa"和"fff"所得到的index是相同的，那么插入后Hashtable的结构如图3-11所示。

Hashtable的实现类图如图3-12所示。

为了使Hashtable拥有比较好的性能，数组的大小也需要根据实际插入数据的多少来进行动态地调整，Hashtable类中定义了一个rehash方法，该方法可以用来动态地扩充Hashtable的容量，该方法被调用的时机为：Hashtable中的键值对超过某一阀值。默认情况下，该阀值等于Hashtable中Entry数组的长度*0.75。Hashtable默认的大小为11，当达到阀值后，每次按照下面的公式对容量进行扩充：newCapacity=oldCapacity*2+1。

Hashtable通过使用synchronized修饰方法的方式来实现多线程同步，因此，Hashtable的同步会锁住整个数组，在高并发的情况下，性能会非常差，Java5中引入java.util.concurrent.ConcurrentHashMap作为高吞吐量的线程安全HashMap实现，它采用了锁分离的技术允许多个修改操作并发进行。它们在多线程锁的使用方式如图3-13和图3-14所示。

ConcurrentHashMap采用了更细粒度的锁来提高在高并发情况下的效率。ConcurrentHashMap将Hash表默认分为16个桶（每一个桶可以被看作是一个Hashtable），大部分操作都没有用到锁，而对应的put、remove等操作也只需要锁住当前线程需要用到的桶，而不需要锁住整个数据。采用这种设计方式以后，在高并发的情况下，同时可以有16个线程来访问数据。显然，大大提高了并发性。

只有个别方法（例如：size()方法和containsValue()方法）可能需要锁定整个表而不仅仅是某个桶，在实现的时候，需要“按顺序”锁定所有桶，操作完毕后，又“按顺序”释放所有桶，“按顺序”的好处是能防止死锁的发生。

假设一个线程在读取数据的时候，另外一个线程在Hash链的中间添加或删除元素或者修改某一个结点的值，此时必定会读取到不一致的数据。那么如何才能实现在读取的时候不加锁却又不会读取到不一致的数据呢？ConcurrentHashMap使用不变量的方式实现，它通过把Hash链中的结点HashEntry设计成几乎不可变的方式来实现，HashEntry的定义如下所示：

从以上这个定义可以看出，除了变量value以外，其他变量都被定义为final类型。因此，增加结点（put方法）的操作只能在Hash链的头部增加。对于删除操作，则无法直接从Hash链的中间删除结点，因为next也被定义为不可变量。因此，remove操作的实现方式如下所示：把需要删除的结点前面所有的结点都复制一遍，然后把复制后的Hash链的最后一个结点指向待删除结点的后继结点，由此可以看出，ConcurrentHashMap删除操作是比较耗时的。此外，使用volatile修饰value的方式使这个值被修改后对所有线程都可见（编译器不会进行优化），采用这种方式的好处如下所示：一方面，避免了加锁；另一方面，如果把value也设计为不可变量（用final修饰），那么每次修改value的操作都必须删除已有结点，然后插入新的结点，显然，此时的效率会非常低下。

由于volatile只能保证变量所有的写操作都能立即反映到其他线程之中，也就是说volatile变量在各个线程中是一致的，但是由于volatile不能保证操作的原子性，因此它不是线程安全的。如下例所示：

程序的运行结果如下。

从上述运行结果可以看出，单线程运行的时候map.put(1, map.get(1) + 1);会被执行100次，因此运行结果是100。当使用多线程运行的时候，在上述代码中使用了5个线程，也就是说map.put(1, map.get(1)+1);会被调用500次，如果这个容器是多线程安全的，那么运行结果应该是500，但是实际的运行结果并不都是500。说明在ConcurrentHashMap在某种情况下还是线程不安全的，这个例子中导致线程不安全的主要原因为：

map.put(1, map.get(1)+1);不是一个原子操作，而是包含了下面三个操作：

1）map.get(1)；这一步是原子操作，由CocurrentHashMap来保证线程安全；

2）+1操作；

3）map.put操作。这一步也是原子操作，由CocurrentHashMap来保证线程安全。

假设map中的值为<1,5>。线程1在执行map.put(1, map.get(1) + 1)的时候首先通过get操作读取到map中的值为5，此时线程2也在执行map.put(1, map.get(1) + 1)，从map中读取到的值也是5，接着线程1执行+1操作，然后把运算结果通过put操作放入map中，此时map中的值为<1,6>；接着线程2执行+1操作，然后把运算结果通过put操作放入map中，此时map中的值还是<1,6>。由此可以看出，两个线程分别执行了一次map.put(1, map.get(1)+1)，map中的值却值增加了1。

因此在访问ConcurrentHashMap中value的时候，为了保证多线程安全，最好使用一些原子操作。如果要使用类似map.put(1, map.get(1)+1)的非原子操作，那么需要通过加锁来实现多线程安全。

在上例中，为了保证多线程安全，可以把run方法改为：