my %union = ( %hash1, %hash2 );
my @keys = sort keys %union;
undef %union;

foreach my $key ( @keys ) {
   if ( ! exists $hash1{$key} ) {
      print "key $key is not in hash 1\n";
   } elsif ( ! exists $hash2{$key} ) {
      print "key $key is not in hash 2\n";
   }
   ....