Path: csiph.com!usenet.pasdenom.info!gegeweb.org!eternal-september.org!feeder.eternal-september.org!mx04.eternal-september.org!.POSTED!not-for-mail
From: Knute Johnson <nospam@rabbitbrush.frazmtn.com>
Newsgroups: comp.lang.java.programmer
Subject: Re: SortedMap question?
Date: Sun, 25 Nov 2012 16:25:02 -0800
Organization: A noiseless patient Spider
Lines: 28
Message-ID: <k8ucsh$o2v$1@dont-email.me>
References: <k8rkud$i3o$1@dont-email.me> <q4qoyde15lpk$.13amx8nbfrj28.dlg@40tude.net> <k8t8dp$tv5$1@dont-email.me> <k8tljj$6jr$1@localhost.localdomain>
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Mon, 26 Nov 2012 00:24:49 +0000 (UTC)
Injection-Info: mx04.eternal-september.org; posting-host="2a29520862ca1452f67bbecd210d65dc"; logging-data="24671"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+xUTx/mwTY01Q/BCSOTSXv"
User-Agent: Mozilla/5.0 (Windows NT 6.2; WOW64; rv:16.0) Gecko/20121026 Thunderbird/16.0.2
In-Reply-To: <k8tljj$6jr$1@localhost.localdomain>
Cancel-Lock: sha1:IuOLx9JSn7lDt7LF3K3Av4311As=
Xref: csiph.com comp.lang.java.programmer:19965

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