From: "David G. Andersen" <dga@...>
Date: 2004-12-04T04:09:12+09:00
Subject: Re: ordered hash ?

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.

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.

  -Dave

-- 
work: dga@lcs.mit.edu                          me:  dga@pobox.com
      MIT Laboratory for Computer Science           http://www.angio.net/