JAVA学习-Map详解

1.介绍

Map接口定义了一个保存key-value的对象，该对象中key值是不存在重复的，每个key值至多对应一个value
在前面几篇的文章中分别介绍了Map的实现类，如HashMap、Hashtable、TreeMap，详细可以查看

• JAVA学习-HashMap详解
• JAVA学习-Hashtable详解
• JAVA学习-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进行编码，如有问题，望指正。