Why Hash Order Changes Between Runs

Part I · Module 6 · Chapter 6.6 · Why Hash Order Changes Between Runs

1. Five Runs, Five Orders

use strict;
use warnings;

my %block = (alu => 1, fifo => 2, decoder => 3, regfile => 4, cpu => 5);

print join(",", keys %block), "\n";

Run that script five times without changing anything:

regfile,cpu,fifo,alu,decoder
cpu,regfile,alu,decoder,fifo
alu,cpu,decoder,fifo,regfile
fifo,alu,decoder,cpu,regfile
decoder,cpu,regfile,alu,fifo

Five different orderings. Same machine, same Perl, same source, same data, nothing edited between runs.

And when you run it yourself you will get five lines that differ from the five above as well — running this capture a second time produced another five distinct orders, none matching the first set. The only reproducible thing about that output is that it is not reproducible.

Now the same script with one word added:

use strict;
use warnings;

my %block = (alu => 1, fifo => 2, decoder => 3, regfile => 4, cpu => 5);

print join(",", sort keys %block), "\n";

alu,cpu,decoder,fifo,regfile
alu,cpu,decoder,fifo,regfile
alu,cpu,decoder,fifo,regfile
alu,cpu,decoder,fifo,regfile
alu,cpu,decoder,fifo,regfile

Identical every time. That is the whole fix, and the rest of the chapter is why it is necessary and what else to know about it.

2. It Is Not Insertion Order Either

A reasonable first guess is that a hash remembers the order you added things. It does not:

use strict;
use warnings;

my %h;

$h{$_} = 1 for qw(zebra apple mango banana);

print "inserted : zebra apple mango banana\n";
print "keys     : ", join(" ", keys %h), "\n";

inserted : zebra apple mango banana
keys     : banana mango zebra apple

Neither insertion order nor alphabetical order. A second run of the same script gave zebra apple banana mango — a different order again, which happens to start with the first-inserted key and is still not insertion order. The keys come back in whatever order the hash's internal layout puts them, and that layout depends on a value chosen when the process starts.

So there are three orders a reader might expect and the hash gives none of them: not insertion, not sorted, and not even the same one twice.

3. Perl Does This on Purpose

This is worth quoting rather than paraphrasing. From the Perl 5.18 release notes, under "Hash randomization":

The seed used by Perl's hash function is now random. This means that the order which keys/values will be returned from functions like keys(), values(), and each() will differ from run to run.

This change was introduced to make Perl's hashes more robust to algorithmic complexity attacks, and also because we discovered that it exposes hash ordering dependency bugs and makes them easier to track down.

Two reasons, and they are different in character:

• Security. perldoc perlsec's "Algorithmic Complexity Attacks" section explains it: if an attacker knows how keys map to internal buckets, they can craft input whose keys all collide, turning fast lookups into slow ones and producing a denial of service. Randomising the seed at process start makes that key set impossible to construct in advance.
• Bug exposure. Perl's own notes say the randomness was kept partly because it breaks code that depended on order. Before 5.18 such code worked by accident and failed unpredictably later; now it fails immediately and visibly.

4. Sort the Keys — and Sort Them Correctly

use strict;
use warnings;

my %errors = (alu => 0, fifo => 7, decoder => 2, regfile => 0);

printf "%-10s %s\n", "block", "errors";

for my $block (sort keys %errors) {
    printf "%-10s %d\n", $block, $errors{$block};
}

block      errors
alu        0
decoder    2
fifo       7
regfile    0

sort keys %h is the default to reach for. But "sort the keys" is not one instruction — it is Chapter 5.9's question again, and the trap is the same:

use strict;
use warnings;

my %cycles = (1 => "a", 2 => "b", 10 => "c", 100 => "d", 9 => "e");

printf "plain sort   : %s\n", join(" ", sort keys %cycles);
printf "numeric sort : %s\n", join(" ", sort { $a <=> $b } keys %cycles);

plain sort   : 1 10 100 2 9
numeric sort : 1 2 9 10 100

1 10 100 2 9 — the plain sort is a text sort, exactly as Chapter 3.6 §3 and Chapter 5.9 §1 measured. Hash keys are always strings, as Chapter 6.2 §4 established, so a hash keyed on numbers always needs <=>.

That combination — hash keys are strings, and sort on strings puts 10 before 2 — catches people twice over.

Ordering by value

Often the useful order is by value rather than key:

use strict;
use warnings;

my %errors = (alu => 0, fifo => 7, decoder => 2, regfile => 0);

printf "worst first : %s\n",
    join(" ", sort { $errors{$b} <=> $errors{$a} or $a cmp $b } keys %errors);

worst first : fifo decoder alu regfile

The comparator looks each key's value up and compares those. Note the tie-break — or $a cmp $b — which matters more here than anywhere else in the track: alu and regfile both have zero errors, and without the tie-break their relative order is left to the sort, which Chapter 5.9 §5 established is not guaranteed.

So a sort by value over a hash needs two things to be reproducible: the sort itself, and a total comparator. Either one missing and the report can differ between runs — and that is measured rather than theoretical. Running the same sort without the tie-break ten times produced two distinct orderings:

fifo decoder alu regfile
fifo decoder regfile alu

The tied pair alu and regfile swapped. With or $a cmp $b added, all ten runs gave the first line.

5. Where the Instability Actually Hurts

use strict;
use warnings;

