As an alternative suggestion, you might consider using Tie::IxHash, which has an Indices() method you can use from the tied object:

#!/usr/bin/perl -w
use strict;
use Tie::IxHash;

my $IxObj = tie my %hash, 'Tie::IxHash';

my @values = qw(zero one two three four five six);
@hash{@values} = (1) x @values;

my $index = $IxObj->Indices('two');
print "$index\n";      # prints: 2

my @indices = $IxObj->Indices(qw/three one five/);
print "@indices\n";    # prints: 3 1 5
__END__
[download]

As for maintaining order, it also has a Push() method for adding key/value pairs, and SortByKey(), SortByValue(), and Reorder() methods which may be sufficient for your odering purposes. I haven't bothered to bench anything, so you may want to do that if performance is an issue.