Re: SortedMap question?
On 11/25/2012 09:47, Martin Gregorie wrote:
Or, if the key comparison is cheap, i.e. short strings or integer
comparisons, and the key population is very large TreeMap can become
attractive: with 8 million nodes you only need 23 comparisions to find a
miss. Growing the tree isn't too expensive either: rebalancing a balanced
red-black tree, which is necessary from time to time as it grows, is only
a matter of adjusting pointers.
That's what I thought, that the searching for a match would be very
quick once the data was in the TreeMap. The test code I wrote may not
have been any good. I created a map with Strings for the keys and
values. I could get about 2 million entries before I started running
into virtual memory issues slowing things down. I searched for
non-existent elements. Using both a HashMap and a TreeMap, the TreeMap
was significantly slower than the HashMap. I even tried a
ConcurrentHashMap and multiple threads to do the search to see if that
would speed things up. While that technique was better than TreeMap it
was still slower than a plain HashMap.
So for the actual case that I am working on, I have a collection of
about 5000 elements and am using an Integer as the key. Data is rarely
changed but often accessed. There should never be a case where the
searched for key will not exist. What would you use, a HashMap or a
TreeMap?
Thanks,
knute...