in reply to Hash Internals

The ordered hash structure uses three things: Thus: 
$orderedhash{$newkey} = $newvalue;
# is really doing

  $next_index = @KEYS;
  $KEYINDEX{$key} = $next_index;
  push @KEYS, $key;
  push @VALUES, $value;

$orderedhash{$oldkey} = $newvalue;
# is really doing

  $key_index = $KEYINDEX{$key};
  $VALUES[$key_index] = $value;

[download]
Deletions require splicing the two arrays, and then lowering the values in the %KEYINDEX hash. And if you want to allow for in-the-middle insertion, that requires splicing again, and raising the values in the hash.

This is obviously a slow structure and a slow process. It does not make for optimization. Hashes are designed so that keys can be looked up quickly, and Perl's hash structure might change soon to make Perl realize that a non-existent key isn't in the hash sooner (that's good).

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

Replies are listed 'Best First'.
RE: Re: Hash Internals
by d_i_r_t_y (Monk) on Oct 23, 2000 at 02:22 UTC
    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'?

[reply]
      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]

In Section Seekers of Perl Wisdom