From: Charles Mills <cmills@...>
Date: 2004-12-03T01:28:39+09:00
Subject: Re: ordered hash ?

On Dec 2, 2004, at 7:59 AM, Glenn Parker 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?

I think an ordered hash typically keeps track of the insertion order.  
So you basically have two ways of accessing elements - by the order of 
insertion (index?) and the hash key.

>   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.
>
Yeah.  Seems like you have to have an array or linked list combined 
with a hash table to make this work.
Here is one way to do it:

Have a hash table which maps hash keys to insertion indices like so 
(note: key.hash #=> hash key):
Hash Table: { hash key => insertion index, hash key => insertion index }

Then an array, indexed by insertion order which contains key, value 
pairs.
Array: [ [ key, value ], [key, value] ]

So to find an element you generate its hash key from the given key.  
Then get the insertion index from the hash table (may be the wrong 
insertion index), if it exists.  Check to make sure it is the right 
insertion index by comparing the key at the insertion index to the key 
you were given.  If it is then you return the value, if it isn't the 
either the hash doesn't contain that key or it is deeper in the hash 
bucket.

You don't have to do it the way described above, but it has some 
advantages.  The main one being you can go both ways insertion index => 
key and key => insertion index.  This is a very useful property.  The 
other big advantage is iteration is very fast.  You have everything you 
need for any type of iteration in the array - the key, the value, and 
the insertion index.

> 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.

You could also include a reorder function, it would be kind of 
expensive, but it is possible because you can go both ways insertion 
index <=> key.

> SkipList and related patterns impose an external sort-ordering on the 
> hash elements, so they would not suit Austin's requirements.
>

-Charlie