title: A fast way to find unique values in the list
body: <p>Given a list of KeyValuePairs, where each pair has a <code>getValue()</code> method, what would be the fastest way to obtain a <code>List</code> (or <code>Set</code>) of unique Values?</p>
  
  <p>All of the below produce acceptable result. <code>u1</code> seems to be fastest over an expected list size (about 1000-2000 KVP)</p>
  
  <p><strong>Can we do better (faster)?</strong></p>
  
  <pre><code>private static Set&lt;String&gt; u1(List&lt;_KVPair&gt; pairs) {
      Set&lt;String&gt; undefined = new HashSet&lt;String&gt;();
  
      for (_KVPair pair : pairs) {
          undefined.add(pair.getValue());
      }
  
      if (undefined.size() == 1) {
          return new HashSet&lt;String&gt;();
      }
      return undefined;
  }
  
  private static List&lt;String&gt; u2(List&lt;_KVPair&gt; pairs) {
  
      List&lt;String&gt; undefined = new ArrayList&lt;String&gt;();
      for (_KVPair pair : pairs) {
          if (!undefined.contains(pair.getValue())) {
              undefined.add(pair.getValue());
          }
      }
  
      return undefined;
  }
  
  private static List&lt;String&gt; u3(List&lt;_KVPair&gt; pairs) {
  
      List&lt;String&gt; undefined = new LinkedList&lt;String&gt;();
  
      Iterator&lt;_KVPair&gt; it = pairs.iterator();
      while (it.hasNext()) {
          String value = it.next().getValue();
          if (!undefined.contains(value)) {
              undefined.add(value);
          }
      }
      return undefined;
  }
  </code></pre>
  
  <p>At about 3600 pairs, 'u3' wins. At about 1500 pairs, 'u1' wins</p>