хеш-таблица

EN: hash table

Структура данных, отображающая ключи в значения путём применения хеш-функции для получения индекса массива: вставка, поиск и удаление в среднем за O(1). Коллизии разрешаются цепочками (связный список в каждой корзине) или открытой адресацией (поиск следующего свободного слота); при большом числе коллизий сложность деградирует до O(n).