【总结】Java基础之Map：HashMap vs. LinkedHashMap vs. TreeMap vs. ConcurrentHashMap

Map是Java最常用的集合类之一。它有很多实现类，我总结了几种常用的Map实现类，如下图所示。本篇文章重点总结几个Map实现类的特点和区别：



特点总结：

实现类	HashMap	LinkedHashMap	TreeMap	Hashtable	ConcurrentHashMap
允许key/value为空	允许为空	允许为空	允许为空	不允许为空	不允许为空
线程安全	不安全	不安全	不安全	安全（全部锁）	安全（部分锁）
排序	无序	迭代器顺序	红黑树顺序（可以自定义）	无序	无序

1、HashMap: Map最常用的实现类
a、HashMap可以存空的key和空的value。

public void nullKeyTest() {
	Map<String, Object> map = new HashMap<String, Object>();
	map.put(null, "value");
	System.out.println(map); // {null=value}
}

public void nullValueTest() {
	Map<String, Object> map = new HashMap<String, Object>();
	map.put("key", null);
	System.out.println(map); // {key=null}
}

b、HashMap线程不安全，在多线程的情况下，需要额外方法实现数据的同步。Collections提供了同步的方法，如下：返回了一个线程安全的HashMap类。（PS：这时候可以考虑ConcurrentHashMap，下文有介绍）。

	public void synchMapTest() {
		Map<String,Object> map = Collections.synchronizedMap(new HashMap<String,Object>());
		// returned a synchoronized HashMap
	}

2、LinkedHashMap: HashMap子类
a、LinkedHashMap作为HashMap的子类，同样也可以存空的key和空的value。

b、LinkedHashMap会按存入顺序存放元素（迭代器顺序）。
现实中很多情况下都可以使用LinkedHashMap，例如购物车的实现：按用户添加的时间顺序显示购物车中的元素。
以下map的输出是有顺序的，而map1是无序的。

public void iterateOrderTest() {
	Map<String, Object> map = new LinkedHashMap<String, Object>();
	map.put("ccc", "value");
	map.put("bbb", "value");
	map.put("aaa", "value");
	System.out.println(map); // {ccc=value, bbb=value, aaa=value}
		
	Map<String, Object> map1 = new HashMap<String, Object>();
	map1.put("ccc", "value");
	map1.put("bbb", "value");
	map1.put("aaa", "value");
	System.out.println(map1); // {aaa=value, ccc=value, bbb=value}
}

c、LinkedHashMap有个方法叫：removeEldestEntry(Map.Entry) ，用户可以重写该方法来制定添加元素时的策略。方法内部返回true时，当要往该map中存放（put\putAll）元素时，就先删除最老的对象，然后再添加新对象。使用实例：在设计Cache（缓存）时，可以重写该方法来制定键值的过期规则。
API：http://docs.oracle.com/javase/6/docs/api/java/util/LinkedHashMap.html#removeEldestEntry(java.util.Map.Entry)
例子：在新建一个LinkedHashMap对象时，重写了其removeEldestEntry方法，如果map的容易大于2时，就返回true，于是最老的键aaa就被删除了。

public void removeEldestEntryTest() {
	Map<String, Object> map = new LinkedHashMap<String, Object>() {
		private int MAX_ENTRIES = 2;
		protected boolean removeEldestEntry(Map.Entry<String, Object> eldest) {
		        return size() > MAX_ENTRIES;
		}
	};

	map.put("aaa", "value");
	map.put("bbb", "value");
	map.put("ccc", "value");
	System.out.println(map); // {bbb=value, ccc=value}
}

所以如果不是为了键值的顺序，还是使用HashMap最好，因为LinkedHashMap需要额外的空间去维护键值之间的链表关系。

3、Hashtable类
Hashtable是JDK1.0就有的，算是很古老的Map实现了，前辈们设计的初衷就是为了线程安全考虑的（有点类似List里的一个实现类，叫Vector）。
另外就是Hashtable不能存放空的key/value，会报java.lang.NullPointerException错误。
值得一提的是，现在很少会用到Hashtable类，如果要在多线程的情况下使用线程安全类，那会考虑ConcurrentHashMap，下文有介绍。

4、SortedMap的实现类：TreeMap
TreeMap红黑树的一个实现。其键值按照自然顺序排序的。它的构造函数中提供了参数Comparator，可以自定义实现排序。
另外，TreeMap也是线程不安全的。

构造器API：

TreeMap(Comparator<? super K> comparator) 
// 返回一个空的tree map，按传入的comparator规则进行排序。

排序的例子：

public void orderTest() {
    Map<String, String> treeMap = new TreeMap<String, String>();
    treeMap.put("aaa", "value1");
    treeMap.put("bbb", "value2");
    treeMap.put("ccc", "value3");
    System.out.println(treeMap); // {aaa=value1, bbb=value2, ccc=value3}
}

// 自定义排序器：按键值的倒序排序：  
public void comparatorTest() {
    Map<String,String> treeMap1 = new TreeMap<String,String>(new Comparator<String>(){
    public int compare(String o1, String o2) {
            return -o1.compareTo(o2);  
        }
    });
    treeMap1.put("aaa", "value1");
    treeMap1.put("bbb", "value2");
    treeMap1.put("ccc", "value3");
    System.out.println(treeMap1); // {ccc=value3, bbb=value2, aaa=value1}
}

5、ConcurrentMap的实现类：ConcurrentHashMap
ConcurrentHashMap是1.5版本引进的。Concurrent的意思是同时发生的，所以这个实现类的重点是线程安全。（有点类似于Hashtable，但也有区别）。
ConcurrentHashMap的默认并发级别是16。
ConcurrentHashMap的设计初衷是优化线程安全中的读操作，ConcurrentHashMap在取元素的操作（包括get）通常没有加锁，而对于另外一个线程安全的Hashtable来说，是所有方法都加同步锁的。
一般来说，在JAVA1.5版本以后，推荐使用的是ConcurrentHashMap，而Hashtable有点像是历史遗留的类而已。

以下是国外的一篇文章中摘录的ConcurrentHashMap和Hashtable的性能对比：

Threads	ConcurrentHashMap	Hashtable
1	1.00	1.03
2	2.59	32.40
4	5.58	78.23
8	13.21	163.48
16	27.58	341.21
32	57.27	778.41

-------------------------------------------
参考：
1、JDK API doc online: http://docs.oracle.com/javase/6/docs/api/java/util/Map.html
2、ConcurrentHashMap and CopyOnWriteArrayList offer thread safety and improved scalabilityhttp://www.ibm.com/developerworks/java/library/j-jtp07233/index.html