moof1138 has asked for the wisdom of the Perl Monks concerning the following question:

Is there a really simple way to get a random key from a hash? I have been doing this:
```#assuming we have %knockknocks populated with many knock knock jokes
my @setups = keys %knockknocks;
my \$jokekey = \$setups[rand @setups];
When I use this I keep thinking that there has to be a better way to do this without an intermediate array, but I could not find anything in the docs or the Cookbook that addressed this.

Replies are listed 'Best First'.
Re: easy way to get random key from hash?
by grinder (Bishop) on Aug 05, 2002 at 19:20 UTC
You can do it without an array, but you will still have to pay the cost of scanning all the keys once. The idea is that you choose the first element if rand() < 1 (which it always will be), the second element if rand() < 1/2 (which it will be half of the time), the third element if rand() < 1/3 (which will be one third of the time, which leave 2/3 for the first two elements, and we've already seen that they get chosen 50/50)...

You can see where this is going: choose the nth element if rand() < 1 / n. Translated to Perl this gives something like:

```sub choose {
my \$count = 0;
my \$result = undef;
for( @_ ) {
\$result = \$_ if rand() < 1 / ++\$count;
}
\$result;
}

my \$jokekey = choose( keys %knockknocks );

This actually chooses from a list, but then that's what the keys of a hash are, so everything is fine.

The beauty of this approach is that you don't need to know beforehand how many elements you have to choose from. That is, the array in question may shrink or grow in the course of the program's run, and the algorithm will compensate. In fact, you may be able to skip loading the hash in the first place, depending on system load. Just read through the file fortune-at-a-time, and cache the file pointer offset instead. Then, at the end of the file seek back to the cached position and read from there. This means you will be able to add fortunes without having to restart the process.

I first heard about this technique in a book by Jon Bentley, either _Programming Pearls_ or _More Programming Perls_. They are probably verging on the edge of being out of print, but if you can track them down, they are absolute gems.

print@_{sort keys %_},\$/if%_=split//,'= & *a?b:e\f/h^h!j+n,o@o;r\$s-t%t#u'
Hey! I was about to post the same algorithm (written slightly differently), found in perlfaq5: "How do I select a random line from a file?" You can find the proof by induction here, by guess who. Mine looked like this:

```my (\$i, \$jokekey);
++\$i && rand(\$i) < 1 && (\$jokekey = \$_) for (keys %hash);

However, I wouldn't use it this way in production. Like you said, it always iterates through all the keys of the hash before it returns the random key. The benefit you gain by not needing to know how many elements isn't really a benefit. The following snippet will give you the same benefit and it's easier to read, and (probably) more efficient:

```sub choose {
#assumes 1st param is \%knockknocks
my \$jokeref = shift;
my @setups = keys %\$jokeref;
return \$setups[rand @setups];
}

Now if the jokes are kept in a separate file, that could change everything ;-)

I think the best technique depends on the size of your jokes hash. If you have lots of jokes, use a separate file with the technique grinder describes (that works very well for randomly selecting a line from a file). If there are just some tens of jokes, then
```\$joke = \$knockknocks{(keys %knockknocks)[rand keys %knockknocks]};
works just as well, IMHO. Keep the easy things easy, and all that :-)
Re: easy way to get random key from hash?
by eduardo (Curate) on Aug 05, 2002 at 18:54 UTC
This is ugly, but it seems to "work":
```#!/usr/bin/perl -w

use strict;

my %hash = (foo=>1, bar=>2, baz=>3);

print \$hash{[keys %hash]->[int rand keys %hash]};