HashMap、LinkedHashMap和TreeMap之间的区别 HashMap、LinkedHashMap和TreeMap是Java中常用的三种Map实现。它们都实现了Map接口，但在内部实现和性能方面有所不同。 HashMap是基于哈希表的实现，它使用键的哈希值来存储和检索数据。它提供了快速的插入、删除和查找操作，但不保证元素的顺序。 LinkedHashMap是HashMap的一个子类，它在HashMap的基础上添加了一个双向链表来维护元素的插入顺序。因此，它保留了元素的插入顺序，并且在迭代时按照插入顺序返回元素。 TreeMap是基于红黑树的实现，它根据键的自然顺序或自定义比较器来存储和检索数据。它提供了有序的键值对集合，可以按照键的顺序进行迭代。 选择使用哪种Map取决于你的需求。如果你需要快速的插入、删除和查找操作，并不关心元素的顺序，那么HashMap是一个不错的选择。如果你需要保留元素的插入顺序，可以使用LinkedHashMap。如果你需要有序的键值对集合，可以使用TreeMap。 希望这个解释能帮助你理解HashMap、LinkedHashMap和TreeMap之间的区别。

Question

在Java中，HashMap、LinkedHashMap和TreeMap有什么区别？

我在输出中没有看到任何区别，因为这三个都有keySet和values。

另外，Hashtable是什么？

Map<String, String> m1 = new HashMap<>();
m1.put("map", "HashMap");
m1.put("schildt", "java2");
m1.put("mathew", "Hyden");
m1.put("schildt", "java2s");
print(m1.keySet()); 
print(m1.values()); 

SortedMap<String, String> sm = new TreeMap<>();
sm.put("map", "TreeMap");
sm.put("schildt", "java2");
sm.put("mathew", "Hyden");
sm.put("schildt", "java2s");
print(sm.keySet()); 
print(sm.values());

LinkedHashMap<String, String> lm = new LinkedHashMap<>();
lm.put("map", "LinkedHashMap");
lm.put("schildt", "java2");
lm.put("mathew", "Hyden");
lm.put("schildt", "java2s");
print(lm.keySet()); 
print(lm.values());

- Kevin

Answer 1

我更喜欢视觉呈现：

属性	HashMap	TreeMap	LinkedHashMap
迭代顺序	没有保证的顺序，在时间上保持不变	按自然排序排序	插入顺序
获取 / 放置 / 删除 / 包含键	O(1)	O(log(n))	O(1)
接口	Map	NavigableMap、Map、SortedMap	Map
Null 值/键	允许	只允许值	允许
快速失败行为	无法保证迭代器的快速失败行为，在存在非同步并发修改的情况下，无法做出任何硬性保证	无法保证迭代器的快速失败行为，在存在非同步并发修改的情况下，无法做出任何硬性保证	无法保证迭代器的快速失败行为，在存在非同步并发修改的情况下，无法做出任何硬性保证
实现	桶	红黑树	双向链接桶
是否同步	实现未同步	实现未同步	实现未同步

- Sergii Shevchyk

---

除了插入顺序外，LinkedHashMap还支持访问顺序（当使用带有布尔类型access-order参数的构造函数时）。 - Eyal Schneider

双向链表桶？我认为这会增加不必要的开销，在插入/删除操作时需要搜索正确的桶来放置对象（因为它必须搜索正确的桶来放置对象）。我一直认为LinkedHashMap实现类似于Map，但额外增加了“条目列表”（可能是作为链接列表）用于迭代。Shevchyk，你确定吗？如果是的话，你能解释一下或给我一些在线链接来支持你的说法吗？ - Sai Dubbaka

@SaiDubbaka LinkedHashMap有双向链接桶，但也有HashMap的桶表。它不是替换它。这意味着访问桶与HashMap中的方式相同，因为链表仅用于按插入顺序（或访问顺序）进行迭代。 - Gerardo Lastra

值得一提的是，O(1) 是最优情况（通常不称为 O，参见此问题）。 - Sebastian S

值得注意的是，O(1)并不总是比O(log n)更好；如果您有一个非常长的关键字，基于二叉搜索树的方法可能比需要对整个关键字执行O(n)哈希才能执行任何操作的方法快得多。 - anon

Answer 2

三个类都实现了Map接口并提供了大部分相同的功能。最重要的区别是遍历条目的顺序：

• HashMap对遍历顺序不做任何保证。当添加新元素时，它甚至可以完全改变。
• TreeMap将根据键的“自然排序”按照它们的compareTo()方法（或外部提供的Comparator）进行迭代。此外，它实现了SortedMap接口，其中包含依赖于此排序顺序的方法。
• LinkedHashMap将按照将条目放入映射中的顺序进行迭代

