HashMap、LinkedHashMap、TreeMap的区别

我更喜欢视觉呈现：

属性 HashMap TreeMap LinkedHashMap Iteration Order 没有保证的顺序，会随着时间的推移保持不变 按照插入顺序自然排序 Get / put / remove / containsKey O(1) O(log(n)) O(1) 接口 Map NavigableMap, Map, SortedMap Map Null values/keys allowed only values allowed 快速失败行为 不能保证迭代器的快速失败行为，在存在不同步的并发修改的情况下不可能做出任何硬保证 不能保证迭代器的快速失败行为, 在存在不同步的并发修改的情况下无法做出任何硬保证 无法保证迭代器的快速失败行为, 在存在不同步的并发修改的情况下无法做出任何硬保证 实现桶 红黑树双链桶 是同步的实现不同步 实现不同步 实现不同步

---

所有三个类都实现了 Map 接口并提供了几乎相同的功能。最重要的区别是条目迭代发生的顺序：

HashMap 绝对不保证迭代顺序。当添加新元素时，它甚至可以（并且将会）完全改变。

TreeMap 将根据它们的 compareTo() 方法（或外部提供的比较器）根据键的“自然顺序”进行迭代。此外，它还实现了 SortedMap 接口，该接口包含依赖于此排序顺序的方法。

LinkedHashMap 将按照条目放入地图的顺序进行迭代

"Hashtable" 是基于哈希的映射的通用名称。在 Java API 的上下文中，Hashtable 是集合框架存在之前的 Java 1.1 时代的一个过时类。不应再使用它，因为它的 API 中充斥着重复功能的过时方法，并且它的方法是同步的（这会降低性能并且通常是无用的）。使用 ConcurrentHashMap 而不是 Hashtable。

---

这三个都表示从唯一键到值的映射，因此实现了 Map 接口。

HashMap 是基于键的散列的映射。它支持 O(1) 获取/放置操作。键必须具有一致的 hashCode() 和 equals() 实现才能工作。 LinkedHashMap 与 HashMap 非常相似，但它增加了对添加（或访问）项的顺序的感知，因此迭代顺序与插入顺序（或访问顺序，取决于构造参数）相同。 TreeMap 是基于树的映射。它的 put/get 操作需要 O(log n) 时间。它要求项目具有某种比较机制，无论是 Comparable 还是 Comparator。迭代顺序由该机制确定。

---

在下图 (bigger one) 中查看每个类在类层次结构中的位置。 TreeMap 实现了 SortedMap 和 NavigableMap 而 HashMap 没有。

https://i.stack.imgur.com/MtCX2.png

---

哈希映射

它有对值（键，值）

没有重复键值

无序无序

它允许一个空键和多个空值

哈希表

与哈希图相同

它不允许空键和空值

LinkedHashMap

它是地图实现的有序版本

基于链表和散列数据结构

树状图

订购和分类版本

基于散列数据结构

---

只是从我自己的地图经验中获得的更多信息，关于我何时使用每一张地图：

HashMap - 在寻找最佳性能（快速）实现时最有用。

TreeMap（SortedMap 接口） - 当我关心能够以我定义的特定顺序对键进行排序或迭代时最有用。

LinkedHashMap - 结合了从 TreeMap 保证排序的优点，而不会增加维护 TreeMap 的成本。 （它几乎和 HashMap 一样快）。特别是，LinkedHashMap 还通过重写 removeEldestEntry() 方法为创建 Cache 对象提供了一个很好的起点。这使您可以创建一个 Cache 对象，该对象可以使用您定义的某些条件使数据过期。

---

HashMap、TreeMap 和 LinkedHashMap 这三个类都实现了 java.util.Map 接口，并表示从唯一键到值的映射。

HashMap

HashMap 包含基于键的值。它只包含独特的元素。它可能有一个空键和多个空值。它没有秩序。公共类 HashMap 扩展 AbstractMap 实现 Map、可克隆、可序列化

LinkedHashMap

LinkedHashMap 包含基于键的值。它只包含独特的元素。它可能有一个空键和多个空值。它与 HashMap 相同，而是维护插入顺序。 //参见下面的类减速 public class LinkedHashMap extends HashMap implements Map

TreeMap

TreeMap 包含基于键的值。它实现了 NavigableMap 接口并扩展了 AbstractMap 类。它只包含独特的元素。它不能有空键，但可以有多个空值。它与 HashMap 相同，而是保持升序（使用其键的自然顺序排序。）。公共类 TreeMap 扩展 AbstractMap 实现 NavigableMap、Cloneable、Serializable

Hashtable

Hashtable 是一个列表数组。每个列表称为一个桶。通过调用 hashcode() 方法来识别桶的位置。哈希表包含基于键的值。它只包含独特的元素。它可能没有任何空键或值。它是同步的。这是一个遗留类。公共类 Hashtable 扩展 Dictionary 实现 Map、Cloneable、Serializable

https://i.stack.imgur.com/clp27.jpg

参考：http://javarevisited.blogspot.in/2015/08/difference-between-HashMap-vs-TreeMap-vs-LinkedHashMap-Java.html