my %errors = (alu => 0, fifo => 7, decoder => 2);

for my $block (keys %errors) {
    printf "%-10s %d\n", $block, $errors{$block};
}

That script is correct in every respect except one: its output order varies. Which matters in three specific situations.

Diffing today's report against yesterday's. This is the big one. A nightly summary compared against the previous night shows every row as moved, and the one row that genuinely changed is invisible in the noise. The whole point of the comparison is lost.

A test that checks output. A regression test asserting a script's exact output passes or fails depending on the hash seed, which makes it flaky — failing perhaps one run in five with no change to the code. That is worse than no test, because it trains people to re-run until it passes.

A human reading two reports side by side. Even without tooling, a reader comparing two runs needs the rows in the same places.

6. The Environment Variable Is a Debugging Aid, Not a Fix

Perl provides a way to pin the seed:

$ PERL_HASH_SEED=0 perl order.pl
cpu,regfile,fifo,decoder,alu
$ PERL_HASH_SEED=0 perl order.pl
cpu,regfile,fifo,decoder,alu
$ PERL_HASH_SEED=0 perl order.pl
cpu,regfile,fifo,decoder,alu

Identical across the three runs. That is genuinely useful for one job: reproducing an order-dependent failure while you track it down. Set it, get the same order every time, and debug deterministically.

It is not a fix, for three reasons:

• perldoc perlsec is explicit that PERL_HASH_SEED "controls how items are actually stored, not how they are presented via keys, values and each" — a separate variable, PERL_PERTURB_KEYS, governs the presentation. So the relationship between the seed and the order you see is not something to build on.
• It re-opens the security property the randomisation exists for.
• It makes the environment responsible for your script's correctness. A script that only produces the right report when an environment variable is set is a script that will produce the wrong report the first time somebody runs it without that variable.

Sort in the code. It is one word, it is local to the thing that needs it, and it works everywhere.

7. Why This Matters in Engineering Work

Reports get diffed. Nightly against previous-nightly, candidate against golden, this branch against main. All of it depends on the output being a function of the data alone, and an unsorted hash walk breaks that.

Flaky tests are expensive. A test that fails one run in five because of hash order costs more than the bug it was meant to catch, because it teaches everyone to ignore failures.

Generated files need to be stable. A constraints file, a filelist, a configuration emitted by a script — if any of them is built by walking a hash, the file's content changes between runs and so does every checksum and every diff of it.

And "pick one" needs a rule. (keys %h)[0] is an arbitrary choice that changes between runs. Whenever a script picks one item out of a hash, there is a real rule for which one, and writing it down is both the fix and the documentation.

8. Common Mistakes

Printing keys %h unsorted. The output order changes between runs.

Assuming insertion order is preserved. It is not, and never was.

Expecting the order to at least be consistent within one machine. It is chosen per process, so consecutive runs differ.

Using a plain sort on numeric keys. Hash keys are strings, so 10 sorts before 2. Use <=>.

Sorting by value without a tie-break. Equal values leave the order unspecified — Chapter 5.9 §5.

Taking (keys %h)[0] as "the first key". It is an arbitrary key, different each run.

Using PERL_HASH_SEED to stabilise production output. It is a debugging aid; sort in the code.

Treating the randomness as an obstacle. Perl's own notes say it exists partly to expose this class of bug.

9. Exercise

Exercise 1 — see it yourself. Write a script that prints keys of a five-key hash unsorted, and run it five times. Record all five lines. Then add sort and run it five more times, and record those.

Exercise 2 — not insertion order. Insert four keys in a deliberate order, print them unsorted, and compare. State the three orders a reader might expect and which one you got.

Exercise 3 — the numeric trap. Build a hash keyed on 1, 2, 9, 10, 100 and print the keys with a plain sort and with { $a <=> $b }. Say why the plain sort behaves that way, naming the chapter that established hash keys are strings.

Exercise 4 — by value, reproducibly. Order a four-block error hash worst-first, with two blocks tied at zero. Run it five times with no tie-break and record whether the tied pair ever swaps. Then add the tie-break and run five more times.

Exercise 5 — the arbitrary first. Write my ($first) = keys %h; over a three-key hash and run it ten times, recording which key you got each time. Then rewrite it to pick the alphabetically first key deliberately.

Exercise 6 — the pinned seed. Run your Exercise 1 script three times with PERL_HASH_SEED=0 set. Confirm the order is identical, then write one sentence on why you would not put that in a wrapper script.

Exercise 7 — find the dependency. You are given a script whose report differs between runs. List the three things you would grep for in it, and say what you would change in each case.

10. Summary

• A hash has no order. Five runs of one unchanged script gave five different key orders.
• It is not insertion order and not sorted order — it follows an internal layout seeded per process.
• Perl randomises it deliberately, from version 5.18, for two documented reasons: hardening against algorithmic complexity attacks, and exposing code that depended on order.
• sort keys %h is the fix, and it made the same script identical across five runs.
• Hash keys are strings, so numeric keys need sort { $a <=> $b }.
• Sorting by value needs a tie-break to be reproducible.
• (keys %h)[0] is an arbitrary key, different each run — say which one you actually want.
• PERL_HASH_SEED is for reproducing a bug, not for stabilising output. Sort in the code.

Chapter 6.7 covers reading and writing several keys in one statement, which is the compact way to pull a known set of fields out of a record you have just parsed.