Loading 1 000 000 numbers takes 2 seconds to load into a treemap (binary search tree), but takes milliseconds to load into a hashmap (in java).
The only difference between the two is that I can see is I can set a hashmap's initial size so it does not constantly need to re-size.
Am I wrong to assume a TreeMap's array's initial size should be able to be set? Is there a different reason that it is so slow?
Is there a logical reason for why one cannot set TreeMap's, or any generic binary search tree's, size or is this wrong?
Unlike HashMap that re-allocates its internals as new ones get inserted, the TreeMap does not generally reallocate its nodes on adding new ones. The difference can be very loosely illustrated as that between an ArrayList and a LinkedList: the first re-allocates to resize, while the second one does not. That is why setting the initial size of a TreeMap is roughly as meaningless as trying to set the initial size of a LinkedList.
The speed difference is due to the different time complexity of the two containers: inserting N nodes into a HashMap is O(n), while for the TreeMap it's O(N*LogN), which for 1000000 nodes is roughly 20 times asymptotic difference. Although the difference in asymptotic complexity does not translate directly into the timing difference because of different constants dictated by the individual algorithms, it serves as a good way to decide which algorithm is going to be faster on very large inputs.