Complexity of Hashmap or Hashtable

The complexity of hashmap or hashtable is depends on many things, usually O(1) (Big O of 1). O(1) means the time to retrieve an element from the data structure is always almost equals to constant. However poor implementation of hashing can lead to the complexity of O(n). In O(1) complexity, the elements of the data structure are distributed across the buckets evenly. In O(n) complexity, the elements of the data structure are all stored in one bucket (very poor hashing implementation).

Hashmap with hashcode

In Java, HashMap works by using hashCode to locate a bucket. Each bucket is a list of items residing in that bucket. The items are scanned, using equals for comparison. When adding items, the HashMap is resized once a certain load percentage is reached. So, sometimes it will have to compare against a few items, but generally it's much closer to O(1) than O(n). For practical purposes, that's all you should need to know.

Remember that o(1) does not mean that each lookup only examines a single item - it means that the average number of items checked remains constant w.r.t. the number of items in the container. So if it takes on average 4 comparisons to find an item in a container with 100 items, it should also take an average of 4 comparisons to find an item in a container with 10000 items, and for any other number of items (there's always a bit of variance, especially around the points at which the hash table rehashes, and when there's a very small number of items).

So collisions don't prevent the container from having o(1) operations, as long as the average number of keys per bucket remains within a fixed bound.

In JDK 8, HashMap has been tweaked so that if keys can be compared for ordering, then any densely-populated bucket is implemented as a tree, so that even if there are lots of entries with the same hash code, the complexity is O(log n). That can cause issues if you have a key type where equality and ordering are different, of course.