This will work:

#!/usr/bin/perl -w
use strict;

my @a = qw( 1 2 3 4 5 );
my @b = qw( a b c d e );
my %h = map { $a[$_] => $b[$_] } ( 0..$#a );
print "$_ => $h{$_}\n" foreach sort keys %h;
[download]

I'm still trying to find a way to do this without using indexes, though ;-)

Update: Yeah, the code japhy and Masem posted does exactly what I was looking for.
That's what happens when you're too far from your copy of The Camel Book ;-)

-mk