Java源码解析 —— Map总结

Contents
  1. 各类Map详解
  2. 类图结构
  3. 比较
    1. 区别
      1. 基本
      2. 实现
      3. 内部原理
      4. 线程安全性
    2. 性能

各类Map详解

Map接口定义了一个保存key-value的对象,该对象中key值是不存在重复的,每个key值至多对应一个value。

在前面几篇的文章中分别介绍了Map的实现类,如HashMap、Hashtable、TreeMap,详细可以查看:

类图结构

Map

如上图所示是实现Map接口的类图结构,主要包含了如下的类与接口:

  • Map接口:定义将键值映射到值的对象,Map规定不能包含重复的键值,每个键最多可以映射一个值,这个接口是用来替换Dictionary类。
  • AbstractMap类:提供了一个Map骨架的实现,尽量减少了实现Map接口所需要的工作量
  • HashMap类:HashMap是实现了Map接口的key-value集合,实现了所有map的操作,允许key和value为null,它相当于Hashtable,与之存在的区别是hashMap不是线程安全的,HashMap允许null值。
  • TreeMap类:TreeMap是基于红黑树的实现,也是记录了key-value的映射关系,该映射根据key的自然排序进行排序或者根据构造方法中传入的比较器进行排序,也就是说TreeMap是有序的key-value集合
  • Hashtable类:它是类似与HashMap的key-value的哈希表,不允许key-value为NULL值,另外一点值得注意的是Hashtable是线程安全的
  • Serializable接口:实现了该接口标识了类可以被序列化和反序列化,具体的 查询序列化详解
  • Cloneable接口:实现了该接口的类可以显示的调用Object.clone()方法,合法的对该类实例进行字段复制,如果没有实现Cloneable接口的实例上调用Obejct.clone()方法,会抛出CloneNotSupportException异常。正常情况下,实现了Cloneable接口的类会以公共方法重写Object.clone()

比较

虽然HashMap、Hashtable、TreeMap这三个都是Map接口的实现,其内部实现及性能等还是存在区别,下面将从区别及性能两个方面去分析。

区别

基本

  • HashMap:初始化容量为16,扩容每次为2 * oldCap, key-value可以为NULL值
  • Hashtable:初始化容量为11,扩容每次为2 * oldCap + 1, key-value不可以为NULL值
  • TreeMap:初始化容量为0,内部是红黑树结构,不存在hash冲突的情况,不存在扩容的操作, key-value不可以为NULL值

实现

  • HashMap:实现了Map接口,继承了AbstractMap类
  • Hashtable:实现了Map接口,继承了AbstractMap类
  • TreeMap:由于TreeMap是有序的,所以其除了实现了Map接口,还实现了SortedMap、NavigableMap接口

内部原理

  • HashMap:HashMap是散列表实现,内部是数组+链表或者红黑树的结构
  • Hashtable:Hashtable也是散列表实现,内部是数组+链表的结构
  • TreeMap:TreeMap内部是红黑树的结构

线程安全性

  • HashMap:不是线程安全的,其实通过Map m = Collections.synchronizeMap(hashMap)的方式也可以使得HashMap变成线程安全的,但是这样做对程序的性能可能是噩梦,在后面会介绍ConcurrentHashMap,建议在多线程的情况下可以使用ConcurrentHashMap替换HashMap
  • Hashtable:是线程安全的,内部方法使用关键字synchronized修饰
  • TreeMap:不是线程安全的

性能

按照如下代码对HashMap、Hashtable、TreeMap的性能进行测试:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
public class HashMapProgress {
//定义用于测试的HashMap
private static HashMap<Integer,Integer> hashMap = new HashMap<>();
//定义用于测试的Hashtable
private static Hashtable<Integer,Integer> hashtable = new Hashtable<>();
//定义用于测试的TreeMap
private static TreeMap<Integer,Integer> treeMap = new TreeMap<>();
/**
* 添加元素的方法
* @param map 对应的map
* @param count 添加个数
*/
public static void addEntry(Map<Integer,Integer> map, int count){
Long startTime = System.currentTimeMillis();
if (count <= 0){
return;
}
for (int i = 0; i < count; i++) {
map.put(i,i);
}
Long endTime = System.currentTimeMillis();
System.out.println("添加(" + count + ")个元素使用时间:" + (endTime - startTime) + "s");
}
/**
* 获取元素的方法
* @param map
* @param count
*/
public static void getEntry(Map<Integer,Integer> map, int count){
Long startTime = System.currentTimeMillis();
if (count <= 0){
return;
}
for (int i = 0; i < count; i++) {
map.get(i);
}
Long endTime = System.currentTimeMillis();
System.out.println("获取(" + count + ")个元素使用时间:" + (endTime - startTime) + "s");
}
public static void main(String[] args){
System.out.println("-------HashMap测试开始-----");
addEntry(hashMap,1000000);
getEntry(hashMap,1000000);
System.out.println("-------HashMap测试结束-----");
System.out.println("-------Hashtable测试开始-----");
addEntry(hashtable,1000000);
getEntry(hashtable,1000000);
System.out.println("-------Hashtable测试结束-----");
System.out.println("-------TreeMap测试开始-----");
addEntry(treeMap,1000000);
getEntry(treeMap,1000000);
System.out.println("-------TreeMap测试结束-----");
}
}

分别测试了100000, 1000000, 10000000个数据的情况,测试结果如下所示:

数据量 HashMap HashTable TreeMap
100000 插入用时:18s 查询用时:9s 插入用时:14s 查询用时:5s 插入用时:33s 查询用时:17s
1000000 插入用时:98s 查询用时:20s 插入用时:625s 查询用时:31s 插入用时:242s 查询用时: 145s
1000000 插入用时:9773s 查询用时:811s 插入用时:15055s 查询用时:3369s 插入用时:22354s 查询用时: 3889s

通过上表可以看出随着数据量的增加,时间变化差异还是很大的,而在单线程的情况下还是尽量使用HashMap,相对于Hashtable、TreeMap性能更好,而针对特定的情况需视情况而论。