From: Robert Klemme <bob.news@...>
Date: 2004-12-07T21:12:32+09:00
Subject: Re: ordered hash ?


"David G. Andersen" <dga@lcs.mit.edu> schrieb im Newsbeitrag
news:20041203190828.GA23305@lcs.mit.edu...
> On Fri, Dec 03, 2004 at 11:59:24PM +0900, David A. Black scribed:
> >
> > Right, just to the extent that a Hash is Ordered in the first place.
> > (I had the feeling Matz was considering having all of them be ordered,
> > but that may be wrong and/or a different matter.)
>
>   The point is that a hash ordered by insertion order is pretty
> easy to maintain.  Your hash table changes from something like:
>
>   hash_item *hash_table;
>
> where:
>
>   struct hash_item {
>     something *item_ref;
>   }
>
>   update(new_item) {
>     /* Yes, yes, you have to do some kind of chaining or
>      * whatever.. but you understand the point here. :) */
>     hash_table[  hash_of(new_item) ] = new_item;
>   }
>
> to:
>
>   hash_item *hash_table;
>   struct hash_item {
>     something *item_ref;
>     hash_item *prev, *next;
>   }
>   hash_item *head, *tail;
>
>   update(new_item) {
>     hash_table[  hash_of(new_item) ] = new_item;
>     new_item.prev = tail;
>     tail = new_item;
>   }
>
> And, as Nobu pointed out, all of the operations remain O(1),
> except, obviously, for each().  They do a little more work, but
> not exceedingly more.

Yeah, but space *can* be crucial sometimes.  So I'd vote for keeping the
current Hash as it is and maybe adding another class InsertionOrderedHash
(or whatever) that keeps insertion order.

> If you want to maintain by something other than insertion order,
> you have to sort things, which _would_ be likely to slow down the
> basic hash table.

I think for ordered maps usually some kind of tree implementation is
chosen, which naturally is a bit slower than a hash.  I think in Java and
C++ (STL) they use red-black-trees.

Kind regards

    robert