If you don't need @vals after you've built the hash, this will build your hash without using any modules:

use Data::Dump 'pp'; # a nicer Data::Dumper

my @keys = qw {red blue red};
my @vals = (1, 2, 3);

my %hash;
push @{$hash{$_}}, shift @vals
  for @keys;

pp \%hash;
__END__
{ blue => [2], red => [1, 3] }
[download]

If you do need @vals, you could replace the above loop with:

push @{$hash{$keys[$_]}}, $vals[$_]
  for 0..$#keys;
[download]

Update: Re-added the call to pp