Java HashMap、LinkedHashMap 和 TreeMap 的区别

Difference between HashMap, LinkedHashMap and TreeMap

提问by Kevin

What is the difference between HashMap, LinkedHashMapand TreeMapin Java? I don't see any difference in the output as all the three has keySetand values. What are Hashtables?

Java 中的HashMap,LinkedHashMap和 有什么区别TreeMap？我没有看到输出有任何区别，因为所有三个都有keySet和values。什么是Hashtables？

Map 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 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 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());

采纳答案by Michael Borgwardt

All three classes implement the Mapinterface and offer mostly the same functionality. The most important difference is the order in which iteration through the entries will happen:

所有三个类都实现了Map接口并提供大致相同的功能。最重要的区别是通过条目进行迭代的顺序：

• HashMapmakes absolutely no guarantees about the iteration order. It can (and will) even change completely when new elements are added.
• TreeMapwill iterate according to the "natural ordering" of the keys according to their compareTo()method (or an externally supplied Comparator). Additionally, it implements the SortedMapinterface, which contains methods that depend on this sort order.
• LinkedHashMapwill iterate in the order in which the entries were put into the map

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

"Hashtable"is the generic name for hash-based maps. In the context of the Java API, Hashtableis an obsolete class from the days of Java 1.1 before the collections framework existed. It should not be used anymore, because its API is cluttered with obsolete methods that duplicate functionality, and its methods are synchronized (which can decrease performance and is generally useless). Use ConcurrentHashMapinstead of Hashtable.

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

回答by tangens

These are different implementations of the same interface. Each implementation has some advantages and some disadvantages (fast insert, slow search) or vice versa.

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

For details look at the javadoc of TreeMap, HashMap, LinkedHashMap.

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

回答by Eyal Schneider

All three represent mapping from unique keys to values, and therefore implement the Mapinterface.

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

1. HashMap is a map based on hashingof the keys. It supports O(1) get/put operations. Keys must have consistent implementations of hashCode()and equals()for this to work.

2. LinkedHashMap is very similar to HashMap, but it adds awareness to the order at which items are added (or accessed), so the iteration order is the same as insertion order (or access order, depending on construction parameters).

3. TreeMap is a tree based mapping. Its put/get operations take O(log n) time. It requires items to have some comparison mechanism, either with Comparable or Comparator. The iteration order is determined by this mechanism.

1. HashMap 是基于键散列的映射。它支持 O(1) 获取/放置操作。钥匙必须有一致的实现hashCode()，并equals()为此工作。

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

3. TreeMap 是一种基于树的映射。它的放置/获取操作需要 O(log n) 时间。它要求项目具有某种比较机制，无论是 Comparable 还是 Comparator。迭代顺序由该机制确定。

回答by siddhusingh

@Amit: SortedMapis an interface whereas TreeMapis a class which implements the SortedMapinterface. That means if follows the protocol which SortedMapasks its implementers to do. A tree unless implemented as search tree, can't give you ordered data because tree can be any kind of tree. So to make TreeMap work like Sorted order, it implements SortedMap ( e.g, Binary Search Tree - BST, balanced BST like AVL and R-B Tree , even Ternary Search Tree - mostly used for iterative searches in ordered way ).

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

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

In NUT-SHELL HashMap: gives data in O(1) , no ordering

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

TreeMap: gives data in O(log N), base 2. with ordered keys

TreeMap: 给出 O(log N) 中的数据，基数为 2. 带有有序键

LinkedHashMap: is Hash table with linked list (think of indexed-SkipList) capability to store data in the way it gets inserted in the tree. Best suited to implement LRU ( least recently used ).

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

回答by Prem Kumar

HashMap

哈希表

• It has pair values(keys,values)
• NO duplication key values
• unordered unsorted
• it allows one null key and more than one null values

• 它有对值（键，值）
• 没有重复的键值
• 无序 无序
• 它允许一个空键和多个空值

HashTable

哈希表

• same as hash map
• it does not allows null keys and null values

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

LinkedHashMap

链接哈希映射

• It is ordered version of map implementation
• Based on linked list and hashing data structures

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

TreeMap

树形图

• Ordered and sortered version
• based on hashing data structures

• 有序和排序版本
• 基于散列数据结构

回答by Ogre Psalm33

Just some more input from my own experience with maps, on when I would use each one:

只是从我自己的地图经验中获得更多输入，关于我何时使用每个地图：

