title: Efficiently finding matching pairs of objects
body: <p>I need an algorithm to find matching pairs of objects in a list. This is an example case:</p>
  
  <pre><code>class Human 
  {
     int ID;
     string monthOfBirth;
     string country;
     string [] hobbies = {};
  }
  </code></pre>
  
  <p>There is a large list of humans and the problem is to find matching human pairs, and this needs to be done efficiently because the lists are huge.</p>
  
  <p>Matching criteria:  </p>
  
  <ol>
  <li>Birth month and country must match exactly</li>
  <li>Both should have more than x% of hobbies matching.</li>
  </ol>
  
  <p>Because of (2) criteria we can't do an exact equals comparison.</p>
  
  <p>The ways I can think of are:</p>
  
  <ol>
  <li>Brute force - Compare each object with every other object. Complexity O(n^2)</li>
  <li>Hash table</li>
  </ol>
  
  <p>For the hash table approach, I'm considering the following way:</p>
  
  <ol>
  <li>Create a hash set of <code>&lt;String, List&lt;Human&gt;&gt;</code> (Or a MultiMap)</li>
  <li>Concatenate birth month and country of each Human to one string</li>
  <li>Use this concatenated string to hash to the HashSet (two humans having same birth month and country must give the same hash code)</li>
  <li>If there is already an element, compare the hobbies for x% of match</li>
  <li>If matching, then this is a duplicate</li>
  <li>If hobbies do not match more than x%, then add this human (linked list approach)</li>
  </ol>
  
  <p>Is there a better way to do this?</p>
  
  <p>Does it make sense to concatenate the month and country? The list would be large, so I'm assuming, 'better' would mean by the amount of storage, not the execution speed. </p>