How to initialize a TreeMap with pre-sorted data?

Question

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).

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?

Quota

I would be very surprised if there is, personally. – Container

What is your 'initialization values' data structure? List? or HashMap? – Unsure

Answer 1

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.

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.

Laterality

Thanks, this is exactly what I needed, although it'll take some wrangling to turn my list of initialization numbers into something that looks like a SortedMap. – Quota

It might not actually. I edited the answer to say use LinkedHashMap -- you can just put your numbers in that in order, and the iterator will preserve the order you added them. – Laterality

LinkedHashMap doesn't implement the SortedMap interface, so I don't think the buildFromSorted method would be used. Instead, I had to create an anonymous implementation of SortedMap, an anonymous implementation of Set inside that, an anonymous implementation of iterator inside that and an anonymous implementation of Entry within that. Ugly and verbose as sin, but does the job. – Quota