• HashMap - Most useful when looking for a best-performance (fast) implementation.
• TreeMap (SortedMap interface) - Most useful when I'm concerned with being able to sort or iterate over the keys in a particular order that I define.
• LinkedHashMap - Combines advantages of guaranteed ordering from TreeMap without the increased cost of maintaining the TreeMap. (It is almost as fast as the HashMap). In particular, the LinkedHashMap also provides a great starting point for creating a Cache object by overriding the removeEldestEntry()method. This lets you create a Cache object that can expire data using some criteria that you define.

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

回答by Ruchira Gayan Ranaweera

HashMap makes absolutely not guarantees about the iteration order. It can (and will) even change completely when new elements are added. TreeMap will iterate according to the "natural ordering" of the keys according to their compareTo() method (or an externally supplied Comparator). Additionally, it implements the SortedMap interface, which contains methods that depend on this sort order. LinkedHashMap will iterate in the order in which the entries were put into the map

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

Look at how performance varying..

看看性能如何变化..

Tree map which is an implementation of Sorted map. The complexity of the put, get and containsKey operation is O(log n) due to the Natural ordering

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

回答by Sergii Shevchyk

I prefer visual presentation:

我更喜欢视觉呈现：

╔══════════════╦═════════════════════╦═══════════════════╦═════════════════════╗
║   Property   ║       HashMap       ║      TreeMap      ║     LinkedHashMap   ║
╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣
║ Iteration    ║  no guarantee order ║ sorted according  ║                     ║
║   Order      ║ will remain constant║ to the natural    ║    insertion-order  ║
║              ║      over time      ║    ordering       ║                     ║
╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣
║  Get/put     ║                     ║                   ║                     ║
║   remove     ║         O(1)        ║      O(log(n))    ║         O(1)        ║
║ containsKey  ║                     ║                   ║                     ║
╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣
║              ║                     ║   NavigableMap    ║                     ║
║  Interfaces  ║         Map         ║       Map         ║         Map         ║
║              ║                     ║    SortedMap      ║                     ║
╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣
║              ║                     ║                   ║                     ║
║     Null     ║       allowed       ║    only values    ║       allowed       ║
║ values/keys  ║                     ║                   ║                     ║
╠══════════════╬═════════════════════╩═══════════════════╩═════════════════════╣
║              ║   Fail-fast behavior of an iterator cannot be guaranteed      ║
║   Fail-fast  ║ impossible to make any hard guarantees in the presence of     ║
║   behavior   ║           unsynchronized concurrent modification              ║
╠══════════════╬═════════════════════╦═══════════════════╦═════════════════════╣
║              ║                     ║                   ║                     ║
║Implementation║      buckets        ║   Red-Black Tree  ║    double-linked    ║
║              ║                     ║                   ║       buckets       ║
╠══════════════╬═════════════════════╩═══════════════════╩═════════════════════╣
║      Is      ║                                                               ║
║ synchronized ║              implementation is not synchronized               ║
╚══════════════╩═══════════════════════════════════════════════════════════════╝

回答by pierrotlefou

See where each class is in the class hierarchy in the following diagram (bigger one). TreeMap implements SortedMapand NavigableMapwhile HashMapdoesn't.

在下图中查看每个类在类层次结构中的位置（较大的一个）。TreeMap 实现了SortedMap，NavigableMap而 whileHashMap没有。

HashTableis obsolete and the corresponding ConcurrentHashMapclass should be used.

HashTable已过时，ConcurrentHashMap应使用相应的类。

回答by Jitendra

All offer a key->value map and a way to iterate through the keys. The most important distinction between these classes are the time guarantees and the ordering of the keys.

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

1. HashMap offers 0(1) lookup and insertion. If you iterate through the keys, though, the ordering of the keys is essentially arbitrary. It is implemented by an array of linked lists.
2. TreeMap offers O(log N) lookup and insertion. Keys are ordered, so if you need to iterate through the keys in sorted order, you can. This means that keys must implement the Comparable interface.TreeMap is implemented by a Red-Black Tree.
3. LinkedHashMap offers 0(1) lookup and insertion. Keys are ordered by their insertion order. It is implemented by doubly-linked buckets.

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

Imagine you passed an empty TreeMap, HashMap, and LinkedHashMap into the following function:

假设您将一个空的 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 + ", ");
  }
}

The output for each will look like the results below.

每个的输出将类似于下面的结果。

For HashMap, the output was, in my own tests, { 0, 1, -1}, but it could be any ordering. There is no guarantee on the ordering.
Treemap,the output was,{ -1, 0, 1}
LinkedList,the output was,{ 1, -1, 0}

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