如何使用预先排序的数据初始化TreeMap？

Question

我的应用程序使用TreeMap来保持数据排序并具有log(n)查找和插入.这在应用程序运行时的一般情况下效果很好,但是当应用程序首次启动时,我需要初始化具有数百万个long的TreeMap,我按排序顺序(升序).

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

Answer 1

当然!该TreeMap.putAll方法(以及采用SortedMap的TreeMap构造函数)调用一个名为buildFromSortedinternal 的方法,该方法在文档中描述为:"来自排序数据的线性时间树构建算法",这样听起来就像它所做的那样.

只需给出putAll实现Map 的方法,但是map的entryset iterator(Map.entrySet().iterator())返回排序值列表.