[数据结构与算法]【数据结构】HashMap、LinkedHashMap和TreeMap区别和使用

前言

关于HashMap、ConcurrentHashMap底层知识前面已有文章进行分析了，面试 ConcurrentHashMap ，看这一篇就够了！里面也链接了阿里大佬的HashMap非常精彩的干货。因此，在本文中只会介绍HashMap、LinkedHashMap和TreeMap的一些明显区别。

1、HashMap

HashMap是无序的数据结构，也就是说，插入顺序和读取顺序不一致，下面简单验证即可。

class Test{
    public static void main(String[] args) {
        Map<String, String> hashMap = new HashMap<String, String>();
        hashMap.put("key1", "value1");
        hashMap.put("key2", "value2");
        hashMap.put("key4", "value4");
        hashMap.put("key3", "value3");
        Set<Map.Entry<String, String>> set = hashMap.entrySet();
        Iterator<Map.Entry<String, String>> iterator = set.iterator();
        while(iterator.hasNext()) {
            Map.Entry entry = iterator.next();
            String key = (String) entry.getKey();
            String value = (String) entry.getValue();
            System.out.println("key:" + key + ",value:" + value);
        }
    }
}

2、LinkedHashMap

相比较而言，LinkedHashMap继承于HashMap，基于HashMap和双向链表来实现的，显然，使用LinkedList主要是为了维护插入顺序，LinkedHashMap是线程不安全的。详细的底层解析可参见：图解LinkedHashMap原理。因此，LinkedHashMap是有序的数据结构，其实现如下图所示。

内部的Entry其实是继承自HashMap的Node数组，许多的方法LinkedHashMap都是调用HashMap的方法来实现的（如put方法）。

下面我们换成LinkedHashMap来看。

class Test{
    public static void main(String[] args) {
        Map<String, String> linkedHashMap= new LinkedHashMap<>();
        linkedHashMap.put("key1", "value1");
        linkedHashMap.put("key2", "value2");
        linkedHashMap.put("key4", "value4");
        linkedHashMap.put("key3", "value3");
        Set<Map.Entry<String, String>> set = linkedHashMap.entrySet();
        Iterator<Map.Entry<String, String>> iterator = set.iterator();
        while(iterator.hasNext()) {
            Map.Entry entry = iterator.next();
            String key = (String) entry.getKey();
            String value = (String) entry.getValue();
            System.out.println("key:" + key + ",value:" + value);
        }
    }
}

当我们想要插入顺序和访问顺序一致的时候，我们就可以使用LinkedHashMap了，如LRU缓存实现。面试题 16.25. LRU 缓存，LinkedHashMap重载的构造方法中还有一个特别的参数，accessOrder用于设置访问顺序存储还是插入顺序存储，默认为false表示按照插入顺序存储。在多个构造方法中都默认设置为false，当然我们也可以使用特定的构造方法设定该值，其构造方法如下：

下面我们将accessOrder设置为true，表示LinkedHashMap中存储的顺序是按照访问顺序进行存储的。

class Test{
    public static void main(String[] args) {
        Map<String, String> linkedHashMap = new LinkedHashMap<>(16, 0.75f, true);
        linkedHashMap.put("key1", "value1");
        linkedHashMap.put("key2", "value2");
        linkedHashMap.put("key4", "value4");
        linkedHashMap.put("key3", "value3");
        Set<Map.Entry<String, String>> set = linkedHashMap.entrySet();
        Iterator<Map.Entry<String, String>> iterator = set.iterator();
        System.out.println("开始时默认为插入顺序：");
        while(iterator.hasNext()) {
            Map.Entry entry = iterator.next();
            String key = (String) entry.getKey();
            String value = (String) entry.getValue();
            System.out.println("key:" + key + ",value:" + value);
        }
        System.out.println("通过get方法，导致key为key1对应的Entry到表尾");
        linkedHashMap.get("key4"); //访问一次，看一下状态如何变化
        Set<Map.Entry<String, String>> set1 = linkedHashMap.entrySet();
        Iterator<Map.Entry<String, String>> iterator1 = set1.iterator();
        while(iterator1.hasNext()) {
            Map.Entry entry = iterator1.next();
            String key = (String) entry.getKey();
            String value = (String) entry.getValue();
            System.out.println("key:" + key + ",value:" + value);
        }
    }
}

也就是最近访问的会被放到末尾，这就很容易使用LinkedHashMap实现LRU了。

3、TreeMap

与HashMap相比，TreeMap是一个能比较元素大小的Map集合，会对传入的key进行了大小排序。其中，可以使用元素的自然顺序（默认Key升序排列），也可以使用集合中自定义的比较器Comparator接口来进行排序；结构上，TreeMap不同于HashMap的哈希映射，TreeMap实现了红黑树的结构，形成了一颗二叉树。

class Test{
    public static void main(String[] args) {
    //借助Lambda表达式简化：TreeMap<String,Integer> treeMap = new TreeMap<String,Integer>(((o1, o2) -> o2.compareTo(o1)));
        TreeMap<String,Integer> treeMap = new TreeMap<String,Integer>(new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return -o1.compareTo(o2); //按照key降序排列
            }
        });
        treeMap.put("key1", 1);
        treeMap.put("key2", 2);
        treeMap.put("key3", 3);
        Set<String> keys = treeMap.keySet();
        Iterator<String> iter = keys.iterator();
        while(iter.hasNext()) {
            String key = iter.next();
            System.out.println(" "+key+":"+treeMap.get(key));
        }
    }
}

假设我们要对value进行排序，那么我们可以将其转为List再利用Collections进行排序：

class Test{
    public static void main(String[] args) {
        TreeMap<String,Integer> treeMap = new TreeMap<String,Integer>();
        treeMap.put("key1", 1);
        treeMap.put("key2", 2);
        treeMap.put("key4", 4);
        treeMap.put("key3", 3);

        List<Map.Entry<String, Integer>> list = new ArrayList<Map.Entry<String, Integer>>(treeMap.entrySet());

        Collections.sort(list,new Comparator<Map.Entry<String,Integer>>() {
            //升序排序
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                return o2.getValue()-o1.getValue();
            }
        });
        for (Map.Entry<String, Integer> e: list) {
            System.out.println(e.getKey()+":"+e.getValue());
        }
    }
}