title: The HashSet<T>.removeAll method is surprisingly slow
body: <p>Jon Skeet recently raised an interesting programming topic on his blog: <a href="https://codeblog.jonskeet.uk/2010/07/29/there-s-a-hole-in-my-abstraction-dear-liza-dear-liza/" rel="noreferrer">&quot;There's a hole in my abstraction, dear Liza, dear Liza&quot;</a> (emphasis added):</p>
  <blockquote>
  <p>I have a set – a <code>HashSet</code>, in fact. I want to remove some items from it… and many of the items may well not exist. In fact, in our test case, <em>none</em> of the items in the &quot;removals&quot; collection will be in the original set. This sounds – and indeed <em>is</em> – extremely easy to code. After all, we’ve got <a href="https://docs.oracle.com/javase/6/docs/api/java/util/Set.html#removeAll(java.util.Collection)" rel="noreferrer"><code>Set&lt;T&gt;.removeAll</code></a> to help us, right?</p>
  <p>We specify the size of the &quot;source&quot; set and the size of the &quot;removals&quot; collection on the command line, and build both of them. The source set contains only non-negative integers; the removals set contains only negative integers. We measure how long it takes to remove all the elements using <code>System.currentTimeMillis()</code>, which isn’t the world most accurate stopwatch but is more than adequate in this case, as you’ll see. Here’s the code:</p>
  <pre><code>import java.util.*;
  public class Test 
  { 
      public static void main(String[] args) 
      { 
         int sourceSize = Integer.parseInt(args[0]); 
         int removalsSize = Integer.parseInt(args[1]); 
          
         Set&lt;Integer&gt; source = new HashSet&lt;Integer&gt;(); 
         Collection&lt;Integer&gt; removals = new ArrayList&lt;Integer&gt;(); 
          
         for (int i = 0; i &lt; sourceSize; i++) 
         { 
             source.add(i); 
         } 
         for (int i = 1; i &lt;= removalsSize; i++) 
         { 
             removals.add(-i); 
         } 
          
         long start = System.currentTimeMillis(); 
         source.removeAll(removals); 
         long end = System.currentTimeMillis(); 
         System.out.println(&quot;Time taken: &quot; + (end - start) + &quot;ms&quot;); 
      }
  }
  </code></pre>
  <p>Let’s start off by giving it an easy job: <strong>a source set of 100 items, and 100 to remove:</strong></p>
  <pre class="lang-none prettyprint-override"><code>c:UsersJonTest&gt;java Test 100 100
  Time taken: 1ms
  </code></pre>
  <p>Okay, so we hadn’t expected it to be slow… clearly we can ramp things up a bit. How about a source of one million items and 300,000 items to remove?</p>
  <pre class="lang-none prettyprint-override"><code>c:UsersJonTest&gt;java Test 1000000 300000
  Time taken: 38ms
  </code></pre>
  <p>Hmm. That still seems pretty speedy. Now I feel I’ve been a little bit cruel, asking it to do all that removing. Let’s make it a bit easier – 300,000 source items and 300,000 removals:</p>
  <pre class="lang-none prettyprint-override"><code>c:UsersJonTest&gt;java Test 300000 300000
  Time taken: 178131ms
  </code></pre>
  <p>Excuse me? Nearly three <em>minutes</em>? Yikes! Surely it ought to be easier to remove items from a <em>smaller</em> collection than the one we managed in 38ms?</p>
  </blockquote>
  <p>Can someone explain why this is happening? Why is the <code>HashSet&lt;T&gt;.removeAll</code> method so slow?</p>