How is the insertion time of an element in HashMap determined in case of collision?

In HashMap, the time to insert an element in case of a collision depends on the collision resolution method. The main methods are chaining and open addressing.

• Chaining: each bucket contains a linked list or another structure where all elements with the same hash are stored. When a collision occurs, the new element is added to the list. In the worst case, insertion time is O(n), where n is the length of the list, but on average it is O(1), assuming the hash function distributes keys evenly.

• Open addressing: when a collision occurs, the next free bucket is searched (linear probing, quadratic probing, etc.). The insertion time depends on the load factor of the table, but on average it is also close to O(1).

In Android (Java), HashMap uses chaining, and starting from certain versions, when the chain length exceeds a threshold, it is converted into a balanced tree (TreeMap), which reduces the worst-case insertion time to O(log n).

Thus, the collision insertion time is determined by the data structure used to store elements in a bucket, and it generally tends toward constant time on average, but can degrade to linear or logarithmic in worst cases.