Java中HashMap、TreeMap和LinkedHashMap的比较

前言

1. HashMap中k的值没有顺序，常用来做统计。

2.LinkedHashMap吧。它内部有一个链表，保持Key插入的顺序。迭代的时候，也是按照插入顺序迭代，而且迭代比HashMap快。

3. TreeMap的顺序是Key的自然顺序（如整数从小到大），也可以指定比较函数。但不是插入的顺序。

4.Hashtable与 HashMap类似,它继承自Dictionary类、不同的是:它不允许记录的键或者值为空;它支持线程的同步、即任一时刻只有一个线程能写Hashtable,因此也导致了 Hashtable在写入时会比较慢。

HashMap

　　HashMap的底层数据结构是 “数组 + 链表”，HashMap的方法不是同步的允许key和value为null的情况。

　　HashMap存储的数据是无序的，存放的顺序和取出的顺序不一致。

　　特点：

　　① HashMap 是一个最常用的Map，它根据键的HashCode 值存储数据，根据键可以直接获取它的值、具有很快的访问速度；

　　② 遍历时、取得数据的顺序是完全随机的；

　　③ HashMap最多只允许一条记录的键为Null；

　　④ 允许多条记录的值为 Null；

　　⑤ HashMap不支持线程的同步、即任一时刻可以有多个线程同时写HashMap；

　　⑥ 可能会导致数据的不一致、如果需要同步、可以用 Collections的synchronizedMap方法使HashMap具有同步的能力、或者使用ConcurrentHashMap。

public static void noOrder() {
        System.out.println("------无序（随机输出）------");
        Map map = new HashMap();
        map.put("1", "Level 1");
        map.put("2", "Level 2");
        map.put("3", "Level 3");
        map.put("4", "Level 4");
        map.put("F", "Level F");
        map.put("Q", "Level Q");
        Iterator it = map.entrySet().iterator();
        while (it.hasNext()) {
            Map.Entry e = (Map.Entry) it.next();
            System.out.println("Key: " + e.getKey() + ";   Value: "
                    + e.getValue());
        }
    }

运行结果：

------无序（随机输出）------
Key: 1;   Value: Level 1
Key: Q;   Value: Level Q
Key: 2;   Value: Level 2
Key: 3;   Value: Level 3
Key: 4;   Value: Level 4
Key: F;   Value: Level F

LinkedHashMap

　　LinkedHashMap 是HashMap的一个子类。LinkedHashMap 拥有 HashMap 的所有特性，它比 HashMap 多维护了一个双向链表，因此可以按照插入的顺序从头部或者从尾部迭代，是有序的，不过因为比 HashMap 多维护了一个双向链表，它的内存相比而言要比 HashMap 大，并且性能会差一些，但是如果需要考虑到元素插入的顺序的话， LinkedHashMap 不失为一种好的选择。

public static void linkedHashMap() {
    System.out.println("------有序（根据输入的顺序输出）------");
    Map map = new LinkedHashMap();
    map.put("F", "Level F");
    map.put("7", "Level 1");
    map.put("8", "Level 2");
    map.put("4", "Level 3");
    map.put("4", "Level 4");
    map.put("Q", "Level Q");
    map.put("E", "Level E");
    Iterator it = map.entrySet().iterator();
    while (it.hasNext()) {
        Map.Entry e = (Map.Entry) it.next();
        System.out.println("Key: " + e.getKey() + ";   Value: "
                + e.getValue());
    }
}

运行结果：

------有序（根据输入的顺序输出）------
Key: F; Value: Level F
Key: 7; Value: Level 1
Key: 8; Value: Level 2
Key: 4; Value: Level 4
Key: Q; Value: Level Q
Key: E; Value: Level E

TreeMap

　　

　　与 HashMap 不同， TreeMap 的底层就是一颗红黑树，它的 containsKey , get , put and remove 方法的时间复杂度是 log(n) ，并且它是按照 key 的自然顺序（或者指定排序）排列，与 LinkedHashMap 不同， LinkedHashMap 保证了元素是按照插入的顺序排列。

　　TreeMap取出来的是排序后的键值对。但如果您要按自然顺序（字典顺序），那么TreeMap会更好。

public static void hasOrder() {
        System.out.println("------有序（但是按默认顺充，不能指定）------");
        Map map = new TreeMap();
        map.put("F", "Level F");
        map.put("7", "Level 1");
        map.put("8", "Level 2");
        map.put("4", "Level 3");
        map.put("4", "Level 4");
        map.put("Q", "Level Q");
        map.put("E", "Level E");
        Iterator it = map.entrySet().iterator();
        while (it.hasNext()) {
            Map.Entry e = (Map.Entry) it.next();
            System.out.println("Key: " + e.getKey() + ";   Value: "
                    + e.getValue());
        }
    }

运行结果：

------有序（但是按默认顺充，不能指定）------
Key: 4;   Value: Level 4
Key: 7;   Value: Level 1
Key: 8;   Value: Level 2
Key: E;   Value: Level E
Key: F;   Value: Level F
Key: Q;   Value: Level Q