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:~$
[download]

I hope this is helpful.