What is the complexity of inserting into a List and Dictionary? What are collisions in dictionaries?

Insertion complexity:

• In List (for example, List<T> in C#), inserting at the end is amortized O(1), since when the array needs to be resized, copying occurs, but on average, insertion is fast.
• In Dictionary, insertion is amortized O(1), as a hash table is used.

Collisions in dictionaries — this is a situation where two different keys have the same hash code and therefore fall into the same bucket of the hash table. Methods used to resolve collisions include:

• chaining — storing a list of elements in one bucket;
• open addressing — searching for the next free cell.

Collisions affect performance by increasing the time for search and insertion.