1.介绍
Map接口定义了一个保存key-value的对象，该对象中key值是不存在重复的，每个key值至多对应一个value
在前面几篇的文章中分别介绍了Map的实现类，如HashMap、Hashtable、TreeMap，详细可以查看
2.类图结构
Map结构
如上图所示是实现Map接口的类图结构，主要包含了如下的类与接口：
- Map接口： 定义将键值映射到值的对象，Map规定不能包含重复的键值，每个键最多可以映射一个值,这个接口是用来替换Dictionary类。
- SortedMap接口:定义按照key排序的Map结构，规定key-value是根据键key值的自然排序进行排序的，或者根据构造key-value时设定的构造器进行排序。
- NavigableMap接口： 是SortedMap接口的子接口，在其基础上扩展了针对搜索目标返回最近匹配项的导航方法，例如方法lowEntry、floorEntry、ceilingEntry等，如果不存在这样的键，则返回null
- 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()
3.比较
虽然HashMap、Hashtable、TreeMap这三个都是Map接口的实现，其内部实现及性能等还是存在区别，下面将从区别及性能两个方面去分析。
3.1 区别
3.1.1 基本
- HashMap：初始化容量为16，扩容每次为2*oldCap,key-value可以为NULL值
- Hashtable：初始化容量为11，扩容每次为2*oldCap+1,key-value不可以为NULL值
- TreeMap：初始化容量为0，内部是红黑树结构，不存在hash冲突的情况，不存在扩容的操作,key-value不可以为NULL值
3.1.2 实现
- HashMap：实现了Map接口，继承了AbstractMap类
- Hashtable：实现了Map接口，继承了AbstractMap类
- TreeMap：由于TreeMap是有序的，所以其除了实现了Map接口，还实现了SortedMap、NavigableMap接口
3.1.3 内部原理
- HashMap:HashMap是散列表实现，内部是数组+链表或者红黑树的结构
- Hashtable：Hashtable也是散列表实现，内部是数组+链表的结构
- TreeMap：TreeMap内部是红黑树的结构
3.1.4 线程安全
- HashMap：不是线程安全的，其实通过Map m = Collections.synchronizeMap(hashMap)的方式也可以使得HashMap变成线程安全的，但是这样做对程序的性能可能是噩梦，在后面会介绍ConcurrentHashMap，建议在多线程的情况下可以使用ConcurrentHashMap替换HashMap.
- Hashtable：是线程安全的，内部方法使用关键字synchronized修饰
- TreeMap：不是线程安全的
3.2 性能
按照如下代码对HashMap、Hashtable、TreeMap的性能进行测试
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 |
| 10000000 | 插入用时：9773s 查询用时：811s | 插入用时：15055s 查询用时：3369s | 插入用时：22354s 查询用时： 3889s |
通过上表可以看出随着数据量的增加，时间变化差异还是很大的，而在单线程的情况下还是尽量使用HashMap，相对于Hashtable、TreeMap性能更好，而针对特定的情况需视情况而论。
4.总结
本文主要是对前面介绍的HashMap、Hashtable、TreeMap这些Map接口实现类的一个总结，主要分析这些实现类的一些特点以及存在的差异，最后想说的是针对不同的情况可以选择不同的Map进行编码，如有问题，望指正。
网友评论