Java集合学习（十四） Map总结

Java集合学习（十四） Map总结2014-08-03Map总结（HashMap, Hashtable, TreeMap, WeakHashMap等使用场景）

学完了Map的全部内容，我们再回头开开Map的框架图。

第1部分 Map概括

Map 是“键值对”映射的抽象接口。 AbstractMap 实现了Map中的绝大部分函数接口。它减少了“Map的实现类”的重复编码。 SortedMap 有序的“键值对”映射接口。 NavigableMap 是继承于SortedMap的，支持导航函数的接口。 HashMap, Hashtable, TreeMap, WeakHashMap这4个类是“键值对”映射的实现类。它们各有区别！

HashMap 是基于“拉链法”实现的散列表。一般用于单线程程序中。 Hashtable 也是基于“拉链法”实现的散列表。它一般用于多线程程序中。 WeakHashMap 也是基于“拉链法”实现的散列表，它一般也用于单线程程序中。相比HashMap，WeakHashMap中的键是“弱键”，当“弱键”被GC回收时，它对应的键值对也会被从WeakHashMap中删除；而HashMap中的键是强键。 TreeMap 是有序的散列表，它是通过红黑树实现的。它一般用于单线程中存储有序的映射。

第2部分 HashMap和Hashtable异同

第2.1部分 HashMap和Hashtable的相同点

HashMap和Hashtable都是存储“键值对（key-value）”的散列表，而且都是采用拉链法实现的。存储的思想都是：通过table数组存储，数组的每一个元素都是一个Entry；而一个Entry就是一个单向链表，Entry链表中的每一个节点就保存了key-value键值对数据。

添加key-value键值对：首先，根据key值计算出哈希值，再计算出数组索引（即，该key-value在table中的索引）。然后，根据数组索引找到Entry（即，单向链表），再遍历单向链表，将key和链表中的每一个节点的key进行对比。若key已经存在Entry链表中，则用该value值取代旧的value值；若key不存在Entry链表中，则新建一个key-value节点，并将该节点插入Entry链表的表头位置。删除key-value键值对：删除键值对，相比于“添加键值对”来说，简单很多。首先，还是根据key计算出哈希值，再计算出数组索引（即，该key-value在table中的索引）。然后，根据索引找出Entry（即，单向链表）。若节点key-value存在与链表Entry中，则删除链表中的节点即可。

上面介绍了HashMap和Hashtable的相同点。正是由于它们都是散列表，我们关注更多的是“它们的区别，以及它们分别适合在什么情况下使用”。那接下来，我们先看看它们的区别。

第2.2部分 HashMap和Hashtable的不同点

1 继承和实现方式不同

HashMap 继承于AbstractMap，实现了Map、Cloneable、java.io.Serializable接口。 Hashtable 继承于Dictionary，实现了Map、Cloneable、java.io.Serializable接口。

HashMap的定义:

publicclass HashMap<K,V>extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable { ... }

Hashtable的定义:

publicclass Hashtable<K,V>extends Dictionary<K,V>implements Map<K,V>, Cloneable, java.io.Serializable { ... }

从中，我们可以看出： 1.1 HashMap和Hashtable都实现了Map、Cloneable、java.io.Serializable接口。实现了Map接口，意味着它们都支持key-value键值对操作。支持“添加key-value键值对”、“获取key”、“获取value”、“获取map大小”、“清空map”等基本的key-value键值对操作。实现了Cloneable接口，意味着它能被克隆。实现了java.io.Serializable接口，意味着它们支持序列化，能通过序列化去传输。

1.2 HashMap继承于AbstractMap，而Hashtable继承于Dictionary Dictionary是一个抽象类，它直接继承于Object类，没有实现任何接口。Dictionary类是JDK 1.0的引入的。虽然Dictionary也支持“添加key-value键值对”、“获取value”、“获取大小”等基本操作，但它的API函数比Map少；而且 Dictionary一般是通过Enumeration（枚举类）去遍历，Map则是通过Iterator（迭代器）去遍历。然而‘由于Hashtable也实现了Map接口，所以，它即支持Enumeration遍历，也支持Iterator遍历。关于这点，后面还会进一步说明。 AbstractMap是一个抽象类，它实现了Map接口的绝大部分API函数；为Map的具体实现类提供了极大的便利。它是JDK 1.2新增的类。

