title: How is it possible for Java HashMap to perform constant time lookup O(1) for "get" operations?
body: <p>I understand the basics of how a HashMap works - hm.put(obj) finds the correct bucket to place the object into, based on the obj.hashCode value.  Then within that bucket if another object .equals(obj) then replace it, if not add it to the bucket.</p>
  
  <p>But I am unclear on how HashMap.put and HashMap.get can be constant time O(1).  As I understand it, the number of buckets should be based on the hashcodes, so putting 100 objects into a hashmap will (roughly) create 100 buckets (I do understand there are sometimes collisions in hashcodes, so it could be less than 100 but not often).  </p>
  
  <p>So as the number of objects added to a hashmap grows, so does the number of buckets - and since collisions are rare then doesn't that mean that the number of buckets grows almost linearly with the number of objects added, in which case HashMap.put/HashMap.get would be O(n) as it has to search over every bucket before it finds the right one.</p>
  
  <p>What am I missing?</p>