Что такое хэш-таблица? Дайте определение хэш-таблицы. Расскажите про эффективность big O в рамках хэш-таблицы.
Данные хранятся в виде пар ключ-значение. Хэш-функции принимают ключ и возвращают выходные данные, соответствующие только этому ключу. Этот процесс называется хэшированием: однозначным сопоставлением друг другу входных и выходных данных. Хэш-функции возвращают для данных уникальные адреса в памяти. Хэш-функции разработаны для оптимизирования поиска, вставки и удаления. Хэш-коллизиями называются ситуации, когда для двух разных входных данных функция возвращает одинаковые выходные данные. Эта проблема свойственна всем хэш-функциям. Часто она решается с помощью увеличения хэш-таблиц до огромного размера. Хэши важны для ассоциативных массивов и индексирования баз данных. Эффективность («О» большое): Индексирование: хэш-таблицы — O(1) Поиск: хэш-таблицы — O(1) Вставка: хэш-таблицы — O(1)