考虑以下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");
现在我想按键对这张地图进行排序。一种选择是我为此目的使用树状图。
Map<String, String> treeMap = new TreeMap<String, String>(unsortMap);
另一个选择是将Java Streams与Sorted()一起使用,如下所示。
Map<String, Integer> sortedMap = new HashMap<>();
unsortMap.entrySet()
.stream()
.sorted(Map.Entry.comparingByKey())
.forEachOrdered(x -> sortedMap.put(x.getKey(), x.getValue()));
在这两个选项中,哪个选项是首选,为什么(可能是在性能方面)?
谢谢
正如其他人指出的那样,将排序后的条目流转储到常规HashMap
将无济于事......LinkedHashMap
是合乎逻辑的选择。
但是,上述方法的替代方法是充分利用流Collectors
API。
Collectors
有一个toMap
方法,允许您为Map
提供替代实现。因此,您可以要求这样的LinkedHashMap
,而不是HashMap
:
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
));
在使用树状图与链接哈希图之间...构造的复杂性可能与 O(n log n) 相同...显然,如果您打算继续向其添加更多元素,那么TreeMap
解决方案是一种更好的方法......我想在这种情况下,你应该从TreeMap
开始。LinkedHashMap
选项的优点是查找将在链接或原始未排序的地图上为 O(1),而树状图的类似于O(log n)
所以如果您需要保留未排序的地图以进行高效查找,而如果您构建 LinkedHashMap,您可以扔掉原始未排序的映射(从而节省一些内存)。
为了使LinkedHashMap
更有效率,您应该在构造时提供所需大小的良好估计器,这样就不需要动态调整大小,因此您LinkedHashMap::new
说() -> new LinkedHashMap<>(unsortedMap.size())
。
我认为使用TreeMap
更整洁...保持代码较小,因此除非存在可以使用未排序和排序的链接映射方法解决的实际性能问题,否则我会使用Tree
.
您的流代码甚至不会对映射进行排序,因为它正在对本质上未排序的HashMap
执行操作。 要使第二个流示例正常工作,您可以使用LinkedHashMap
,它保持广告顺序:
Map<String, Integer> sortedMap = new LinkedHashMap<>();
unsortMap.entrySet()
.stream()
.sorted(Map.Entry.comparingByKey())
.forEachOrdered(x -> sortedMap.put(x.getKey(), x.getValue()));
但是现在你的两个例子甚至不是相同的底层数据结构。TreeMap
由一棵树支撑(如果我没记错的话,是红色黑色)。 如果您希望能够以排序方式进行迭代或快速搜索键,则可以使用TreeMap
。LinkedHashMap
是带有链表的哈希图。 如果您需要维护广告顺序(例如在实现队列时),则可以使用此功能。
第二种方式不起作用,当你调用HashMap#put
时,它不持有看跌订单。您可能需要LinkedHashMap
。
TreeMap v.s. Stream(LinkedHashMap):
- 代码样式。使用树状图更简洁,因为您可以在一行中实现它。
- 空间复杂性。如果原始地图是
HashMap
,则使用这两种方法都需要创建一个新的Map
。如果LinkedHashMap
原始地图,则只需使用第一种方法创建新Map
。您可以通过第二种方法重用LinkedHashMap
。 - 时间复杂度。它们都应该有 O(nln(n))。