What is %labels?  Also, your declaration of %Hidlabels should use parentheses, not curlies.  As for the regex, you're matching on f(\d+), which only occurs once in the string...

This works for me:

my $str = "f3333_4444_2222";
my %Hidlabels = ( 3333=>1, 4444=>2, 2222=>3 );
$str =~ s/(\d+)/$Hidlabels{$1}/g;
[download]