One way is to use a HoH and keep the insertion order alongside the data.
knoppix@Microknoppix:~$ perl -Mstrict -wE '
> my @keys = qw{ pete bill mary jack dave leah };
> my $order = 0;
> my %hash;
>
> foreach my $key ( @keys )
> {
> $hash{ $key } = { data => $order * 2, order => ++ $order };
> }
>
> say qq{$_ => $hash{ $_ }->{ data } }
> for sort { $hash{ $a }->{ order } <=> $hash{ $b }->{ order } }
> keys %hash;'
pete => 0
bill => 2
mary => 4
jack => 6
dave => 8
leah => 10
knoppix@Microknoppix:~$
I hope this is helpful.