Well ... if your hash wasn't 2^40 entries (yikes!) ... grep would be the answer.

#!/usr/bin/perl

use strict;
use warnings;

my %freq = (
    aaa => 5,
    aab => 2,
    aac => 8,
    aad => 7,
    faa => 5,
    fab => 2,
    fac => 8,
    fad => 7,
    baa => 5,
    bab => 2,
    bac => 8,
    bad => 7,
    caa => 5,
    cab => 2,
    cac => 8,
    cad => 7,
);

my @keys = grep( /^aa/, keys %freq );

foreach my $key ( @keys ) {
  print $key, " => ", $freq{$key}, "\n";
}
[download]