I agree with BrowserUk that we may be able to provide better answers given a better problem definition. This sounds a bit like an XY Problem.

However, an alternative approach is to 'invert' the hash. This will give very fast lookup of a key for a value in the original hash, but will only ever return one single key, the same one every time, chosen at random, from the set of all keys in the original hash having a particular value. (Note that the 'random choice' referred to here occurs when the original hash is inverted, and is fixed thereafter.)

>perl -wMstrict -le
"my %hash = qw(one 1  uno 1  un 1  two 2  tres 3);
 my %hsah = reverse %hash;
 ;;
 for my $v (1, 2, 4) {
   print qq{value '$v' },
         exists $hsah{$v} ? qq{is $hsah{$v} } : q{does not exist },
         q{in original hash};
   }
"
value '1' is uno in original hash
value '2' is two in original hash
value '4' does not exist in original hash
[download]