When the HashMap internal array is filled (more on that in the next question), it is automatically resized to be twice as large. This is usually solved by providing a good hash function with a uniform distribution. Of course, lots of collisions could degrade the performance to O(log(n)) time complexity in the worst case, when all elements land in a single bucket.
HashMap has O(1) complexity, or constant-time complexity, of putting and getting the elements. To retrieve the object by its key, the HashMap again has to calculate the hashCode for the key, find the corresponding bucket, traverse the tree, call equals on keys in the tree and find the matching one. If a pair with such key already exists in the bucket, it is replaced with a new one. So when the HashMap has determined the bucket for a key, it has to traverse this tree to put the key-value pair in its place. In Java’s HashMap, each bucket actually refers not to a single object, but to a red-black tree of all objects that landed in this bucket (prior to Java 8, this was a linked list).
There is more than one way of resolving collisions in the hash map data structures. A hashCode is not unique, however, and even for different hashCodes, we may receive the same array position.
