use strict;
use warnings;
use Data::Dumper;

my %hash = (
  'Alabama'    => ['Andalusia','Anniston','Clanton','Eufaula','Auburn','Auburn','Auburn','Auburn'],  
  'California' => ['Barstow','Eufaula'],
  'New York'   => ['Amsterdam','Coney Island','Beacon','Beacon','Beacon','Beacon','Beacon'],
  'Utah'       => ['Beacon','Layton'],
);

# Invert the hash.
my %inverted = map {
	my $state = $_;
	map { $_ => $state } @{$hash{$state}}
} sort keys %hash;

print Dumper \%inverted;

# And back again:
%hash = ();
while (my ($city, $state) = each %inverted) {
	push @{ $hash{$state} ||= [] }, $city;
}

print Dumper \%hash;