title: How are HashMap et al really O(1)?
body: <p>I'm studying Java collection performance characteristics, Big O notation and complexity, etc.  There's a real-world part I can't wrap my head around, and that's why HashMap and other hash containers are considered O(1), which should mean that finding an entry by key in a 1,000 entry table should take about the same time as a 1,000,000 entry table.</p>
  
  <p>Let's say you have HashMap myHashMap, stored with a key of first name + last name.  If you call myHashMap.get("FredFlinstone"), how can it instantly find Fred Flinstone's Person object?  How can it not have to iterate through the set of keys stored in the HashMap to find the pointer to the object?  If there were 1,000,000 entries in the HashMap, the list of keys would also be 1,000,000 long (assuming no collision), which must take more time to go through than a list of 1.000, even if it were sorted.  So how can the get() or containsKey() time not change with n?</p>
  
  <p>Note: I thought my question would be answered in <a href="https://stackoverflow.com/questions/1055243/is-a-java-hashmap-really-o1">Is a Java hashmap really O(1)?</a> but the answers didn't really address this point.  My question is also not about collisions.</p>