title: Is a Java hashmap search really O(1)?
body: <p>I've seen some interesting claims on SO re Java hashmaps and their <code>O(1)</code> lookup time. Can someone explain why this is so? Unless these hashmaps are vastly different from any of the hashing algorithms I was bought up on, there must always exist a dataset that contains collisions.</p>
  
  <p>In which case, the lookup would be <code>O(n)</code> rather than <code>O(1)</code>. </p>
  
  <p>Can someone explain whether they <em>are</em> O(1) and, if so, how they achieve this?</p>