Making the "simple" key smaller might be possible in many cases, but the calculation method to getting it to "smallish" will probably defeat the gain over hashes.

The subtraction of a simple constant makes almost no difference:

$t=time; $a[ $_-123 ] = $_ for 123 .. 123+1e6; print time() - $t; prin
+t total_size \@a;;
0.252718925476074
32388792

$t=time; $h{ $_ } = $_ for 123 .. 123+1e6; print time() - $t; print to
+tal_size \%h;;
0.625
112278277
[download]

To me the most important reasons to use arrays are: 1) Data must stay in original order 2) Data is not guaranteed to be unique 3) The "target" API works only with lists/arrays

Of those, the first two are moot. If the data can be stored in an array, then it can also be stored in a hash whilst meeting both of those criteria.

That is, it is the keys of a hash that must be unique, and that is easily achieved by incrementing a integer variable as you build the hash. And once you've done that retrieval in insertion order is just a matter of iterating the keys.

For your third criteria, if the APIs don't accept hashes, then there is no choice.