I come up this structure for your reference. I name it OrderedHash. The code given below is strictly for the purpose to explain the structure more clearly, not any kind of actual implementation. This OrderedHash structure contains two parts:

1. An array, normal array, which contains the key pair values of the OrderedHash. In the Array, those key-value pairs are stored in this sequence: k1, v1, k2, v3, k3, v3...
2. A hash, normal hash, its keys are the keys of the OrderedHash, values are indexes point to the key of the actual key value pairs in the above array.

A brief analysis of this structure:

1. It reserves the order.
2. It is independent, yet not much implementing effort
3. We don't invent or implement any hashing algorithm, we simply use a normal hash for indexing.
4. Its performance is the same as a normal hash. We don't sacrifice performance.
5. This solution DO sacrifice space to gain performance and to reduce implementation effort, it uses as twice as many space used by a normal hash that has the same number of elements.

The following code is only to demo the structure.

package OrderedHash;
use strict;

sub new {
   my $self = {};
   $self->{INDEX} = {};
   $self->{PAIRS} = [];
   bless $self;
   return $self;
}

sub set {
   my ($self, $key, $value) = @_;
   push @{$self->{PAIRS}}, $key;
   $self->{INDEX}->{$key} = $#{$self->{PAIRS}};
   push @{$self->{PAIRS}}, $value;
}

sub get {
   my ($self, $key) = @_;
   return $self->{PAIRS}->[$self->{INDEX}->{$key} + 1];
}

sub list_in_order {
   my $self = shift;
   my $is_key = 1;
   foreach (@{$self->{PAIRS}}) {
      if (!$is_key) {
          print "$_\n";
      } else {
          print "[$_] = ";
      }
      $is_key = !$is_key;
   }
}

1;

use OrderedHash;
use Data::Dumper;
use strict;

my $oh = new OrderedHash;
$oh->set("a", 1);
$oh->set("b", 2);
$oh->set("c", 3);
print Dumper($oh);
$oh->list_in_order;
[download]