What is the average number of operations required to perform the main search or insert operation in a HashMap data structure?

In Java's HashMap data structure, the average number of operations for performing the main search or insert operation is O(1) — that is, constant time. This is achieved by using a hash function that computes the index for storing or searching for an element.

However, in the worst case, when there are many collisions (several keys end up in the same bucket), the time can degrade to O(n), where n is the number of elements in the bucket. Modern implementations of HashMap (starting from Java 8) use balanced trees (TreeNode) to store elements in buckets when there are many collisions, which improves the worst case to O(log n).

Example of using HashMap:

Map<String, Integer> map = new HashMap<>();
map.put("apple", 1); // insertion in O(1) on average
Integer value = map.get("apple"); // search in O(1) on average