@sorted = sort keys %hash;

%hash = map { my $v = $hash{$_}; s/ /_/g; $_, $v } @sorted;