如何使用预先排序的数据初始化 TreeMap? [英] How to initialize a TreeMap with pre-sorted data?

问题描述

我的应用使用 TreeMap 来保持数据排序并进行日志(n)查找和插入.这在应用程序运行时的一般情况下效果很好，但是当应用程序第一次启动时，我需要用几百万个 long 来初始化 TreeMap，我得到了 sorted order(升序).

My app uses a TreeMap to keep data sorted and have log(n) lookups & inserts. This works great in the general case while the app is running, but when the app first starts, I need to initialize the TreeMap with several million longs that I get in sorted order (ascending).

由于这些初始化值已经排序，有没有办法将它们插入到 TreeMap 而无需支付树插入和重新平衡的 log(n) 成本?

Since these initialization values are already sorted, is there any way to insert them into the TreeMap without paying the log(n) cost of tree insertion and re-balancing?

推荐答案

好的！TreeMap.putAll 方法(以及采用 SortedMap 的 TreeMap 构造函数)调用名为 buildFromSorted 内部，在文档中描述为:线性时间从排序的数据中构建树算法"，所以这听起来像是你想要的.

Sure! The TreeMap.putAll method (and the TreeMap constructor that takes a SortedMap) calls a method called buildFromSorted internally, which is described in the docs as: "Linear time tree building algorithm from sorted data", so that sounds like it does what you want.

只需给 putAll 方法提供一些实现 Map 的东西，但是 map 的 entryset 迭代器 (Map.entrySet().iterator()) 返回您的排序值列表.

Just give the putAll method something that implements Map, but where the map's entryset iterator (Map.entrySet().iterator()) returns your list of sorted values.

这篇关于如何使用预先排序的数据初始化 TreeMap?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！