What is the average time complexity of search, insert, and delete operations by key in a HashMap?

In Java, the HashMap data structure provides the following average time complexities for the main operations:

• Search (get): O(1) — access to an element by key occurs in constant time on average.
• Insertion (put): O(1) — adding an element is also performed in average constant time.
• Deletion (remove): O(1) — removing an element by key usually takes constant time.

However, in the worst case (for example, with a large number of collisions and chains), these operations can degrade to O(n), where n is the number of elements in the table.

With the introduction of Java 8, in the case of long collision chains, a balanced tree (TreeNode) is used, which improves the worst case to O(log n).