One column from each file, so only the keys need to be compared? Here's a solution that uses no memory and only takes N iterations. I've been told hash lookups for Perl hashes is usually constant-time, so it can be ignored.

my $match = 0;

# Need to run each to the end
# so its safe to use again later.
while (defined(my $key = each(%hash1))) {
   $match ||= exists $hash2{$k};
}

if (!$match) {
   # No common
   ...
}
[download]