CODEWITHSUNDEEP
perlhash
Oleg V. Volkov
Oleg V. Volkov

Reputation: 22461

Is it guaranteed anywhere in docs that hashes with same keys will also have same order?

There's not much guarantees about order of hash keys in Perl. Is there any mention in docs that I can't find that would say that as long as two hashes use exactly same keys, they will go in exactly same order?

Short test seems to confirm that. Even if I generate some additional keys for internal key table between assigning to two different hashes, their keys are returned in same order:

my %aaa;
my %bbb;
my %ccc;
my %ddd;

@aaa{qw(a b c d e f g h i j k l)}=();
# Let's see if generating more keys for internal table matters
@ccc{qw(m n o p q r s t u v w x)}=();
@bbb{qw(a b c d e f g h i j k l)}=();
# Just to test if different insertion order matters
@ddd{qw(l k c d e f g h i j a)}=(); $ddd{b} = ();

print keys %aaa, "\n";
print keys %bbb, "\n";
print keys %ddd, "\n";

However I wouldn't rely on udocumented behavior and only fact that can be easily found in docs is that keys, values and each all will use same order as long as hash is not modified.

Upvotes: 8

Views: 408

Answers (6)

Oleg V. Volkov
Oleg V. Volkov

Reputation: 22461

Since at least 5.18, following is explicitly mentioned in perldoc perlsec:

keys, values, and each return items in a per-hash randomized order. Modifying a hash by insertion will change the iteration order of that hash.

Perl has never guaranteed any ordering of the hash keys, and the ordering has already changed several times during the lifetime of Perl 5. Also, the ordering of hash keys has always been, and continues to be, affected by the insertion order and the history of changes made to the hash over its lifetime.

Therefore two hashes with same set of keys are explicitly NOT guaranteed to be iterated in same order.

Upvotes: 0

Joe McMahon
Joe McMahon

Reputation: 3382

It is specifically guaranteed that this is undependable.

See the Algorithmic Complexity Attacks section of perlsec in full. Despite its regrettable incoherency, it states that

  • in 5.8.1, the order is guaranteed to be random every time.
  • in 5.8.2 and later, the order will be the same unless Perl detects pathological behavior (specifically, a series of keys that would all hash to a small number of buckets, causing the hash performance to suffer). In those cases, "the function is perturbed by a pseudorandom seed".

The documentation does not guarantee that the ordering will always be the same; in fact, it specifically states that it will not be predictable in a pathological case. Should the hashing function be changed in a future release, it's possible that data which previously did not generate degenerate hashing would now do so, and then would be subject to the random perturbation.

So the takeaway is that if you're not using 5.8.1, maybe you'll get the same order, and maybe it won't change when you update your Perl, but it might. If you are using 5.8.1, then a random order is guaranteed.

If you want a dependable order, use one of the CPAN classes that provides a hash that has a guaranteed key order - Tie::Hash::Indexed, Tie::IxHash - or just sort your keys. If you have a hash that has less than a few thousand keys, you probably won't notice an appreciable difference. If it has more than that, maybe you should consider a heavier-weight solution such as a database anyway.

Edit: and just to make it more interesting, keys will be randomly ordered as of 5.18.

Upvotes: 5

pilcrow
pilcrow

Reputation: 58681

A longer test disproves.

So, different hashes with the same set of keys won't always have the same order. For me the program below demonstrates that two hashes with keys qw(a b c d e f) can differ in ordering:

v5.16.0
%h1: ecabdf
%h2: eadcbf

Program:

#!/usr/bin/env perl

use strict;
use warnings;
use feature qw(say);

# http://stackoverflow.com/q/12724071/132382

use constant KEYS => qw(a b c d e f);

my %h1 = map { $_ => undef } KEYS;
my %h2 = map { $_ => undef } KEYS;

delete @h2{'b', 'd', 'f'};
@h2{'x', 'y', 'z'} = ();
@h2{'b', 'd', 'f'} = ();
delete @h2{'x', 'y', 'z'};

say $^V;
say '%h1: ', keys(%h1);
say '%h2: ', keys(%h2);

Update

Here's a simpler demonstration that insertion order alone matters:

$ perl -MList::Util=shuffle -E \
> '@keys = ('a'..'z'); @h1{@keys} = @h2{shuffle @keys} = ();
> say keys(%$_) for (\%h1, \%h2)'
wraxdjyukhgftienvmslcpqbzo
warxdjyukhgftienmvslpcqbzo
#^^             ^^  ^^
#||             ||  ||

Upvotes: 7

Sinan Ünür
Sinan Ünür

Reputation: 118156

Here is a counter-example that is shorter than @pilcrow's (apparently I missed his answer when I first looked at this question):

#!/usr/bin/env perl

use strict; use warnings;

my @hashes = (
    { map { $_ => rand } 'a' .. 'z' },
    { map { $_ => rand } 'a' .. 'd', 'f' .. 'z' }
);

delete $hashes[0]{e};

print "@{[ keys %$_ ]}\n" for @hashes;

Output:

C:\temp> t
w r a x d j y u k h g f t i n v m s l c p q b z o
w r a x d j y u k h g f t i n v m s l c p b q z o

Upvotes: 4

matt freake
matt freake

Reputation: 5090

From perlsec:

Perl has never guaranteed any ordering of the hash keys, and the ordering has already changed several times during the lifetime of Perl 5. Also, the ordering of hash keys has always been, and continues to be, affected by the insertion order.

http://perldoc.perl.org/perlsec.html

Upvotes: 13

amon
amon

Reputation: 57640

perldoc -f keys has some info on the ordering:

The keys of a hash are returned in an apparently random order. The actual random order is subject to change in future versions of Perl, but it is guaranteed to be the same order as either the values or each function produces (given that the hash has not been modified). Since Perl 5.8.1 the ordering can be different even between different runs of Perl for security reasons (see Algorithmic Complexity Attacks in perlsec).

So the only guarantee is that no ordering is guaranteed.

Upvotes: 3

Related Questions