From: David Stokar Date: 2007-10-09T16:44:32+09:00 Subject: Re: Ordered Hashes in 1.9? ------=_Part_3501_18333305.1191915872521 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Content-Disposition: inline To clarify, the ordering is not on the key, but on the order of insertion. It's rather a HashQueue :-) David Stokar On 10/9/07, Eric Mahurin wrote: > > On 10/8/07, murphy wrote: > > David Flanagan wrote: > > > Is this an implementation detail, or is it part of the specification? > > If it becomes specification, we might want to add Array-style handling > > for Hash: > > > > * Hash#[] with a range or a start and a length > > I would guess that the implementation of the ordering is a linked > list, which has slow random access. > > A linked list would allow O(1) overhead for insert/delete and not hurt > other operations. The space overhead would be two pointers per key > (next and previous). > > ------=_Part_3501_18333305.1191915872521 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Content-Disposition: inline To clarify, the ordering is not on the key, but on the order of insertion. It's rather a HashQueue :-)

David Stokar

On 10/9/07, Eric Mahurin < eric.mahurin@gmail.com> wrote:
On 10/8/07, murphy < murphy@rubychan.de> wrote:
> David Flanagan wrote:
> > Is this an implementation detail, or is it part of the specification?
> If it becomes specification, we might want to add Array-style handling
> for Hash:
>
> * Hash#[] with a range or a start and a length

I would guess that the implementation of the ordering is a linked
list, which has slow random access.

A linked list would allow O(1) overhead for insert/delete and not hurt
other operations.  The space overhead would be two pointers per key
(next and previous).


------=_Part_3501_18333305.1191915872521--