Java 使用 Steams VS TreeMap 对地图进行排序

Question

考虑以下 Java HashMap。Map<String, String> unsortMap = new HashMap<String, String>();unsortMap.put("Z", "z");unsortMap.put("B", "b");unsortMap.put("A", "a");unsortMap.put("C", "c");现在我想按键排序这个地图。一种选择是我为此目的使用 TreeMap。Map<String, String> treeMap = new TreeMap<String, String>(unsortMap);我的另一个选择是使用带有 Sorted() 的 Java Streams，如下所示。Map<String, Integer> sortedMap = new HashMap<>();unsortMap.entrySet()    .stream()    .sorted(Map.Entry.comparingByKey())    .forEachOrdered(x -> sortedMap.put(x.getKey(), x.getValue()));在这两个中，哪个选项是首选的，为什么（可能是在性能方面）？

Answer 1

正如其他人所指出的那样，将排序的条目流转储到常规HashMap中不会做任何事情......LinkedHashMap是合乎逻辑的选择。

但是，上述方法的替代方法是充分利用 Stream CollectorsAPI。

Collectors有一个toMap方法允许您为Map. HashMap因此，您可以要求这样，而不是 a LinkedHashMap：

unsortedMap.entrySet()

    .stream()

    .sorted(Map.Entry.comparingByKey())

    .collect(Collectors.toMap(

       Map.Entry::getKey,

       Map.Entry::getValue,

       (v1, v2) -> v1, // you will never merge though ask keys are unique.

       LinkedHashMap::new

    ));

在使用 TreeMap 与 LinkedHashMap 之间......构造的复杂性可能与 O(n log n) 相同......显然，TreeMap如果您打算继续向其中添加更多元素，则该解决方案是一种更好的方法......我想TreeMap在这种情况下你应该从 a 开始。该LinkedHashMap选项的优点是，在 Linked 或原始未排序的地图上查找将是 O(1)，而 TreeMap 就像O(log n)这样，如果您需要保留未排序的地图以进行高效查找，而在您构建 LinkedHashMap您可以扔掉原始未排序的地图（从而节省一些内存）。

为了使事情变得更有效率，LinkedHashMap您应该在构造时提供所需大小的良好估计器，这样就不需要动态调整大小，所以不要LinkedHashMap::new说() -> new LinkedHashMap<>(unsortedMap.size()).

我认为 a 的使用TreeMap更简洁......因为可以使代码更小，所以除非存在可以使用未排序和排序的链接地图方法解决的实际性能问题，否则我将使用Tree.

Answer 2

您的流代码甚至不会对地图进行排序，因为它正在对 a 执行操作HashMap，而 a 本质上是未排序的。为了使您的第二个流示例正常工作，您可以使用LinkedHashMap，它维护插入顺序：

Map<String, Integer> sortedMap = new LinkedHashMap<>();

unsortMap.entrySet()

    .stream()

    .sorted(Map.Entry.comparingByKey())

    .forEachOrdered(x -> sortedMap.put(x.getKey(), x.getValue()));

但是现在您的两个示例甚至都不是相同的底层数据结构。ATreeMap背靠一棵树（如果我没记错的话是红黑色）。TreeMap如果您希望能够以排序方式进行迭代，或者快速搜索键，您将使用 a 。ALinkedHashMap是带有一个链表的哈希图。如果您需要维护插入顺序，例如在实现队列时，您将使用它。

Answer 3

第二种方式不起作用，当您调用时HashMap#put，它不持有看跌订单。你可能需要LinkedHashMap.

TreeMap vs Stream（LinkedHashMap）：

1. 代码风格。使用 TreeMap 更简洁，因为您可以在一行中实现它。

2. 空间复杂度。如果原图是HashMap，两种方法都需要新建一个Map。如果如果原始地图是LinkedHashMap，那么您只需要Map使用第一种方法创建一个新地图。您可以重新使用LinkedHashMap第二种方法。

3. 时间复杂度。它们都应该有 O(nln(n))。