From: "Brian Schröder" <ruby@...>
Date: 2004-12-03T02:16:17+09:00
Subject: Re: ordered hash ?

On Fri, 3 Dec 2004 00:59:29 +0900
Glenn Parker <glenn.parker@comcast.net> wrote:

> Austin Ziegler wrote:
> > On Thu, 2 Dec 2004 23:37:34 +0900, Nikolai Weibull
> >>
> >>Having an ordered Hash is like saying that arrays should be indexed by
> >>strings--it's simply not what they are meant to be.
> > 
> > Be that as it may, it is still necessary to have an insertion-ordered
> > hash-like object.
> > 
> > I use it in PDF::Writer for page objects that can be referred to
> > meaningfully -- but still render in the order in which they were
> > inserted.
> 
> How is an "OrderedHash" different from something we might call a 
> "HashedArray", i.e. an array where elements also have a string-like 
> address?  With this hybrid type, the array-ness and the hash-ness are 
> orthogonal and neither takes precedence.  To me, this says that the only 
> solution (that can maintain an arbitrary ordering) is something like 
> Michael's two-layered implementation, where a hash and an array both 
> refer to the same set of objects internally.  Hashing destroys ordering, 
> so you have to pay for it somewhere else.
> 
> A more flexible altnerative to Michael's OrderedHash implementation 
> might embed an index within each element, or maintain a parallel hash 
> with indices, then sort the elements by index on demand.  If you access 
> the elements in sorted order infrequently, this might be a win for 
> performance.
> 
> SkipList and related patterns impose an external sort-ordering on the 
> hash elements, so they would not suit Austin's requirements.
> 

Why is everybody in this thread so fixed on using array and hash. As I see it
the requirements are:

insert(k1, k2, value)
delete_by_k1(k1, value)
delete_by_k2(k2, value)
get_by_k1(k1)
get_by_k2(k2)
each_by_k1

and maybe things like delete_min etc. Any datastructure that fullfills these
purposes fits. If I can construct one by using an Array and a Hash thats good,
but if I can achieve this using a fibonaccy heap or a skiplist or something
else that should not matter.

Maybe we should first get the specifications right? (Austin, what exactly are
your needs, have I hit them more or less?)

kind regards,

Brian

-- 
Brian Schr�der
http://www.brian-schroeder.de/