Iterating hash based on the insertion order?

Question

Don't want to sort the entries.

using this does not preserve the order as well

 foreach my $val (keys %hash) {
     ...
 } 

Answer 1

Hashes are unordered by default in Perl 5. You can use tie and Tie::IxHash to override this behavior. Be warned though, there is a performance hit and other considerations (like the fact that the order will not be preserved in copies).

#!/usr/bin/perl

use strict;
use warnings;

use Tie::IxHash;

tie my %hash, "Tie::IxHash"
    or die "could not tie %hash";

$hash{one}   = 1;
$hash{two}   = 2;
$hash{three} = 3;

for my $k (keys %hash) {
    print "$k $hash{$k}\n";
}

A better option may be to use an array or a hash of hashes:

#!/usr/bin/perl

use strict;
use warnings;

my %hash;
$hash{one}   = { data => 1, order => 1 };
$hash{three} = { data => 3, order => 2 };
$hash{two}   = { data => 2, order => 3 };

for my $k (sort { $hash{$a}{order} <=> $hash{$b}{order} } keys %hash) {
    print "$k $hash{$k}{data}\n";
}

As for performance, here are the results of a benchmark:

hash: e, c, a, b, d, f
IndexedOO: a, b, c, d, e, f
IxHash: a, b, c, d, e, f
hoh_pis: a, b, c, d, e, f
hoh: a, b, c, d, e, f
IxHashOO: a, b, c, d, e, f
Indexed: a, b, c, d, e, f
           Rate   IxHash       hoh  Indexed IxHashOO  hoh_pis IndexedOO     hash
IxHash    108/s       --      -34%     -39%     -56%     -67%      -70%     -85%
hoh       163/s      51%        --      -8%     -33%     -51%      -55%     -77%
Indexed   177/s      64%        9%       --     -27%     -46%      -52%     -75%
IxHashOO  243/s     125%       49%      37%       --     -26%      -33%     -65%
hoh_pis   330/s     205%      102%      86%      36%       --      -10%     -53%
IndexedOO 366/s     238%      124%     106%      50%      11%        --     -48%
hash      704/s     551%      332%     297%     189%     113%       92%       --

From this we can see that using Tie::Hash::Indexed in its OO capacity (rather than its tied capacity) is the best of indexed hash methods and is about half the speed of an unordered hash. The HoH method is pretty close if you use a custom sort that takes advantage of the fact that we know where each item should go (if you plan on deleting keys, you will need to return grep { defined } @k; instead of just @k).

Here is the benchmark:

#!/usr/bin/perl

use strict;
use warnings;

use Tie::IxHash;
use Tie::Hash::Indexed;
use Benchmark;

#this is O(n) instead of O(n log n) or worse
sub perfect_insert_sort {
    my $h = shift;
    my @k;
    for my $k (keys %$h) {
        $k[$h->{$k}{order}] = $k;
    }
    return @k;
}

my @keys = qw/a b c d e f/;
my %subs = (
    hash => sub {
        my $i;
        my %h = map { $_ => $i++ } @keys;
        return join ", ", keys %h;
    },
    hoh => sub {
        my $i;
        my $order;
        my %h = map {
            $_ => { data => $i++, order => $order++ }
        } @keys;
        return join ", ", sort { $h{$a}{order} <=> $h{$b}{order} }
            keys %h;
    },
    hoh_pis => sub {
        my $i;
        my $order;
        my %h = map {
            $_ => { data => $i++, order => $order++ }
        } @keys;
        return join ", ", perfect_insert_sort \%h;
    },
    IxHash => sub {
        my $i;
        tie my %h, "Tie::IxHash";
        %h = map { $_ => $i++ } @keys;
        return join ", ", keys %h;
    },
    Indexed => sub {
        my $i;
        tie my %h, "Tie::Hash::Indexed";
        %h = map { $_ => $i++ } @keys;
        return join ", ", keys %h;
    },
    IxHashOO => sub {
        my $i;
        my $o = tie my %h, "Tie::IxHash",
            map { $_ => $i++ } @keys;
        return join ", ", $o->Keys;
    },
    IndexedOO => sub {
        my $i;
        my $o = tie my %h, "Tie::Hash::Indexed",
            map { $_ => $i++ } @keys;
        my @k = my $k = $o->FIRSTKEY;
        while ($k = $o->NEXTKEY($k)) {
            push @k, $k;
        }
        return join ", ", @k;
    },
);

for my $sub (keys %subs) {
    print "$sub: ", $subs{$sub}(), "\n";
}

@keys = 1 .. 1_000;
Benchmark::cmpthese -1, \%subs;