TreeMap、HashMap和LinkedHashMap的性能表现？

Question

TreeMap、HashMap和LinkedHashMap的性能表现？

8

在TreeMap中，元素是排序的；在HashMap中，元素是无序的。因此，如果我考虑使用get、put和remove方法，应该选择哪个映射以获得更好的性能？

- Vicky

1

请查看Javadoc文档。HashMap被指定为O(1)：基本操作（get和put）具有常数时间性能，假设哈希函数将元素适当地分散在桶中。TreeMap被指定为保证log(n)时间成本用于containsKey、get、put和remove操作。 - user207421

不知道您评估哪个选项更好的标准，回答这个问题是不可能的。显然，如果您只需要一个排序的集合，那么只有 TreeMap 可以胜任。但您已经知道了这一点。 - Raedwald

1

这里讲得相当详细：HashMap、LinkedHashMap和TreeMap的区别。 - nawfal

被接受的答案说HashMap更快。但是LinkedHashMap（Java 8）的Javadocs说它的迭代速度比HashMap要快得多。因此，根据您的具体标准，可能会有所不同。除非需要排序，否则绝对不要使用TreeMap，并使用LinkedHashMap来保留插入顺序。 - Lambart

3个回答

0

这取决于你的映射中键的哈希和比较函数有多快。这取决于你更关心平均情况性能还是最坏情况性能。这取决于你是否对映射的键应用了一个好的哈希函数；哈希值应该在哈希函数的域上分布良好（是的，它可能取决于你的数据）。

一般来说（当你不想测试时），哈希映射通常是一个很好的答案，但如果你没有成千上万的条目，它也不太可能产生很大的差异（对于小尺寸，"vec map" 也可以很好地工作）。

- dhardy

0

关于迭代的意图而言，取决于：

HashMap 对此不做保证，这意味着它是随机的；
TreeMap 使用自然顺序或指定的比较器来进行排序；
LinkedHashMap 按插入顺序迭代。

此外，对于 put/get/remove/containsKey 的时间复杂度：

HashSet - O(1)；
TreeMap - O(log(n)) 或 O(1)；-- 请参见参考资料！
LinkedHashSet - O(1)。

Geekforgeeks:

https://www.geeksforgeeks.org/differences-treemap-hashmap-linkedhashmap-java/

StackOverflow：

HashMap、LinkedHashMap 和 TreeMap 的区别

- JoaoFCarvalho

1

你所有的参考资料都表明TreeMap的时间复杂度是O(log n)。那么O(1)从哪里来的？ - General Grievance

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Keith Randall · Accepted Answer

除非你需要排序，否则请使用HashMap。 HashMap 更快。

话虽如此，您可以通过将通用接口用作声明来轻松切换：

 Map<String,String> M = new HashMap<String,String>();
 ...use M lots of places...

接下来你只需要调整一个位置，你的代码就可以使用新的地图类型。

编辑：

一个简单的时间测试：

import java.util.*;
class TimingTest {
  public static void main(String[] args) {
    Map<String,String> M = new HashMap<String,String>();
    long start = System.currentTimeMillis();
    for (int i = 0; i < 100000; i++) {
      M.put(Integer.toString(i), "foo");
    }
    long end = System.currentTimeMillis();
    System.out.println(end - start);
  }
}