How is the time of adding an element to the HashMap data structure determined?

The time complexity of adding an element to a HashMap in Java is usually considered to be close to constant — O(1). This is achieved by using a hash function that computes the index of the bucket for storing the key-value pair.

However, in the worst case, if many keys hash to the same bucket (collisions), the time can degrade to O(n), where n is the number of elements in that bucket. Modern implementations of HashMap (starting from Java 8) convert a linked list to a balanced tree (TreeNode) when there are many collisions, which improves search and insertion times to O(log n) in the worst case.

Thus, the time to add an element is determined by:

• computing the hash code of the key,
• determining the bucket,
• inserting into the data structure of the bucket (list or tree).

Example of adding an element:

HashMap<String, Integer> map = new HashMap<>();
map.put("key", 42); // adding an element with the key "key"