---

HashMap 绝对不保证迭代顺序。当添加新元素时，它甚至可以（并且将会）完全改变。 TreeMap 将根据它们的 compareTo() 方法（或外部提供的比较器）根据键的“自然顺序”进行迭代。此外，它还实现了 SortedMap 接口，该接口包含依赖于此排序顺序的方法。 LinkedHashMap 将按照条目放入地图的顺序进行迭代

https://i.stack.imgur.com/9Ete5.jpg

树图是排序图的一种实现。由于自然排序，put、get 和 containsKey 操作的复杂度为 O(log n)

---

@Amit：SortedMap 是一个接口，而 TreeMap 是一个实现 SortedMap 接口的类。这意味着 if 遵循 SortedMap 要求其实施者执行的协议。除非实现为搜索树，否则树不能为您提供有序数据，因为树可以是任何类型的树。因此，为了使 TreeMap 像 Sorted order 一样工作，它实现了 SortedMap（例如，二叉搜索树 - BST，平衡 BST，如 AVL 和 RB 树，甚至三叉搜索树 - 主要用于以有序方式进行迭代搜索）。

public class TreeMap<K,V>
extends AbstractMap<K,V>
implements SortedMap<K,V>, Cloneable, Serializable

在 NUT-SHELL HashMap 中：给出 O(1) 中的数据，没有排序

TreeMap ：给出 O(log N) 中的数据，以 2 为底。带有有序键

LinkedHashMap ：是具有链表（想想 indexed-SkipList）能力的哈希表，以插入树的方式存储数据。最适合实现 LRU（最近最少使用）。

---

哈希映射不保留插入顺序。例子。 Hashmap 如果您将键插入为

1  3
5  9
4   6
7   15
3   10

它可以将其存储为

4  6
5  9
3  10
1  3
7  15

Linked Hashmap 保留插入顺序。

例子。如果您要插入密钥

1  3
5  9
4   6
7   15
3   10

它会将其存储为

1  3
5  9
4   6
7   15
3   10

和我们插入的一样。

树图以递增的键顺序存储值。例子。如果您要插入密钥

1  3
5  9
4   6
7   15
3   10

它会将其存储为

1  3
3  10
4   6
5   9
7   15

---

以下是 HashMap 和 TreeMap 之间的主要区别

HashMap 不维护任何顺序。换句话说，HashMap 不提供任何保证首先插入的元素将首先打印，其中就像 TreeSet 一样，TreeMap 元素也根据其元素的自然顺序进行排序内部 HashMap 实现使用 Hashing，TreeMap 内部使用 Red-黑树实现。 HashMap 可以存储一个空键和多个空值。TreeMap 不能包含空键，但可以包含多个空值。 HashMap 对 get 和 put 等基本操作具有恒定的时间性能，即 O(1)。根据 Oracle 文档，TreeMap 为 get 和 put 方法提供有保证的 log(n) 时间成本。 HashMap 比 TreeMap 快得多，因为对于大多数操作，HashMap 的性能时间相对于 TreeMap 的日志时间是恒定的。 HashMap 使用 equals() 方法进行比较，而 TreeMap 使用 compareTo() 方法来维护排序。 HashMap 实现 Map 接口，而 TreeMap 实现 NavigableMap 接口。

---

HashMap：Order 不保持比 LinkedHashMap 更快用于存储对象堆

订单不维护

比 LinkedHashMap 更快

用于存储对象堆

LinkedHashMap：LinkedHashMap 插入顺序将保持比 HashMap 慢，比 TreeMap 快 如果要保持插入顺序，请使用此选项。

LinkedHashMap 插入顺序将保持不变

比 HashMap 慢，比 TreeMap 快

如果您想维护广告订单，请使用此选项。

TreeMap：TreeMap是基于树的映射 TreeMap会遵循key的自然排序 比HashMap和LinkedHashMap慢 需要保持自然（默认）排序时使用TreeMap

TreeMap 是基于树的映射

TreeMap 将遵循 key 的自然顺序

比 HashMap 和 LinkedHashMap 慢

当您需要保持自然（默认）排序时使用 TreeMap

---

这些是同一接口的不同实现。每种实现都有一些优点和一些缺点（快速插入，慢速搜索），反之亦然。

有关详细信息，请查看 TreeMap、HashMap、LinkedHashMap 的 javadoc。

---

虽然这里有很多优秀的答案，但我想提供我自己的表格来描述与 Java 11 捆绑的各种 Map 实现。

我们可以在表格图形中看到这些差异：

HashMap 是无特殊需求时常用的通用 Map。

LinkedHashMap 扩展了 HashMap，添加了以下行为： 维护一个顺序，即最初添加条目的顺序。更改键值条目的值不会改变其在顺序中的位置。

TreeMap 也维护一个顺序，但使用（a）“自然”顺序，这意味着在 Comparable 接口上定义的关键对象上 compareTo 方法的值，或者（b）调用您提供的 Comparator 实现。 TreeMap 实现了 SortedMap 接口及其继承者 NavigableMap 接口。

