It sounds like you might actually be trying to cluster the hashes based on relative similarity to each other -- or maybe you just want to identify the two hashes that are most similar to each other.

Anyway, it might be interesting to treat the key-value pairs as strings, print the contents of each hash as a sorted list of these strings, then do pair-wise diffs on the text files. The pair with the fewest diffs is the closest match. The following has not been tested, but perhaps it will be useful.

sub printHash 
{
   my ( $hash_name, $hash_ref ) = @_;
   open( LIST, ">", $hash_name ) or die $!;
   print LIST sort map { "$_ $$hash_ref{$_}\n" } keys %$hash_ref;
   close LIST;
}

...

# assume you have an "ur-hash", holding hash_refs keyed by hash_name:

my @difflist1 = my @difflist2 = sort keys %all_hashes;

foreach my $name ( keys %all_hashes ) {
   printHash( $name, $all_hashes{$name} );
}
my %distances;
foreach my $h1 ( @difflist1 ) {
   shift @difflist2;  # dispose of the identical item in list2
   foreach my $h2 ( @difflist2 ) {
      $distances{"$h1:$h2"} = `diff $h1 $h2 | grep -c '^<>'`;
   }
}
# then do something with the values in %distances
[download]

(update: fixed to read $$hash_ref{$_} in the subroutine)