“Hashtable”是基于哈希的映射的通用名称。在Java API的上下文中， Hashtable是Java 1.1时代之前集合框架存在的过时类。不应再使用它，因为它的API杂乱无章地复制了功能，并且它的方法是同步的（这可能会降低性能并且通常是无用的）。请使用ConcurrentHashMap代替Hashtable。

- Michael Borgwardt

---

Map是什么，它与HashMap和Hashtable有什么区别？ - Kevin

@theband：Map是一个接口。HashMap和Hashtable都实现了它；就像我之前写的，Hashtable是一个遗留类。 - Michael Borgwardt

Hashtable 和 HashMap 之间一个显著的区别是，在 Hashtable 中，“键”和“值”都不能为 null。而在后者中没有此限制。 - aioobe

是的 - 实际上这些是实现排序的标准方式。TreeMap有一个接受比较器的构造函数，如果没有提供比较器，则它期望所有添加的对象都实现了Comparable接口。 - Michael Borgwardt

您可以选择是否按照插入顺序或访问顺序迭代LinkedHashMap。 - lbalazscs

Answer 3

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

1. HashMap是基于键的哈希函数的映射，支持O(1)的获取/插入操作。为使其正常工作，键必须具有 hashCode()和equals()的一致实现。

2. LinkedHashMap与HashMap非常相似，但它添加了对添加（或访问）项目的顺序的意识，因此迭代顺序与插入顺序相同（或访问顺序，具体取决于构造参数）。

3. TreeMap是一种基于树的映射。其插入/获取操作需要O(log n)时间。它需要具有某种比较机制的项，可以使用Comparable或Comparator。迭代顺序由此机制确定。

- Eyal Schneider

---

如果我理解正确的话，LinkedHashMap和TreeMap之间唯一的区别在于性能，因为插入顺序与自然顺序相同？ - Moshe Shaham

如 #2 中所说，LinkedHashMap 会按照插入顺序迭代，而不是自然顺序。因此，如果您将 (2,5,3) 添加到 LinkedHashMap 中，并对其进行 for-each 循环，它将返回 2,5,3。如果添加到 TreeMap 中，则会返回 2,3,5。 - grinch

TreeMap 还有很多其他好用的技巧，比如头尾映射。 - Thomas Ahle

私有的TreeMap<String, Integer> mySection2 = new TreeMap<>(); mySection2.put("abc1", 2); mySection2.put("abc2", 5); mySection2.put("abc3", 3);for (Integer x: mySection2.values()) { Log.e("LOG", "TreeMap====" + x); }这给了我与插入项相同的顺序？请建议它与LinkedHashMaps有何不同？ - B.shruti

@B.shruti：这是因为您的插入顺序与键的字典顺序匹配（“abc1”，“abc2”，“abc3”）。如果您以不同的顺序插入，您的代码仍将按照字典顺序进行迭代。 - Eyal Schneider

谢谢您的回答，基本上我理解树和链式哈希映射之间的区别在于，链式哈希映射会按照插入顺序迭代值，而树映射会根据“键”的自然排序/字典/排序顺序迭代值，而不是按值排序。 - B.shruti

Answer 4

请看下面的图表，了解每个类在类层次结构中的位置（更大的图片）。TreeMap实现了SortedMap和NavigableMap，而HashMap没有。 HashTable已经过时，应该使用相应的ConcurrentHashMap类。

- pierrotlefou

---

这个图解非常棒，回答得很好。 - ThinkTank

Answer 5

HashMap

• 它具有键值对(keys,values)
• 不允许键重复的值
• 无序未排序
• 允许一个空键和多个空值

Hashtable

• 与哈希映射相同
• 不允许空键和空值

LinkedHashMap

• 它是有序的Map实现版本
• 基于链表和哈希数据结构

TreeMap

• 有序和排序版本
• 基于哈希数据结构

- Prem Kumar

---

HashTable也是同步的。总之，我喜欢你的答案，简洁清晰。 - Surasin Tancharoen

Answer 6

根据我的经验，以下是我在何时使用不同的地图：

• HashMap - 在需要高性能（快速）实现时最有用。
• TreeMap（SortedMap接口）- 当我关心能够按我定义的特定顺序对键进行排序或迭代时最有用。
• LinkedHashMap - 结合了从TreeMap保证排序的优点，而又不像维护TreeMap那样成本增加（它几乎和HashMap一样快）。特别是，LinkedHashMap还提供了创建缓存对象的良好起点，通过覆盖removeEldestEntry() 方法。这让您可以创建一个可以使用您定义的某些标准过期数据的缓存对象。

