To modify keys of a hash, it is necessary to copy it. The keys can be modified in the process of the copy by using 'map' like this:

my %Orig=('a b'=>44,  'c d'=>22, rr=>99);

my %Copy = map {my $y=$Orig{$_}; #Save Copy of Val
                tr/ /_/;
                $_ => $y}
             keys %Orig;

print qq(C: $_ => $Copy{$_}\n) for keys %Copy;
print qq(O: $_ => $Orig{$_}\n) for keys %Orig;
[download]

The trick here is to save a copy of the Value into "$y" before "$_" is modified.
Once $_ is modified, the $Orig{$_} is no longer valid, so it must be saved into $y first.