title: LinkedHashMap complexity
body: <p>i have simple problem to find the first unique element in array A. But, what bothers me is the time complexity using different methods. I've tried this two methods so far.</p>
  
  <p>First Method:</p>
  
  <pre><code>LinkedHashMap&lt;Integer, List&lt;Integer&gt;&gt; map = new LinkedHashMap&lt;Integer, List&lt;Integer&gt;&gt;();
  for (int i = 0; i &lt; A.length; i++)
  {
      if (!map.containsKey(A[i]))
          map.put(A[i], new ArrayList&lt;&gt;());
      map.get(A[i]).add(i);
  }
  
  for (Map.Entry&lt;Integer, List&lt;Integer&gt;&gt; m : map.entrySet())
      if (m.getValue().size() == 1)
          return m.getKey();
  return -1;
  </code></pre>
  
  <p>Second Method:</p>
  
  <pre><code>    for(int i=0; i&lt; A.length; i++){
          boolean unique = true;
          nestedFor:for(int j=0; j&lt; A.length; j++){
              if(i != j &amp;&amp; A[i] == A[j]){
                  unique = false;
                  break nestedFor;
              }
          }
          if(unique)
              return A[i];
      }
      return -1;
  </code></pre>
  
  <p>Testing with array of 1000000 elements, the first method executes at ~2000ms, while the second at ~10ms. My question is: shouldn't the first method executes faster since its complexity is O(nLogn) compared to second method which complexity is O(n^2)? What am i missing here ? Below the test code:</p>
  
  <pre><code>    int[] n = new int[1000000];
      for (int i = 0; i &lt; n.length; i++)
          n[i] = new Random().nextInt(2000000);
  
      long start = System.currentTimeMillis();
      firstUnique(n);
      System.err.println("Finished at: " + (System.currentTimeMillis() - start ) + "ms");
  </code></pre>
  
  <p>EDIT:</p>
  
  <pre><code>for (int i = 0; i &lt; A.length; i++)
  {
      if (!map.containsKey(A[i]))
          map.put(A[i], new ArrayList&lt;&gt;());
      map.get(A[i]).add(i);
  }
  </code></pre>
  
  <p>Consumes 99% of execution time, while </p>
  
  <pre><code>for (Map.Entry&lt;Integer, List&lt;Integer&gt;&gt; m : map.entrySet())
      if (m.getValue().size() == 1)
          return m.getKey();
  </code></pre>
  
  <p>is always 1-3ms. So, yes filling the map is the most expensive operation. </p>
  
  <p>What would you suggest as most efficient method for this kind of problem? </p>