- Ogre Psalm33

---

准确来说，TreeMap 并不会按顺序保存元素，它是按照键的顺序进行排序。 - Mr. Lance E Sloan

Answer 7

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

HashMap

1. HashMap 基于键存储值。

2. 它只包含唯一元素。

3. 它可能有一个空键和多个空值。

4. 它不维护任何顺序。

   public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable

LinkedHashMap

1. LinkedHashMap 包含基于键的值。
2. 它只包含唯一元素。
3. 它可以有一个 null 键和多个 null 值。

4. 它与 HashMap 相同，但保留插入顺序。 //请参见下面的类声明

   public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>

TreeMap

1. TreeMap 包含基于键的值。它实现了 NavigableMap 接口并扩展了 AbstractMap 类。
2. 它只包含唯一的元素。
3. 它不能有空键，但可以有多个空值。

4. 它与 HashMap 相同，但维护升序（使用其键的自然顺序进行排序）。

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

Hashtable

1. Hashtable是一个列表数组，每个列表称为bucket。通过调用hashcode()方法来确定bucket的位置。Hashtable根据key存储值。
2. 它只包含唯一元素。
3. 可能没有任何null键或值。
4. 它是同步的。

5. 它是一个遗留类。

   public class Hashtable<K,V> extends Dictionary<K,V> implements Map<K,V>, Cloneable, Serializable

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

- roottraveller

---

请看这里 - https://dev59.com/jHNA5IYBdhLWcg3wL62x#1055337 - roottraveller

@HaakonLøtveit 我也建议在这里查看实际代码 - http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/HashMap.java#HashMap - roottraveller

仍然表示在最坏情况下它是O(n)。这是一个数学概念，除非它实际上是O(1)，否则你不能说它是O(1)。你还假设了一些非常好的哈希函数。我的意思是，我们可以使用像class TerribleHashKey {@Override hashCode() { return 4; /* Determined by fair dice throw */ }}这样的东西作为其他有趣的东西的键。具有O(1)的高概率和O(1)不是相同的。人们来这里寻求作业帮助。让我们不要毁掉他们的成绩.. ;) - Haakon Løtveit

@HaakonLøtveit 上述复杂度是针对Java库中经过优化的哈希函数。当然，我们可以假设一个初学者程序员总是可以编写类似于 public int hashCode() { return 4; } 的代码来实现O(N)的哈希函数。 - roottraveller

Daniel James谈论的是小o符号，而不是大O符号。因此它并不是非常相关。此外，当您承认程序员可以随意打破哈希函数的速度，将其降级为O(n)或O(log(n))（取决于Java的版本），那么您就不能再声称O(1)了。如果您说“平均情况”，我会完全同意您的观点。 :-) - Haakon Løtveit

Answer 8

HashMap不能保证迭代顺序, 当添加新元素时，迭代顺序甚至可以完全改变。TreeMap将根据键的compareTo()方法（或外部提供的Comparator）的“自然排序”进行迭代。此外，它实现了SortedMap接口，其中包含依赖于该排序顺序的方法。LinkedHashMap将按照将条目放入映射中的顺序进行迭代。

查看性能变化情况... TreeMap是SortedMap的一种实现。由于自然排序，put、get和containsKey操作的复杂度为O(log n)。

- Ruchira Gayan Ranaweera

---

谢谢，LinkedHashMap的“O(1)维护顺序的开销”确实有道理，但您是否有更详细的解释参考资料？ - ericn

Answer 9

@Amit: SortedMap是一个接口，而TreeMap是实现了SortedMap接口的类。这意味着它遵循SortedMap要求其实现者执行的协议。 除非实现为搜索树，否则树无法提供有序数据，因为树可以是任何类型的树。因此，为了使TreeMap按排序顺序工作，它实现了SortedMap（例如，二叉搜索树-BST，平衡BST如AVL和R-B Tree，甚至三叉搜索树-大多用于以排序方式进行迭代搜索）。

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

简述：

HashMap : 平均时间复杂度为 O(1) ，无序的

TreeMap : 平均时间复杂度为 O(log N)，以2为底数，有序的

LinkedHashMap : 带有链表的哈希表（类似于索引跳表），能够按照插入顺序存储数据。最适合实现 LRU （最近最少使用）。

- siddhusingh

Answer 10

哈希映射不会保留插入顺序。
例如，哈希映射如果插入键为

1  3
5  9
4   6
7   15
3   10

它可以将其存储为：

4  6
5  9
3  10
1  3
7  15

LinkedHashmap会保留插入顺序。

例如，如果您要插入键值对：

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

- Shivam Shukla