Why is this hash, created from a constant list, "in different order" each time the program is run?

Question

Below is the small script in Perl. Every time I run this code I'm getting different output.

Can anyone help me to understand the basics of storage of hash variables, that is how indexing is done for the key value pairs of Perl's hash variable.

#!/usr/bin/perl

%data = ('John Paul' => 45, 'Lisa' => 30, 'Kumar' => 40);
@names = keys %data;
print "$names[0]\n";
print "$names[1]\n";
print "$names[2]\n";

Answer 1

The behaviour is documented in perlsec's Algorithmic Complexity Attacks.

---

A hash is an array of linked lists. A hashing function converts the key into a number which is used as the index of the array element ("bucket") into which to store the value. More than one key can hash to the same index ("collision"), a situation handled by the linked lists.

If a malicious user knew the hashing algorithm, he could devise values that would hash to the same index, causing the hash to degenerate into a linked list. This can lead to huge performance drops in some applications, and thus can be used as part of a denial of service (DoS) attack.

Two measures are taken to avoid that. One is to salt the hashing algorithm to randomize the order in which elements are stored, and the other makes it harder to detect the salt by perturbing the order in which the iterator visits the hash elements.

$ perl -E'
   my @k = "a".."z";
   for (1..3) {
      my %h = map { $_ => 1 } @k;
      say keys %h;
   }
'
iocmbygdkranwxfejuqpzvltsh
bmcoigdywrankujfxezpqlvths
juexfwarnkgdybmcoihstlvzpq

Answer 2

This behavior is described in perldoc -f keys

Hash entries are returned in an apparently random order. The actual random order is specific to a given hash; the exact same series of operations on two hashes may result in a different order for each hash. Any insertion into the hash may change the order, as will any deletion, with the exception that the most recent key returned by each or keys may be deleted without changing the order. So long as a given hash is unmodified you may rely on keys, values and each to repeatedly return the same order as each other.

.. in order to prevent Algorithmic Complexity Attacks