HashMap、LinkedHashMap和TreeMap之间的区别。

What is the difference between HashMap, LinkedHashMap and TreeMap in Java? I don't see any difference in the output as all the three has keySet and values. What are Hashtables?

在Java中HashMap、LinkedHashMap和TreeMap有什么区别?我看不出输出有什么不同，因为这三个都有键集和值。哈希表是什么?

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

16 个解决方案

#1

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

这三个类都实现了Map接口，并且提供了几乎相同的功能。最重要的区别是迭代遍历条目的顺序:

• HashMap makes absolutely no guarantees about the iteration order. It can (and will) even change completely when new elements are added.
• HashMap对迭代顺序没有任何保证。当添加新元素时，它甚至可以(而且将)完全改变。
• 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.
• TreeMap将根据其compareTo()方法(或外部提供的比较器)根据键的“自然顺序”迭代。此外，它实现SortedMap接口，其中包含依赖于此排序顺序的方法。
• LinkedHashMap will iterate in the order in which the entries were put into the map
• LinkedHashMap将按照将条目放入映射的顺序进行迭代

"Hashtable" is the generic name for hash-based maps. In the context of the Java API, Hashtable is 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 ConcurrentHashMap instead of Hashtable.

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

#2

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               ║
╚══════════════╩═══════════════════════════════════════════════════════════════╝

#3

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

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

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

   HashMap是基于对键哈希的映射。它支持O(1) get/put操作。键必须具有hashCode()和equals()的一致实现才能工作。

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).

   LinkedHashMap与HashMap非常相似，但它增加了对添加(或访问)项的顺序的认识，因此迭代顺序与插入顺序(或访问顺序，取决于构造参数)相同。

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.

   TreeMap是一种基于树的映射。它的put/get操作需要O(log n)时间。它要求项目具有某种比较机制，可以是可比的，也可以是比较国的。迭代顺序由这个机制决定。

#4

See where each class is in the class hierarchy in the following diagram (bigger one). TreeMap implements SortedMap and NavigableMap while HashMap doesn't.

请查看下一个图(较大的一个)中每个类在类层次结构中的位置。TreeMap实现了SortedMap和NavigableMap，而HashMap则没有。

HashTable is obsolete and the corresponding ConcurrentHashMap class should be used.

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

#5

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.
• HashMap——在寻找最佳性能(快速)实现时最有用。
• 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.
• TreeMap (SortedMap接口)——当我考虑按我定义的特定顺序对键进行排序或迭代时，这是最有用的。
• 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.
• LinkedHashMap -结合了TreeMap的保证排序的优点，而不增加维护TreeMap的成本。(它几乎和HashMap一样快)。特别是，LinkedHashMap还通过覆盖removeEldestEntry()方法为创建缓存对象提供了一个很好的起点。这允许您创建一个缓存对象，该对象可以使用您定义的一些标准来过期数据。

#6

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
• 基于哈希数据结构

#7

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()方法(或外部提供的比较器)根据键的“自然顺序”迭代。此外，它实现了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)

#8

All three classes HashMap, TreeMap and LinkedHashMap implements java.util.Map interface, and represents mapping from unique key to values.

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

HashMap

HashMap

1. A HashMap contains values based on the key.

   HashMap包含基于键的值。

2. It contains only unique elements.

   它只包含唯一的元素。

3. It may have one null key and multiple null values.

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

4. It maintains no order.

   它不维护秩序。

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

   公共类HashMap 扩展AbstractMap 实现Map ， Cloneable, Serializable。 ,v> ,v> ,v>

LinkedHashMap

LinkedHashMap

1. A LinkedHashMap contains values based on the key.
2. LinkedHashMap包含基于密钥的值。
3. It contains only unique elements.
4. 它只包含唯一的元素。
5. It may have one null key and multiple null values.
6. 它可能有一个空键和多个空值。

7. It is same as HashMap instead maintains insertion order. //See class deceleration below

   它与HashMap相同，而是保持插入顺序。/ /请参见下面的类减速

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

   公共类LinkedHashMap 扩展HashMap 实现Map ,v> ,v> ,v>

