There is a much better answer in this case than storing multiple bits of information in the hash keys. I would personally never do that unless I absolutely had to. The example given in this question is actually a really simple data structure: One name to Multiple values, or in perl, a hash whose values are array references. Enough lecturing now.

my %countries = ();
my $foo = "US:New York";
my ($country, $city) = (split /:/, $foo);
push @{ $countries{$country} }, $city;
[download]

This code assumes you understand references in perl.

Then to print all the cities within the country:

foreach my $city (@{$countries{$country}}) {
    print "$city\n";
}
[download]

It's trivial to include even more information than that as well; turn that array reference into a hash reference by city, containing maybe another hash reference with even more information or an array with a list of people who live there.