Path: csiph.com!newsfeed.hal-mli.net!feeder3.hal-mli.net!newsfeed.hal-mli.net!feeder1.hal-mli.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 15:28:11 +0100 Lines: 28 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 HS+5OG9iEzSP49E3djeAMwnFITq+C01BrClds1C7Pbg0b/sWSx8LXJbjbd23Ts9HY= Cancel-Lock: sha1:p/7p6P7aLV8lPVfX8z/b10VECJo= User-Agent: Mozilla/5.0 (Windows NT 6.0; WOW64; rv:16.0) Gecko/20121026 Thunderbird/16.0.2 In-Reply-To: Xref: csiph.com comp.lang.java.programmer:19941 On 25.11.2012 02:34, markspace wrote: > On 11/24/2012 3:23 PM, Knute Johnson wrote: >> 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? > > > What Robert said. Also HashMap might have to "grow" itself, resulting > re-inserting every single element already in the Map. I think TreeMap > has a more predictable O(ln n) insertion time for each insertion. > > I might be wrong about that: a balanced tree could resort itself pretty > heavily too on any given insertion. TreeMap uses a red black tree: http://docs.oracle.com/javase/6/docs/api/java/util/TreeMap.html It has some characteristics which according to my memory avoid the extreme rebalancing overhead of other binary trees: http://en.wikipedia.org/wiki/Red_black_tree Kind regards robert -- remember.guy do |as, often| as.you_can - without end http://blog.rubybestpractices.com/