Wat is de complexiteit van het invoegen in List en Dictionary? Wat zijn botsingen in woordenboeken?

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

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

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

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

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