in reply to Re^5: What makes an array sorted and a hash unsorted?
in thread What makes an array sorted and a hash unsorted?

You cannot speak generally of the intrinsic sequence of the elements of a hash. It is not a fixed quantity
It most certainly is. Each hash element is mapped to a bucket using a fixed function: hash(key,seed,nr_of_bufs). key is the key to be hashed, seed is fixed at program start, and nr_of_bufs is the current number of buffers used. But there's no randomness involved in the hash function. Given the same input parameters, the result will always be the same. It's a deterministic function. Arrays can be seen as a special case, where the "hash" function is just sub hash {0+$_[0]}.

Replies are listed 'Best First'.
Re^7: What makes an array sorted and a hash unsorted?
by herveus (Prior) on Jun 03, 2009 at 18:33 UTC
    Howdy!

    You are missing the point.

    In general, a Perl hash with a given set of keys will produce them in a consistent order when you call keys(). Calling keys() makes the set of keys into a list. That list is inherently ordered, but it's not the hash.

    Now, add or delete elements from the hash. There is no assurance that the list returned by keys() will be in the same order. In fact, insertions can change the order of keys that existed before. The set of keys in a hash has no deterministic fixed order. Change the insertion order and the keys come out in a different order. Consider the following: 

    my @hash_keys = qw/foo bar baz quux w x y z/;
my %foo;
my %bar;

for my $key (@hash_keys)
{
    $foo{$key} = 1;
    print "$key: ", join(':', keys %foo), "\n";
}
for my $key (reverse @hash_keys)
{
    $bar{$key} = 1;
    print "$key: ", join(':', keys %bar), "\n";
}

    [download]
    which produced the following output: 
    foo: foo
bar: bar:foo
baz: bar:baz:foo
quux: bar:baz:quux:foo
w: w:bar:baz:quux:foo
x: w:bar:baz:quux:x:foo
y: y:w:bar:baz:quux:x:foo
z: y:w:bar:baz:quux:x:foo:z
z: z
y: y:z
x: y:x:z
w: w:y:x:z
quux: w:y:quux:x:z
baz: w:y:baz:quux:x:z
bar: w:y:bar:baz:quux:x:z
foo: w:baz:x:y:bar:quux:foo:z

    [download]

    If there was an intrinsic sequence, why does adding "foo" to hash cause "x" to suddenly appear much earlier in the list produced by keys()? Why are the lists with all eight keys not the same? If the sequence were intrinsic, one would not expect either of those outcomes.

    yours,
    Michael
[reply]
[d/l]
[select]
      If there was an intrinsic sequence, why does adding "foo" to hash cause "x" to suddenly appear much earlier in the list produced by keys
      Which part of hash(key,seed,nr_of_bufs). key is the key to be hashed, seed is fixed at program start, and nr_of_bufs is the current number of buffers used did you fail to grasp?
[reply]

In Section Meditations