You can use reverse to reverse a hash: keys become values, values become keys. One has to be careful though, if there are duplicate values (two persons sharing a phone number) only one entry will survive. In addition, if the values are not strings, Perl will stringify them, which can have funny effects.

You can also use grep like this:

my @keys = grep { $hash{$_} eq $some_value } keys %hash;
[download]

which can return multiple values keys.

Update: some example

my %verzeichnis = (
    peter => 12345,
    paul  => 34567,
    mary  => 12345
);

my @names = grep { $verzeichnis{$_} eq '12345' } keys %verzeichnis;
print "@names\n";

my %rueckwaertssuche = reverse %verzeichnis;
print $rueckwaertssuche{'12345'}, "\n"; # lost mary
[download]