коллизия

EN: collision

Коллизия хеша возникает, когда два различных ключа дают одинаковое хеш-значение и поэтому попадают в одну и ту же корзину хеш-таблицы. Коллизии неизбежны согласно принципу Дирихле; хеш-таблицы разрешают их через chaining (связный список в корзине) или open addressing (поиск свободного слота). Большое количество коллизий деградирует среднюю O(1)-сложность операций до O(n).