Path: csiph.com!usenet.pasdenom.info!weretis.net!feeder4.news.weretis.net!eternal-september.org!feeder.eternal-september.org!mx04.eternal-september.org!.POSTED!not-for-mail
From: David Lamb <dalamb@cs.queensu.ca>
Newsgroups: comp.lang.java.programmer
Subject: Re: SortedMap question?
Date: Sun, 25 Nov 2012 08:59:05 -0500
Organization: A noiseless patient Spider
Lines: 11
Message-ID: <k8t87f$rsq$2@dont-email.me>
References: <k8rkud$i3o$1@dont-email.me> <q4qoyde15lpk$.13amx8nbfrj28.dlg@40tude.net> <k8t7l5$l22$2@dont-email.me>
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Sun, 25 Nov 2012 13:59:11 +0000 (UTC)
Injection-Info: mx04.eternal-september.org; posting-host="7f42270a997e580902d19031af10867c"; logging-data="28570"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/tc8bUa4M9OuFYeAq43bh8"
User-Agent: Mozilla/5.0 (Windows NT 5.1; rv:16.0) Gecko/20121026 Thunderbird/16.0.2
In-Reply-To: <k8t7l5$l22$2@dont-email.me>
Cancel-Lock: sha1:FZfja6dqRysoZVlEH8dqm+ic8MM=
Xref: csiph.com comp.lang.java.programmer:19935

On 25/11/2012 8:49 AM, David Lamb wrote:
> On 24/11/2012 6:57 PM, Joerg Meier wrote:
>> Assuming you used HashMap, as far as I recall, its get(x) performance is
>> already at O(1) unless you mess up your hashcodes. Doesn't really go
>> lower.
>
> The constant factors can matter a lot. 100 > 1 even though both are O(1).

Which, sigh, of course they're not, as Arne pointed out. O(logN) for 
SortedMap, as I should have immediately picked up on from the name alone.