Сложность вставки:

В List (например, List<T> в C#) вставка в конец — амортизированная O(1), так как при необходимости расширения массива происходит копирование, но в среднем вставка быстрая.
В Dictionary вставка — амортизированная O(1), так как используется хеш-таблица.

Коллизии в словарях — это ситуация, когда два разных ключа имеют одинаковый хеш-код, и поэтому попадают в одну и ту же корзину (bucket) хеш-таблицы. Для разрешения коллизий используются методы:

цепочки (chaining) — в одной корзине хранится список элементов;
открытая адресация (open addressing) — поиск следующей свободной ячейки.

Коллизии влияют на производительность, так как увеличивают время поиска и вставки.

Какова сложность вставки в List и Dictionary? Что такое коллизии в словарях?