Что ты знаешь про хеш-таблицы? Данный вопрос за всю историю моих собеседований мне задавали лишь два раза. Я структурировал ответ и немного дополнил. Считаю этого достаточно, чтобы можно было пофлексить перед интервьюером 😎 Хеш-таблица - это структура данных, которая позволяет хранить пары «ключ-значение» и обеспечивать быстрый доступ к значениям по ключу. Основные характеристики: Хеш-функция - применяется к ключу и возвращает целочисленное хеш-значение (обычно большое число). Методы разрешения коллизий: Метод цепочек (Chaining) – каждый элемент массива хранит список (или другой контейнер) с элементами, имеющими одинаковый хеш. Открытая адресация (Open Addressing) – при коллизии ищется следующая свободная ячейка (например, линейное пробирование). Коллизия, это когда одному хешу соответствует более одного значения. Сложность операций Операция Средний случай Худший случай (при плохой хеш-функции) Вставка O(1) O(n) Поиск O(1) O(n) Удаление O(1) O(n) В Python хеш-таблицы реализованы в виде словарей (dict) и множеств (set). Как работает хеш-функция? Словари и списки в Python являются коллекциями элементов. Разница между этими коллекциями состоит в том, что в списках каждому элементу присваивается порядковый номер — индекс. В словарях таких индексов нет. Вместо этого человек сам задает значение в виде ключа, и уже это значение является аналогом индекса элемента. Процесс преобразования строк, чисел, а также кортежей в число называется хешированием. А функция, которая осуществляет этот процесс, называется хеш-функцией. А словарь, в общем смысле, называется хеш-таблицей. Процесс хеширования --name-->| hash func | --->hashValue 234 — хеш-функция — 4 'hello world' — хеш-функция — 8 (234, 'hello world') — хеш-функция — 1 Каждая хеш-функция должна обладать рядом свойств: Она должна быть детерминированной (последовательной). Передав такой функции число 234, мы получили число 4. Это значит, что в будущем каждый раз, передавая число 234, мы хотим получать индекс 4. Иначе она была бы попросту бесполезна, и мы бы не смогли обращаться к хеш-таблице. Разным входным данным должны соответствовать разные числа. Например, хеш-функция, которая возвращает 1 для всех слов, была бы довольно бесполезна в применении. Пример работы хеш-функции Итак, хеш-функция позволяет связать строку, число или кортеж с некоторым числом-индексом, то есть позволяет нам создать словарь. Давайте начнем с пустого списка: Indices: 0 1 2 ... Values: [], [], [], ... Данные будут храниться в этом списке. Допустим, что у нас есть некоторая хеш-функция, которая сможет выдать нам индексы для хранения информации. Будем хранить цены на продукты в магазине. Передадим в хеш-функцию строку 'apples'. 'apples' — хеш-функция — 3 Хеш-функция выдала число 3. Отлично, давай запишем цену яблок в элемент списка под индексом 3: [ , , , 60, , ] Теперь добавим хлеб (допустим, функция вернула индекс 0): [40, , , 60, , ] Продолжаем добавлять, пока не заполним информацию обо всех товарах в магазине: [40, 35, 89, 60, 13, 5] А теперь, когда мы заполнили базу данных магазина, используя хеш-функцию, можно узнать, сколько стоили яблоки. Ты снова обращаешься к хеш-функции и спрашиваешь у нее, под каким индексом находятся яблоки. А хеш-функция отвечает, что под индексом 3. 'apples' — хеш-функция — 3 Хеш-функция сообщила, где хранится цена на яблоки, и нам ничего не пришлось искать. Такое решение работает, так как: Хеш-функция неизменно связывает название с одним индексом. Строке «яблоки» всегда будет соответствовать один и тот же индекс. Разные строки связываются с разными индексами. Яблоки — 3, хлеб — 0. Хеш-функция знает о размере списка и всегда возвращает действительные индексы. Соединяя вместе списки и хеш-функцию, ты получаешь хеш-таблицу. Пожалуй, это самая полезная структура данных из сложных структур. Однако, скорее всего, тебе никогда не придется заниматься реализацией хеш-таблиц самостоятельно. 🎩 #python #interview