The following is a slight modification of your program. It (ab)uses the fact that Perl only checks whether to split buckets when you use a new bucket. It does not make any assumptions about Perl's hashing algorithm. It is therefore able to generate the special keys much more quickly than yours does.

my $HOW_MANY = shift || 100_000;

my ($s, $e1, $e2);
$s = time;
for ($i=0; $i<$HOW_MANY; $i++) {
  $q{$i}=1;
}
$e1 = time - $s;
print qq{
Normally, it takes me about $e1 second(s) to put $HOW_MANY items into 
+a
hash.  Now I'm going to construct $HOW_MANY special keys and see 
how long it takes to put those into a hash instead.
};
undef %q;

print "Generating $HOW_MANY keys\n";
my @keys;
my $i = 0;
while (@keys < $HOW_MANY) {
  $i++;
  my %hash = (0 => 0, $i => 0);
  if (%hash =~ /1/) {
    # Goes in the same bucket as 0
    push @keys, $i;
  }
}

print "Putting the $HOW_MANY special keys into the hash.\n";
$i = 0;
$lasttime = $s = time;
foreach $key (@keys) {
  $h{$key} = 1;
  
  $i++;
  
  if (time() - $lasttime  > 5) {
    my $h = %h + 0;
    print "I have put $i keys into the hash, using $h bucket(s)\n" ;
    $lasttime = time;
  }
}

$e2 = time - $s;
print qq{
The $HOW_MANY special keys took $e2 seconds to put into the hash,
instead of $e1 seconds.
};
[download]

Update: (Much later.) Perl changed when it splits buckets so this program no longer runs slowly. Furthermore Perl's hashing algorithm is now random, so Dominus' program no longer runs slowly. Shucks.