in reply to Re: Hash Internals
in thread Hash Internals

what is wrong with an implementation that just uses a hash and a list to keep the order of keys? FETCH-ing should be faster (a single hash lookup); STORE-ing \ would be faster (only replace the hash value), KEYS would be the same, VALUEs would be a little slower, EACH also slightly slower...

i guess the big question is whether given an existing key-value, does replacing that key's value keep its original position or does it move to the 'end'?

Replies are listed 'Best First'.
RE: RE: Re: Hash Internals
by japhy (Canon) on Oct 23, 2000 at 02:31 UTC
    That's ok for a limited design, where you'll only be adding to the front or back.

    $_="goto+F.print+chop;\n=yhpaj";F1:eval
[reply]
      how so?

      replacing an existing value would be simply: 

      $my_ordered_hash{$old_key} = $newvalue;

      [download]
      would be implemented as: 
      sub STORE
{
    my( $this, $key, $val ) = @_;
    if ( exists( $this->{hash}->{$key} ) )
    {
        $this->{hash}->{$key} = $val;
    }
    else
    {    $this->{hash}->{$key} = $val;
        push @{$this->{order}}, $key; 
    }    
}

      [download]
      ...since replacing a value for an existing key should not (in this case) change its order. if you did want this behaviour ie STOREing a value *always* appends to the end, then the performance of STOREing with this implementation gets a little ugly -- O(n), for the array scan.

      the only really messy problem with this implementation is DELETEing - since that requires array scanning and splicing.

      is there any other complications?

[reply]
[d/l]
[select]
        That's not adding a k-v pair. I'd said adding to front or back. Even adding to the FRONT is a bit edgy, since using unshift() a lot can be icky.

        $_="goto+F.print+chop;\n=yhpaj";F1:eval
[reply]

In Section Seekers of Perl Wisdom