Что такое хеш-функция и хеш-таблица

Алла: Тимофей, ты обещал рассказать, что такое хеш-таблица.
Тимофей: Да, конечно. Ваша с Васей мама работает продавцом в магазине. В магазин приходят покупатели за товарами. Каждый товар имеет определённую стоимость.
Допустим, у вашей мамы есть список, в котором она хранит все товары с их ценой. Чтобы найти товар в этом списке, в худшем случае придётся просмотреть все объекты в нём. То есть потребуется O(n)O(n) операций. Если в магазине большой ассортимент, это может занять много времени. Вряд ли покупатели захотят ждать, пока продавец найдёт нужный товар в списке.
Если потребуется удалить что-то из списка, в худшем случае это займёт линейное время.
Только операция добавления нового товара будет быстрой. Это можно сделать всего за O(1)O(1).
Гоша: А если список отсортирован, то найти товар можно быстрее. Кстати, здесь список товаров мы представляем как массив.
Какая сложность поиска в отсортированном массиве в худшем случае?
Тимофей: Да, так поиск станет намного быстрее. Но покупателям всё равно придётся ждать, пока вы выясните стоимость товара! К тому же операция удаления элемента будет также линейной, как и в случае неупорядоченного массива. А операция добавления станет ещё менее эффективной.
Какая сложность добавления элемента в отсортированный массив?
Гоша: А как же бинарное дерево поиска? В нём операции выполнялись бы за логарифмическое время.
Алла: Вот было бы здорово, если бы все эти операции выполнялись ещё быстрее. Причём вне зависимости от того, насколько богатый ассортимент в магазине.
Тимофей: На самом деле это возможно. Представь, что у твоей мамы есть помощница, которая помнит все товары и цены наизусть. Она может сразу назвать стоимость любого товара, запомнить, что товар закончился, либо у него изменилась цена.
Рассмотрим структуру данных, которая способна заменить помощницу.
Какая сложность операции обращения к элементу в массиве по его индексу?
Тимофей: Получается, если известен номер элемента в массиве для каждого товара, можно узнать его стоимость за O(1)O(1). Конечно, номера всех элементов помнит помощница вашей мамы. Но найти такую помощницу сложно, поэтому хотелось бы обходиться без её помощи.
image
Алла: Была бы такая функция, на вход которой подаётся название товара, а на выходе она бы выдавала номер ячейки массива, где расположен товар с ценой!
Скопировать код
f(помидор) = 0
f(огурец) = 1
f(авокадо) = 2
f(моцарелла) = 3
Тимофей: Для этого и существуют хеш-функции.
Хеш-функция — функция, которая обеспечивает преобразование входных данных разного типа и произвольной длины в число по определённому алгоритму. То есть на вход подаётся ключ, который преобразуется в числовое значение.
Результат вычисления хеш-функции называется хешем.
Хеш-функции используются для реализации хеш-таблиц.
Алла: А что такое хеш-таблица?
Тимофей: Хеш-таблица — структура данных, которая хранит в массиве пары ключ-значение. Индекс ключа в массиве вычисляется с помощью хеш-функции.
Причём в отличие от деревьев поиска, ключи необязательно должны быть сравнимы между собой.
Алла: В общем, понятно. А можешь привести пример хеш-функции?
Тимофей: Например, хеш-функция может возвращать значение, равное порядковому номеру первой буквы товара. Тогда, например, для «арбуз» функция вернёт 1, для «банан» — 2, а для «яблоко» — 33.
Более сложный пример — возвращать сумму номеров всех букв, входящих в название, в алфавите. Тогда для «арбуз» значение функции будет 51, для «банан» — 34, а для «яблоко» — 92.
На практике такие хеш-функции не используют. Про хеш-функции, применяемые в реальных задачах, я расскажу позже.
image
В какой ячейке хеш-таблицы будет лежать цена гречки?
Алла: А что будет, если для разных объектов хеш-функция выдаст одно и то же значение? Они будут храниться в одной ячейке хеш-таблицы?
Тимофей: Ситуация, когда хеш-функция выдаёт для разных входных данных одно и то же значение, называется коллизией.
В реализации хеш-таблицы должна быть заложена логика разрешения коллизий. Есть несколько вариантов, как с коллизиями бороться. О них я расскажу чуть позже.
image
Ключи в хеш-таблице в общем случае не упорядочены. Например, сосиска лексикографически больше колбасы, но в хеш-таблице может быть расположена в ячейке с меньшим индексом.
Значениями в хеш-таблице могут быть данные разных типов: массивы, строки, числа, кортежи, и другие структуры данных. Значением может быть даже другая хеш-таблица.
Представьте, что у вас три сайта, и вы хотите собирать статистику по посещениям всех страниц на каждом из них.
В этом случае удобно использовать такую хеш-таблицу:
Скопировать кодPYTHON
pages_visit_stats = {
    'site1':{
        'page1': 12,
        'page2': 22
    },
    'site2': {
        'page1': 2,
        'page2': 0
    },
    'site3': {
        'page1': 2,
        'page2': 0,
        'page3': 10,
    }
}
Алла: Я что-то не понимаю. В прошлых примерах на вход подавался объект, от него вычислялся хеш. После этого мы знали номер ячейки массива, в которой должен лежать этот объект. Теперь в ячейках массива лежат другие таблицы?
Тимофей: Да. Мы вычисляем значение хеш-функции от ключа. Например, от 'site1'. Допустим, получили 2. Идём в ячейку с номером 2. Эта ячейка соответствует другой хеш-таблице. Мы спрашиваем: где можно найти значение для 'page1'? Хеш-функция нам говорит, что в ячейке с номером 12. Этот номер относится уже к другому массиву. Таким образом мы узнаем, что элемент pages_visit_stats['site1']['page1'] имеет значение 12.
Это не самый сложный пример того, какой структурой данных могут быть значения в хеш-таблице.
А вот с ключами всё не так просто.
Любой неизменяемый объект может использоваться в качестве ключа, а изменяемые объекты, такие как множество, массив, или другая хеш-таблица, не могут.
Скопировать кодPYTHON
unexisting_dict = {
    [1, 2, 3]: 'key_list',
    {'a', 'b'}: 'key_set',
    {'1': 'one'}: 'key_dict'
}
Кстати, изменяемые объекты также не могут быть элементами множества. 
Скопировать кодPYTHON
unexisting_set = set([1, 2, 3])
А любые неизменяемые — могут.
Алла: А почему так?
Тимофей: Представь, что у тебя хеш-таблица, ключ в которой — массив чисел. Ты записала
пару: [1, 2]: value в свою структуру данных. Для этого от ключа был вычислен хеш и данные помещены в соответствующую ячейку.
Потом ты изменила массив. После этого потребовалось найти значение по ключу. Для этого снова было вычислено значение хеш-функции. Но ключ изменился, поэтому функция в общем случае выдаст другое значение. Осуществить поиск не получится. С удалением возникнет такая же проблема.
Алла: А почему функция выдаст другое значение в общем случае, а не в любом?
Гоша: Ну Тимофей же сказал, что иногда разным данным присваивается один и тот же хеш.
Алла: Ах, ну да, коллизии. Тимофей, расскажешь про это подробнее?
Тимофей: Да, конечно. Но сначала я приведу примеры хеш-функций и расскажу, какими свойствами должна обладать хорошая хеш-функция.
Решите задачи A, E: https://contest.yandex.ru/contest/19095/problems/