title: java 8, most efficient method to return duplicates from a list (not remove them)?
body: <p>I have an <code>ArrayList</code> of Strings, and I <strong>want to find and return all values which exist more than once in the list</strong>. Most cases are looking for the opposite (removing the duplicate items like distinct()), and so example code is hard to come by.</p>
  
  <p>I was able to come up with this:</p>
  
  <pre><code>public synchronized List&lt;String&gt; listMatching(List&lt;String&gt; allStrings) {
  
      long startTime = System.currentTimeMillis();
  
      List&lt;String&gt; duplicates = allStrings.stream().filter(string -&gt; Collections.frequency(allStrings, string) &gt; 1)
              .collect(Collectors.toList());
  
      long stopTime = System.currentTimeMillis();
      long elapsedTime = stopTime - startTime;
      LOG.info("Time for Collections.frequency(): "+ elapsedTime);
  
      return duplicates;
  }
  </code></pre>
  
  <p>But this uses <code>Collections.frequency</code>, which loops through the whole list for each item and counts every occurrence. This takes about <strong>150ms</strong> to run on my current list of about <strong>4,000 strings</strong>.
  This is a bit slow for me and will only get worse as the list size increases. I took the frequency method and rewrote it to return immediately on the 2nd occurrence:</p>
  
  <pre><code>protected boolean moreThanOne(Collection&lt;?&gt; c, Object o) {
      boolean found = false;
      if (o != null) {
          for (Object e : c) {
              if (o.equals(e)) {
                  if (found) {
                      return found;
                  } else {
                      found = true;
                  }
              }
          }
      }
      return found;
  }
  </code></pre>
  
  <p>and changed my method to use it:</p>
  
  <pre><code>public synchronized List&lt;String&gt; listMatching(List&lt;String&gt; allStrings)   {
      long startTime = System.currentTimeMillis();
  
      List&lt;String&gt; duplicates = allStrings.stream().filter(string -&gt; moreThanOne(allStrings, string))
              .collect(Collectors.toList());
  
      long stopTime = System.currentTimeMillis();
      long elapsedTime = stopTime - startTime;
      LOG.info("Time for moreThanOne(): "+ elapsedTime);
  
      return duplicates;
  }
  </code></pre>
  
  <p>This seems to work as expected, but does not really increase the speed as much as I was hoping, clocking in at about <strong>120ms</strong>. This is probably due to it also needing to loop through the whole list for each item, but I am not sure how to avoid that and still accomplish the task.</p>
  
  <p>I know this might seem like premature optimization, but my List can easily be <strong>1mil+</strong>, and this method is a critical piece of my app that influences the timing of everything else.</p>
  
  <p>Do you see any way that I could further optimize this code? Perhaps using some sort of fancy Predicate? An entirely different approach?</p>
  
  <p><strong>EDIT:</strong>
  Thanks to all your suggestions, I was able to come up with something significantly faster:</p>
  
  <pre><code>public synchronized Set&lt;String&gt; listMatching(List&lt;String&gt; allStrings) {
  
      Set&lt;String&gt; allItems = new HashSet&lt;&gt;();
      Set&lt;String&gt; duplicates = allStrings.stream()
              .filter(string -&gt; !allItems.add(string))
              .collect(Collectors.toSet());
  
      return duplicates;
  }
  </code></pre>
  
  <p>Running under the same conditions, this is able to go through my list in <strong>&lt;5ms</strong>.
  All the HashMap suggestions would have been great though, if I had needed to know the counts. Not sure why the <code>Collections.frequency()</code> method doesn't use that technique.</p>