You can turn your structure into the new structure like so:

my %hash;
while (my ($k,$v) = each %values) {
  push @{$hash{$v}}, $k;
}
[download]

So just keep it as a flat hash until you need the other structure (at the end, to print), then convert it.