Path: csiph.com!usenet.pasdenom.info!weretis.net!feeder1.news.weretis.net!feeder.erje.net!eu.feeder.erje.net!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail From: Robert Klemme Newsgroups: comp.lang.java.programmer Subject: Re: SortedMap question? Date: Sun, 25 Nov 2012 01:36:19 +0100 Lines: 23 Message-ID: References: Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Trace: individual.net YEAvj3f4ctxrIkf7h/gjzwXSTHSgBs7MKDQZZZgGKOYBh+MegakRVXHosybtx+68Y= Cancel-Lock: sha1:b9gzwfcH0LwxRojj09PHmC9CVG8= User-Agent: Mozilla/5.0 (X11; Linux i686; rv:17.0) Gecko/17.0 Thunderbird/17.0 In-Reply-To: Xref: csiph.com comp.lang.java.programmer:19912 On 11/25/2012 12:23 AM, Knute Johnson wrote: > I have been operating under a mis-perception that a SortedMap would be > more quickly searched than an unsorted Map. More specifically that the > cost would come when adding an element to the SortedMap. I wrote a > little test program to measure the amount of time it took to look for > non-existent data in a Map and a SortedMap and it took somewhere between > twice and three times as long to look for the data in the SortedMap. The TreeMap is a tree implementation and you typically have O(log n) for insertion and lookup operations. For a HashMap it's O(1) - as has been stated already. So the expectation would be for the TreeMap to be slower - at least asymptotically. > So am I know correct in thinking that the only real advantage of a > SortedMap is if you wish to iterate over the keys of the map in some order? SortedMap also supports creation of various sub sets of the map based on the key order as well as access to the min and max keys. The JavaDoc is pretty comprehensive. Kind regards robert