You might find Data::Pairs useful.

In addition to your hash, you could record the keys and values in an array, then reverse the array to retrieve the reverse of the entry order. This is just another implementation of a log or journal, as suggested previously.

As it appears from your example that your sets of data may be interleaved, unrolling them is not as simple as merely reversing the log/journal. You might do something like the following:

use strict;
use warnings;
use Data::Dumper;

my %hash = (key1 => [1],
         key2 => [1],
         key3 => [1]);

my @array = (
    [ key1 => 1 ],
    [ key2 => 1 ],
    [ key3 => 1 ],
);

my %keys = (
    key1 => 1,
    key2 => 1,
    key3 => 1,
);

foreach my $result (
    [ key2 => 4 ],
    [ key3 => 8 ],
    [ key1 => 7 ],
    [ key2 => 9 ],
    [ key4 => 8 ],
    [ key2 => 9 ],
    [ key3 => 2 ],
) {
    my ($key, $value) = @$result;
    push(@{$hash{$key}},$value);
    push(@array, $result );
    $keys{$key}++;
}


my $nkeys = scalar(keys %keys);
while(@array) {
    my @set;
    my %set;
    for( my $i = $#array; $i >= 0; $i-- ) {
        my ($key, $value) = @{ $array[$i] };
        unless($set{$key}) {
            push(@set, splice(@array, $i, 1));
            $set{$key} = $value;
        }
        last if( @set == $nkeys );
    }
    foreach my $entry (@set) {
        print "@$entry\n";
    }
    print "\n";
}

__END__

key3 2
key2 9
key4 8
key1 7

key2 9
key3 8
key1 1

key2 4
key3 1

key2 1
[download]