title: Why is iterating a map slower than iterating a list?
body: <p>I was asked this question in an interview and the interviewer wanted to discuss the trade-offs on all the approaches I could think of:</p>
  
  <blockquote>
    <p>Design and implement a TwoSum class. It should support the following
    operations: add and find.</p>
    
    <p>add - Add the number to an internal data structure.<br>
      find - Find if there exists any pair of numbers whose sum is equal to the value.</p>
  </blockquote>
  
  <p>I came up with the below solution first which is very straight forward.</p>
  
  <p><strong>Design1:</strong></p>
  
  <pre><code>public class TwoSumDesign1 {
    private final Map&lt;Integer, Integer&gt; map = new HashMap&lt;Integer, Integer&gt;();
  
    public void add(int number) {
      map.put(number, map.getOrDefault(number, 0) + 1);
    }
  
    public boolean find(int value) {
      for (Map.Entry&lt;Integer, Integer&gt; entry : map.entrySet()) {
        int i = entry.getKey();
        int j = value - i;
        if ((i == j &amp;&amp; entry.getValue() &gt; 1) || (i != j &amp;&amp; map.containsKey(j))) {
          return true;
        }
      }
      return false;
    }
  }
  </code></pre>
  
  <p>But then doing some research I found out that we can use List to store all the numbers and iterating a list is faster than iterating <code>keySet</code>, but I still don't understand why?</p>
  
  <p>Referenced from : <a href="https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html" rel="nofollow noreferrer">https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html</a></p>
  
  <blockquote>
    <p>Iteration over collection views requires time proportional to the "capacity" of the HashMap instance (the number of buckets) plus its size (the number of key-value mappings). Thus, it's very important not to set the initial capacity too high (or the load factor too low) if iteration performance is important.</p>
  </blockquote>
  
  <p><strong>Design2:</strong></p>
  
  <pre><code>public class TwoSumDesign2 {
    private final List&lt;Integer&gt; list = new ArrayList&lt;Integer&gt;();
    private final Map&lt;Integer, Integer&gt; map = new HashMap&lt;Integer, Integer&gt;();
  
    // Add the number to an internal data structure.
    public void add(int number) {
      if (map.containsKey(number))
        map.put(number, map.get(number) + 1);
      else {
        map.put(number, 1);
        list.add(number);
      }
    }
  
    // Find if there exists any pair of numbers whose sum is equal to the value.
    public boolean find(int value) {
      for (int i = 0; i &lt; list.size(); i++) {
        int num1 = list.get(i), num2 = value - num1;
        if ((num1 == num2 &amp;&amp; map.get(num1) &gt; 1) || (num1 != num2 &amp;&amp; map.containsKey(num2)))
          return true;
      }
      return false;
    }
  }
  </code></pre>
  
  <p>Can anyone explain what all the trade-offs are that we should think about with this problem and why the second solution is faster than iterating the map's <code>keySet</code>?</p>