TreeMap

TreeMap

1. A TreeMap contains values based on the key. It implements the NavigableMap interface and extends AbstractMap class.
2. TreeMap包含基于密钥的值。它实现NavigableMap接口并扩展AbstractMap类。
3. It contains only unique elements.
4. 它只包含唯一的元素。
5. It cannot have null key but can have multiple null values.
6. 它不能有空键，但可以有多个空值。

7. It is same as HashMap instead maintains ascending order(Sorted using the natural order of its key.).

   它与HashMap相同，而是保持升序(使用其键的自然顺序排序)。

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

   公共类TreeMap 扩展AbstractMap 实现NavigableMap ， Cloneable, Serializable。 ,v> ,v> ,>

Hashtable

哈希表

1. A Hashtable is an array of list. Each list is known as a bucket. The position of bucket is identified by calling the hashcode() method. A Hashtable contains values based on the key.
2. Hashtable是列表的数组。每个列表都被称为bucket。通过调用hashcode()方法确定bucket的位置。哈希表包含基于键的值。
3. It contains only unique elements.
4. 它只包含唯一的元素。
5. It may have not have any null key or value.
6. 它可能没有任何空键或值。
7. It is synchronized.
8. 它是同步的。

9. It is a legacy class.

   它是一个遗留类。

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

   公共类Hashtable 扩展字典 实现Map ， Cloneable, Serializable ,v> ,v> ,v>

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

裁判:http://javarevisited.blogspot.in/2015/08/difference-between-HashMap-vs-TreeMap-vs-LinkedHashMap-Java.html

#9

Let me put it simple:

简单来说:

• HashMap is implemented as a hash table, and there is no ordering on keys or values.
• HashMap是作为哈希表实现的，对键或值没有排序。
• TreeMap is implemented based on red-black tree structure, and it is ordered by the key.
• TreeMap是基于红黑树结构实现的，它是按键排序的。
• LinkedHashMap preserves the insertion order
• LinkedHashMap保存了插入顺序
• Hashtable is synchronized, in contrast to HashMap. It has an overhead for synchronization.This is the reason that HashMap should be used if the program is thread-safe.
• Hashtable是同步的，与HashMap相反。它有一个同步开销。这就是如果程序是线程安全的，HashMap应该被使用的原因。

#10

@Amit: SortedMap is an interface whereas TreeMap is a class which implements the SortedMap interface. That means if follows the protocol which SortedMap asks 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 ).

SortedMap是一个接口，而TreeMap是一个实现SortedMap接口的类。这意味着如果遵循SortedMap要求其实现者执行的协议。树除非实现为搜索树，否则不能为您提供有序数据，因为树可以是任何类型的树。为了让TreeMap像排序一样工作，它实现了SortedMap (e)。g，二叉搜索树- BST，平衡的BST，如AVL和R-B树，甚至三元搜索树-大多用于有序的迭代搜索)。

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:是具有链表(想想索引- skiplist)功能的哈希表，可以以插入到树中的方式存储数据。最适合实现LRU(最近最少使用)。

#11

Following are major difference between HashMap and TreeMap

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

1. HashMap does not maintain any order. In other words , HashMap does not provide any guarantee that the element inserted first will be printed first, where as Just like TreeSet , TreeMap elements are also sorted according to the natural ordering of its elements

   HashMap不维护任何顺序。换句话说，HashMap没有提供任何保证，插入的元素首先会被打印出来，就像TreeSet一样，TreeMap元素也根据元素的自然顺序进行排序。

2. Internal HashMap implementation use Hashing and TreeMap internally uses Red-Black tree implementation.

   内部HashMap实现使用散列，TreeMap内部使用红黑树实现。

3. HashMap can store one null key and many null values.TreeMap can not contain null keys but may contain many null values.

   HashMap可以存储一个空键和多个空值。TreeMap不能包含空键，但可以包含许多空值。

4. HashMap take constant time performance for the basic operations like get and put i.e O(1).According to Oracle docs , TreeMap provides guaranteed log(n) time cost for the get and put method.

   HashMap的基本操作(如get和put i)的时间性能是恒定的。e O(1)。根据Oracle docs, TreeMap为get和put方法提供了保证日志(n)时间成本。

