Ordered Hashes

Perl hashes have no internal order. A hash consists of a number of "buckets''. When a record is inserted into the hash, the key is transformed, using a "hash function'', into a bucket number. The details of the hash function itself are not important, but a good hash function ensures that even very similar keys are mapped to different buckets. If too many keys map to the same bucket, then Perl has to spend a lot of time searching through that bucket for the corresponding value.

The important thing is not how Perl puts the key into the hash table but what the table gives us. To find if a value is in a hash, Perl takes the key name supplied, applies the same transformation and checks to see whether the key is in that position. This is much faster than searching through an ordered list.

However, while we often appreciate the speed in which hashes work, sometimes we want to maintain key order as well. A common solution is to create both our hash and an array. The array stores the keys in sorted order and we can then iterate through our has as required:

        my @idNumbers = qw(101 102 ... );
        
        my %nameMapping = ( 101 => 'Siva', 102 => 'Sakthi', ... );

        foreach my $Key ( @idNumbers ) {
                print "$Key : $nameMapping{$Key} \n";
        }

If @idNumbers and %nameMapping are created in one place in our program and then never changed (such as could be expected for a list of months of the year) then this is a very good solution. However if our hash is likely to grow over time then we can encounter problems. What happens if a key is added to one structure but not the other?

Fortunately there are better solutions.

Tie::InsertOrderHash

        use Tie::InsertOrderHash;

        tie my %nameMapping => 'Tie::InsertOrderHash',
             101   => 'Siva',
             102   => 'Sakthi',
             103   => 'Swetha',
             104   => 'Saran',
             105   => 'Darwin';              

        print join(" ", keys %nameMapping), "\n";

        # prints: 101,102,103,104,105

In the above example, we're setting the hash at creation time. This is not required. We can add our values to our hash whenever we desire, just like a normal hash, further, our values can be any kind of value we can normally use in a hash.

Tie::IxHash

Tie::InsertOrderHash does not allow you to change values in your hash and keep the original ordering. Thus, as mentioned above, updating the keys in 102 will cause 102 to now appear after 105 when listing the keys.

If you want to be able to change values without changing the ordering then Tie::IxHash may be a better option.

        use Tie::IxHash;

        tie my %nameMapping => 'Tie::IxHash',
             101   => 'Siva',
             102   => 'Sakthi',
             103   => 'Swetha',
             104   => 'Saran',
             105   => 'Darwin';
   
     # Update Hash Value
     $nameMapping{102} = 'Kumar';

        print join(" ", keys %nameMapping), "\n";

        # prints: 101,102,103,104,105

There is also Tie::Hash::Indexed which provides less features than Tie::IxHash, but is considerably faster.

To get a similar behaviour to Tie::InsertOrderHash you can delete a key-value pair from your hash before providing the new value. Thus if we were to write:

delete($nameMapping{102} );

$nameMapping{102} = 'KumarS';

then June would be considered to have been inserted last.