From: Charles O Nutter Date: 2006-07-26T05:03:50+09:00 Subject: Re: Hash order bug? ------=_Part_178977_26786075.1153857825231 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Content-Disposition: inline On 7/25/06, Keith Gaughan wrote: > > On Wed, Jul 26, 2006 at 03:50:05AM +0900, William James wrote: > > > What language has ordered hashes? > > Java, in the form of the TreeMap collection. The usefulness of them is > limited though, As anecdotal evidence, I've used it twice in the past > four years. > And even in the TreeMap case, you sacrifice performance for features. An unordered hash will be the fastest for lookup and insertion. Adding any additional features will slow it down out of the necessity of imposing an order on either keys or values. With TreeMap, I think it's something like O(log n) lookup times rather than the theoretical O(1) with a straight hash, and that's not counting any tree rebalancing needed after future insertions. At minimum, you'll double up memory storing an array and a hash together, or you'll sacrifice performance maintaining and traversing a balanced tree. Leave hash alone; custom data structures are fine when the peculiar beast known as an "ordered hash" is actually useful. -- Charles Oliver Nutter @ headius.blogspot.com JRuby Developer @ www.jruby.org Application Architect @ www.ventera.com ------=_Part_178977_26786075.1153857825231--