my %all_ids = map { $_ => undef } @all_ids;  # note there's multiple ways to init this hash

while ( my ($key, $value) = each(%hash) ) {
  printf "the pair (%s => %s) is not in the array", $key, $value unless exists $all_ids{$key};
}

# or grep instead of while:
my @missing_keys = grep( !exists $all_ids{$_}, keys %hash);