TreeMap 实现了 SortedMap 接口及其继承者 NavigableMap 接口。

NULLs：TreeMap 不允许 NULL 作为键，而 HashMap 和 LinkedHashMap 允许。这三个都允许 NULL 作为值。

这三个都允许 NULL 作为值。

HashTable 是 Java 1 的遗留物。被 ConcurrentHashMap 类取代。引用 Javadoc： ConcurrentHashMap 遵循与 Hashtable 相同的功能规范，并包含与 Hashtable 的每个方法对应的方法版本。

https://i.stack.imgur.com/NAuTl.png

---

这三者中最重要的是它们如何保存条目的顺序。

HashMap - 不保存条目的顺序。例如。

public static void main(String[] args){
        HashMap<String,Integer> hashMap = new HashMap<>();
        hashMap.put("First",1);// First ---> 1 is put first in the map
        hashMap.put("Second",2);//Second ---> 2 is put second in the map
        hashMap.put("Third",3); // Third--->3 is put third in the map
        for(Map.Entry<String,Integer> entry : hashMap.entrySet())
        {
            System.out.println(entry.getKey()+"--->"+entry.getValue());
        }
    }

https://i.stack.imgur.com/f7dhQ.png

LinkedHashMap ：它保存输入的顺序。例如：

public static void main(String[] args){
        LinkedHashMap<String,Integer> linkedHashMap = new LinkedHashMap<>();
        linkedHashMap.put("First",1);// First ---> 1 is put first in the map
        linkedHashMap.put("Second",2);//Second ---> 2 is put second in the map
        linkedHashMap.put("Third",3); // Third--->3 is put third in the map
        for(Map.Entry<String,Integer> entry : linkedHashMap.entrySet())
        {
            System.out.println(entry.getKey()+"--->"+entry.getValue());
        }
    }

https://i.stack.imgur.com/4sBoG.png

TreeMap ：它以键的升序保存条目。例如：

public static void main(String[] args) throws IOException {
        TreeMap<String,Integer> treeMap = new TreeMap<>();
        treeMap.put("A",1);// A---> 1 is put first in the map
        treeMap.put("C",2);//C---> 2 is put second in the map
        treeMap.put("B",3); //B--->3 is put third in the map
        for(Map.Entry<String,Integer> entry : treeMap.entrySet())
        {
            System.out.println(entry.getKey()+"--->"+entry.getValue());
        }
    }

https://i.stack.imgur.com/QEkX1.png

---

所有这些都提供了一个键-> 值映射和一种遍历键的方法。这些类之间最重要的区别是时间保证和键的顺序。

HashMap 提供 0(1) 查找和插入。但是，如果您遍历键，键的顺序基本上是任意的。它由一组链表实现。 TreeMap 提供 O(log N) 查找和插入。键是有序的，因此如果您需要按排序顺序遍历键，您可以。这意味着键必须实现 Comparable 接口。TreeMap 由红黑树实现。 LinkedHashMap 提供 0(1) 查找和插入。键按其插入顺序排序。它由双重链接的存储桶实现。

假设您将一个空的 TreeMap、HashMap 和 LinkedHashMap 传递给以下函数：

void insertAndPrint(AbstractMap<Integer, String> map) {
  int[] array= {1, -1, 0};
  for (int x : array) {
    map.put(x, Integer.toString(x));
  }
  for (int k: map.keySet()) {
   System.out.print(k + ", ");
  }
}

每个的输出将如下面的结果所示。

对于 HashMap，在我自己的测试中，输出是 {0, 1, -1}，但它可以是任何顺序。没有对订购的保证。 Treemap，输出为，{ -1, 0, 1} LinkedList，输出为，{ 1, -1, 0}

---

HashMap 可以包含一个空键。

HashMap 没有顺序。

树状图

TreeMap 不能包含任何空键。

TreeMap 保持升序。

LinkedHashMap

LinkedHashMap 可用于维护插入顺序，将哪些键插入 Map，也可用于维护访问顺序，即访问哪些键。

例子：：

1) HashMap 映射 = 新的 HashMap();

    map.put(null, "Kamran");
    map.put(2, "Ali");
    map.put(5, "From");
    map.put(4, "Dir");`enter code here`
    map.put(3, "Lower");
    for (Map.Entry m : map.entrySet()) {
        System.out.println(m.getKey() + "  " + m.getValue());
    } 

2) TreeMap map = new TreeMap();

    map.put(1, "Kamran");
    map.put(2, "Ali");
    map.put(5, "From");
    map.put(4, "Dir");
    map.put(3, "Lower");
    for (Map.Entry m : map.entrySet()) {
        System.out.println(m.getKey() + "  " + m.getValue());
    }

3) LinkedHashMap map = new LinkedHashMap();

    map.put(1, "Kamran");
    map.put(2, "Ali");
    map.put(5, "From");
    map.put(4, "Dir");
    map.put(3, "Lower");
    for (Map.Entry m : map.entrySet()) {
        System.out.println(m.getKey() + "  " + m.getValue());
    }

---