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