2 线程安全不同

Hashtable的几乎所有函数都是同步的，即它是线程安全的，支持多线程。而HashMap的函数则是非同步的，它不是线程安全的。若要在多线程中使用HashMap，需要我们额外的进行同步处理。对HashMap的同步处理可以使用Collections类提供的synchronizedMap静态方法，或者直接使用JDK 5.0之后提供的java.util.concurrent包里的ConcurrentHashMap类。

3 对null值的处理不同

HashMap的key、value都可以为null。 Hashtable的key、value都不可以为null。

我们先看看HashMap和Hashtable “添加key-value”的方法

HashMap的添加key-value的方法

// 将“key-value”添加到HashMap中public V put（K key, V value） {// 若“key为null”，则将该键值对添加到table[0]中。if （key == null）return putForNullKey（value）;// 若“key不为null”，则计算该key的哈希值，然后将其添加到该哈希值对应的链表中。int hash = hash（key.hashCode（））;int i = indexFor（hash, table.length）;for （Entry<K,V> e = table[i]; e ！= null; e = e.next） {Object k;// 若“该key”对应的键值对已经存在，则用新的value取代旧的value。然后退出！if （e.hash == hash && （（k = e.key） == key || key.equals（k））） {V oldValue = e.value;e.value = value;e.recordAccess（this）;return oldValue;}} // 若“该key”对应的键值对不存在，则将“key-value”添加到table中modCount++;addEntry（hash, key, value, i）;return null;} // putForNullKey（）的作用是将“key为null”键值对添加到table[0]位置private V putForNullKey（V value） {for （Entry<K,V> e = table[0]; e ！= null; e = e.next） {if （e.key == null） {V oldValue = e.value;e.value = value;// recordAccess（）函数什么也没有做e.recordAccess（this）;return oldValue;}}// 添加第1个“key为null”的元素都table中的时候，会执行到这里。// 它的作用是将“设置table[0]的key为null，值为value”。modCount++;addEntry（0, null, value, 0）;return null;}

Hashtable的添加key-value的方法

// 将“key-value”添加到Hashtable中public synchronized V put（K key, V value） {// Hashtable中不能插入value为null的元素！！！if （value == null） {throw new NullPointerException（）;} // 若“Hashtable中已存在键为key的键值对”，// 则用“新的value”替换“旧的value”Entry tab[] = table;// Hashtable中不能插入key为null的元素！！！// 否则，下面的语句会抛出异常！int hash = key.hashCode（）;int index = （hash & 0x7FFFFFFF） % tab.length;for （Entry<K,V> e = tab[index] ; e ！= null ; e = e.next） {if （（e.hash == hash） && e.key.equals（key）） {V old = e.value;e.value = value;return old;}} // 若“Hashtable中不存在键为key的键值对”，// （01） 将“修改统计数”+1modCount++;// （02） 若“Hashtable实际容量” > “阈值”（阈值=总的容量 * 加载因子）//则调整Hashtable的大小if （count >= threshold） {// Rehash the table if the threshold is exceededrehash（）; tab = table;index = （hash & 0x7FFFFFFF） % tab.length;} // （03） 将“Hashtable中index”位置的Entry（链表）保存到e中 Entry<K,V> e = tab[index];// （04） 创建“新的Entry节点”，并将“新的Entry”插入“Hashtable的index位置”，并设置e为“新的Entry”的下一个元素（即“新Entry”为链表表头）。tab[index] = new Entry<K,V>（hash, key, value, e）;// （05） 将“Hashtable的实际容量”+1count++;return null;}

根据上面的代码，我们可以看出：