HashMap与TreeMap

小咪咪 2022-12-30 05:00 313阅读 0赞

**1、HashMap**  
使用HashMap做个测试：

Map<Character, Integer> map = new HashMap<Character, Integer>();
    map.put('s', 1);
    map.put('a', 3);
    map.put('j', 2);
    map.put('d', 9);
    map.put('f', 3);
    for (Character in : map.keySet()) {
        Integer str = map.get(in);//得到每个key多对用value的值
        System.out.println(in + "     " + str);
    }

输出结果：

a     3
    s     1
    d     9
    f     3
    j     2

现象：输出顺序是无序的，既不是插入的先后顺序，也不是key的大小顺序。  
总结：HashMap是无序的存储结构。

**2、TreeMap**  
相同的代码，把HashMap换成TreeMap：

Map<Character, Integer> map = new TreeMap<Character, Integer>();
    map.put('s', 1);
    map.put('a', 3);
    map.put('j', 2);
    map.put('d', 9);
    map.put('f', 3);
    for (Character in : map.keySet()) {
        Integer str = map.get(in);//得到每个key多对用value的值
        System.out.println(in + "     " + str);
    }

输出结果：

a     3
    d     9
    f     3
    j     2
    s     1

现象：输出顺序是按照key的顺序，从小到大输出的。  
总结：TreeMap是有序的存储结构。这里的有序、无序指的是key的大小顺序，不是先后插入顺序。

**为什么会这样？**  
HashMap基于哈希表，底层结构由数组来实现，hash值重复的情况，我们称之为哈希碰撞（又或者哈希冲突）。在HashMap中，是通过链表的形式来解决的，在hash值重复的数组角标下，通过链表将新插入的元素依次排列，当然如果插入的key相同，那么我们会将新插入的value覆盖掉原有的value。  
TreeMap基于红黑树，所谓红黑树就是用红黑标注节点的自平衡二叉树，每次插入或删除节点时，key需要按照比较器（JDK自带或者自定义）来选择插入的位置，并且为了满足红黑树的特征，需要进行左旋、右旋、着色操作，来平衡二叉树。

**优点：**  
HashMap：数组+链表的存储方式，key值化身hashcode简单高效，插入和删除操作效率都很高。  
TreeMap：拥有自平衡二叉树的优点，查询非常高效。

**缺点：**  
HashMap：如果频繁插入数据，会导致HashMap频繁扩容，每次扩容都要重新拷贝数据，开销较大。  
TreeMap：每次插入和删除操作，都需要进行左旋、右旋、着色操作，来平衡二叉树，开销较大。

下面我用代码来验证一下HashMap与TreeMap的插入速率：

size = 1\* 10000输出结果：

长度：10000
    HashMap 10000次插入。耗时：3
    TreeMap 10000次插入。耗时：11

修改size = 10\* 10000输出结果：

长度：100000
    HashMap 100000次插入。耗时：18
    TreeMap 100000次插入。耗时：37

修改size = 100\* 10000输出结果：

长度：1000000
    HashMap 1000000次插入。耗时：127
    TreeMap 1000000次插入。耗时：520

修改size = 1000\* 10000输出结果：

长度：10000000
    HashMap 10000000次插入。耗时：8584
    TreeMap 10000000次插入。耗时：12609

结论：从一万到一千万的数量级来说，都是HashMap的插入操作效率要远远高于TreeMap，这是因为TreeMap每次插入操作都要进行大量的运算。

下面升级一下代码，看看查询速度怎么样：

int size = 1* 10000;
    System.out.println("长度：" + size);
    long timeHashMapPut = System.currentTimeMillis();
    Map<Integer, Integer> hashMap = new HashMap<>();
    for (int i=0;i<size;i++) {
        hashMap.put(i, i);
    }
    System.out.println("HashMap " + size+"次插入。耗时：" + (System.currentTimeMillis() - timeHashMapPut));
    long timeHashMapQuery = System.currentTimeMillis(); //增加查询耗时
    for (int i=0;i<10;i++) {
        int key = (int) (Math.random() * size);
        System.out.println("查询结果"+key+"：" + hashMap.get(key));
    }
    System.out.println("HashMap " +"10次查询。耗时：" + (System.currentTimeMillis() - timeHashMapQuery));
    
    long timeTreeMapPut = System.currentTimeMillis();
    Map<Integer, Integer> treeMap = new TreeMap<Integer, Integer>();
    for (int i=0;i<size;i++) {
        treeMap.put(i, i);
    }
    System.out.println("TreeMap " + size+"次插入。耗时：" + (System.currentTimeMillis() - timeTreeMapPut));
    long timeTreeMapQuery = System.currentTimeMillis(); //增加查询耗时
    for (int i=0;i<10;i++) {
        int key = (int) (Math.random() * size);
        System.out.println("查询结果"+key+"：" + treeMap.get(key));
    }
    System.out.println("TreeMap " +"10次查询。耗时：" + (System.currentTimeMillis() - timeTreeMapQuery));

size = 1\* 10000输出结果：

长度：10000
    HashMap 10000次插入。耗时：2
    HashMap 10次查询。耗时：1
    TreeMap 10000次插入。耗时：10
    TreeMap 10次查询。耗时：0

修改size = 10\* 10000输出结果：

长度：100000
    HashMap 100000次插入。耗时：17
    HashMap 10次查询。耗时：0
    TreeMap 100000次插入。耗时：35
    TreeMap 10次查询。耗时：0

修改size = 100\* 10000输出结果：

长度：1000000
    HashMap 1000000次插入。耗时：529
    HashMap 10次查询。耗时：1
    TreeMap 1000000次插入。耗时：499
    TreeMap 10次查询。耗时：0

修改size = 1000\* 10000输出结果：

长度：10000000
    HashMap 10000000次插入。耗时：11048
    HashMap 10次查询。耗时：1
    TreeMap 10000000次插入。耗时：6079
    TreeMap 10次查询。耗时：0

总结：从一万到一千万的数量级来说，TreeMap是查询效率稍微高于HashMap，但是优势可以忽略不计。总体来说，日常使用，HashMap的综合效率要高于TreeMap。

[什么是红黑树？][Link 1]  
[Java集合–TreeMap完全解析][Java_TreeMap]

[Link 1]: https://blog.csdn.net/qq_36610462/article/details/83277524
[Java_TreeMap]: https://www.jianshu.com/p/2dcff3634326