5. HashMap is much faster than TreeMap, as performance time of HashMap is constant against the log time TreeMap for most operations.

   HashMap比TreeMap快得多，因为大多数操作的HashMap的性能时间与日志时间TreeMap是常量。

6. HashMap uses equals() method in comparison while TreeMap uses compareTo() method for maintaining ordering.

   HashMap使用equals()方法进行比较，而TreeMap使用compareTo()方法来维护排序。

7. HashMap implements Map interface while TreeMap implements NavigableMap interface.

   HashMap实现了Map接口，而TreeMap实现了NavigableMap接口。

#12

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。

#13

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. HashMap提供0(1)查找和插入。不过，如果对键进行迭代，键的顺序基本上是任意的。它由一个链表数组实现。
3. 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.
4. TreeMap提供O(log N)查找和插入。键是有序的，所以如果你需要按顺序遍历键，你可以。这意味着键必须实现可比较的接口。TreeMap由红黑树实现。
5. LinkedHashMap offers 0(1) lookup and insertion. Keys are ordered by their insertion order. It is implemented by doubly-linked buckets.
6. 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，- 1,0}

#14

Hash map doesn't preserves the insertion order.
Example. Hashmap If you are inserting keys as

哈希映射没有保留插入顺序。的例子。如果要插入键为as的Hashmap

1  3
5  9
4   6
7   15
3   10

It can store it as

它可以把它储存起来

4  6
5  9
3  10
1  3
7  15

Linked Hashmap preserves the insertion order.

链接Hashmap保留了插入顺序。

Example.
If you are inserting keys

的例子。如果是插入键。

1  3
5  9
4   6
7   15
3   10

It will store it as

它会把它储存起来

1  3
5  9
4   6
7   15
3   10

same as we insert.

当我们插入相同。

Tree map stores the vales in Increasing Order Of Keys. Example.
If you are inserting keys

树图通过增加键的顺序来存储vales。的例子。如果是插入键。

1  3
5  9
4   6
7   15
3   10

It will store it as

它会把它储存起来

1  3
3  10
4   6
5   9
7   15

#15

HashMap
can contain one null key.

HashMap可以包含一个空键。

HashMap maintains no order.

HashMap维护没有秩序。

TreeMap

TreeMap

TreeMap can not contain any null key.

TreeMap不能包含任何空键。

TreeMap maintains ascending order.

TreeMap维护升序排序。

LinkedHashMap

LinkedHashMap

LinkedHashMap can be used to maintain insertion order, on which keys are inserted into Map or it can also be used to maintain an access order, on which keys are accessed.

LinkedHashMap可以用于维护插入顺序(在该插入顺序上插入键)，也可以用于维护访问顺序(在该插入顺序*问键)。

Examples::

例子::

1) HashMap map = new HashMap();

1) HashMap = new 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();

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

3) LinkedHashMap =新的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());
    }

#16

• HashMap:

  HashMap:

  • Order not maintains
  • 为了不维护
  • Faster than HashMap and LinkedHashMap
  • 比HashMap和LinkedHashMap要快
  • Used for store heap of objects
  • 用于存储堆对象。

• LinkedHashMap:

  LinkedHashMap:

  • LinkedHashMap insertion order will be maintained
  • 将维护LinkedHashMap插入顺序。
  • Slower than HashMap and faster than TreeMap
  • 比HashMap慢，比TreeMap快
  • If you want maintain an insertion order use this.
  • 如果您希望保持插入顺序，请使用此命令。

• TreeMap:

  TreeMap:

  • TreeMap is a tree based mapping
  • TreeMap是一种基于树的映射
  • TreeMap will follow the natural ordering of key
  • TreeMap将遵循键的自然顺序。
  • Slower than HashMap and LinkedHashMap
  • 比HashMap和LinkedHashMap要慢
  • Use TreeMap when you need to maintain natural(default) ordering
  • 当您需要维护自然(默认)排序时使用TreeMap。