Хеш-таблицы

Хеш-таблицы

Представьте, что вы продавец в магазине. Когда клиент покупает товары, вы проверяете их цены по прайс-листу(по книге или таблице). Если записи не упорядочены по алфавиту и их очень много, то поиск, например, какого‑нибудь слова «персики» в каждой строке займёт слишком много времени. Фактически, может получиться линейный поиск, где необходимо проверять каждую запись. Это займёт времени: O(n). Если прайс-лист упорядочен по алфавиту, вы сможете воспользоваться бинарным поиском(что такое бинарный поиск?), время выполнения которого составляет всего O(log n). Предположим вы можете посмотреть 10 записей за секунду. Вы знаете, что двоичный поиск работает очень быстро. Но сам процесс поиска — это каждый раз рутинная работа даже для отсортированного списка. Пока осуществляется поиск — клиент ждёт. Гораздо удобнее было бы завести "помощника", который помнит все названия товаров и их цены. Тогда ничего искать вообще не придётся: вы спрашиваете "помощника", а он мгновенно отвечает. Получается что "помощник" может сообщать за время O(1) (почти мгновенно) цену любого товара. Соответственно он сработает ещё быстрее чем бинарный(двоичный) поиск.

Где взять такого помощника? Обратимся к структурам данных. Пока возможно вам известны две структуры данных: массивы и списки(о стеках речь не пойдёт, потому что в них нормальный поиск не возможен). Прайс-лист в магазине или книгу можно организовать в виде массива. Но каждый элемент такого прайс-листа или книги в массиве на самом деле состоит должен будет состоять из двух элементов: названия товара и цены. Если отсортировать массив по имени, вы сможете проводить по нему бинарный поиск для определения цены товара по его имени. Это значит, что поиск будет выполняться за время O(log n). Но нам ведь нужен поиск или "помощник" который бы выдавал нам цену по имени практически мгновенно! В этом нам помогут хеш-функция.

Хеш-функция

Хеш-функция представляет собой функцию, которая получает на вход строку и возвращает число. По-научному говорят, что хеш-функция "отображает строки на числа". Однако, хеш-функция должна соответствовать некоторым требованиям.

• Она должна быть последовательной. Допустим, вы передали ей строку "яблоки" и получили 5. Это значит, что каждый раз в будущем передавая ей строку "яблоки", вы получите число 5. Без этого она бесполезна.
• Разным словам должны соответствовать разные числа. Например, хеш-функция, которая возвращает 1 для каждого полученного ею слова, никуда не годится. В идеале каждое входное слово должно отображаться на своё число.

Зачем это нужно, чтобы хеш-функция связывала строки и числа? Это нужно, чтобы реализовать нашего "помощника". Начнём с пустого массива. Все цены будут храниться в этом массиве, передадим хеш-функции строку "яблоки". Хеш-функция пусть вернёт нам значение "5". Сохраним цену яблок в элементе массива под индексом 5. Добавим хлеб. Передадим хеш-функции строку "хлеб". Получим число 3. Сохраним цену на хлеб в массиве под индексом 3 и т.д. Продолжать можно действовать так, и со временем весь массив будет заполнен ценами на товары. А теперь запрашиваете: сколько стоит "хлеб"? Искать в массиве при этом ничего не нужно. Нужно просто передать строку "хлеб" хеш-функции. Результат скажет, что значение цены находится под индексом 3, мы цену оттуда и возьмём. Получается, что хеш-функция всегда сообщает нам, где цена хранится. Такое решение работает потому что:

• Хеш функция неизменно связывает название с одним числом(индексом). Каждый раз, когда она вызывается для строки "хлеб", вы получаете от неё одно и то же число. При первом вызове этой функции вы узнаете, где следует сохранить цену товара, а при последующих вызовах она сообщает, где взять эту цену.
• Хеш-функция связывает разные строки с разными числами. Для каждой строки получается своя позиция массива, в которой сохраняется цена товара.
• Хеш-функция знает размер массива и должна возвращать только действительные индексы. Таким образом, если размер массива равен 20 элементам, хеш-функция не вернёт 100, потому что это значение не является действительным индексом.

Таким образом мы создали "помощника" по магазину который всегда знает цену по названию! Связав воедино хеш-функцию и массив, мы получили структуру данных, которая называется хеш-таблица. Хеш-таблица это первая структура данных, с которой связана дополнительная логика. Массивы и списки напрямую отображаются на адреса памяти, но хеш-таблицы устроены более умно. Они определяют место хранения элементов с помощью хеш-функций.

Выше мы только что рассмотрели идеальную хеш-функцию. Она связывает товар точно с отдельной позицией массива. В реальности такого идеального однозначного сопоставления, скорее всего, не получится. Товарам придётся соседствовать. В одной позиции будут находиться несколько товаров, а другие позиции останутся пустыми. Эту ситуацию мы обсудим ниже в разделе о коллизиях. Ещё взаимно-однозначное связывание называют инъективной функцией.

Вероятно хеш-таблицы станут самой полезной из сложных структур данных, с которой вы познакомитесь. Они также известны под другими названиями: "ассоциативные массивы", "словари", "отображения", "хеш-карты", или просто "хеши". Помните описание массивов и связанных списков? Обращение к элементу массива происходит мгновенно. А хеш-таблицы используют массивы для хранения данных, поэтому при обращении к элементам они не уступают массивам.

Ассоциативный массив — абстрактный тип данных, с помощью которого хранятся пары «ключ-значение». В разных языках ему соответствуют разные типы данных. В Python — это Dictionary, т.е. Словарь (что такое словарь Python), в других языках:

• Ruby — Hash
• Lua — Table
• JavaScript — Object
• Elixir/Java — Map

Ассоциативные массивы популярны в прикладном программировании. С их помощью удобно представлять составные данные, содержащие множество различных параметров. В обычном индексированном массиве значения расположены по индексам, а значит его можно положить в память «как есть». С ассоциативными массивами все работает по-другому. У них нет индексов, которые бы могли определить порядок — значит, и нет простого способа добраться до значений. Для реализации ассоциативных массивов часто используют специальную структуру данных — хеш-таблицу. Хеш-таблица позволяет организовать данные ассоциативного массива удобным для хранения способом. Для этого хеш-таблица использует индексированный массив и функцию для хеширования ключей. При этом хеш-таблица — это не просто способ размещать данные в памяти, она включает в себя логику. Посмотрим, как ассоциативные массивы устроены внутри(они же хеш-таблицы). Скорее всего, вам никогда не придётся заниматься реализацией ассоциативных массивов или хеш-таблиц самостоятельно. В любом приличном современном языке программирования высокого уровня существует их реализация. В Python хеш-таблицы ещё называются словарями. Новая хеш-таблица задаётся пустыми фигурными скобками. Разберём подобный простой код на Python:

book = {} # book["key"] = "value"

book – это новая хеш-таблица. Добавим в неё несколько цен:

book["яблоки"] = 57.5
book["молоко"] = 78.9
book["хлеб"] = 52.5
print(book)
# {'яблоки': 57.5, 'молоко': 78.9, 'хлеб': 52.5}

Пока всё просто! А теперь запросим цену для яблок.

print(book["яблоки"]) # => 57.5 - цена

Хеш-таблица состоит из ключей и значений. В хеше book имена продуктов являются ключами, а цены – значениями. Хеш-таблица связывает ключи со значениями. Очень важно, чтобы хеш-функции в хеш-таблицах были последовательными, то есть неизменно возвращали один и тот же результат для одинаковых входных данных. Если это условие будет нарушено, вы не сможете найти свой элемент после того, как он будет помещён в хеш-таблицу!

Что такое хеширование

Любая операция внутри хеш-таблицы начинается с того, что ключ каким-то образом преобразуется в индекс обычного массива. Для получения индекса из ключа нужно выполнить два действия:

• Найти хеш, то есть хэшировать ключ
• Привести ключ к индексу — например, через остаток от деления

Хеширование — операция, которая преобразует любые входные данные в строку или число фиксированной длины. Функция, реализующая алгоритм преобразования, называется «хеш-функцией». При этом результат хеширования называют «хешем» или «хеш-суммой».

Наиболее известны CRC32, MD5, SHA и много других типов хеширования:

# В Python есть библиотека zlib, содержащая алгоритм хеширования crc32
# Этот алгоритм удобен для наглядности
import zlib

# Любые данные, которые мы хотим хешировать, представляются в виде байтовой строки
data = b"Hello, python!"
hash = zlib.crc32(data)

# Хеш всегда одинаковый для одних и тех же данных
print(hash)  # => 3159842700

С хешированием мы встречаемся в разработке. Например, идентификатор commit в git d7834a94 — это хеш, полученный в результате хеширования данных "коммита".

При записи в хеш-таблицу сначала нужно получить хеш. Затем его можно преобразовать в индекс массива — например, вычислить остаток от деления:

# Это делается для того, чтобы индексы не были слишком большими
# Чем больше размер массива, тем больше памяти он занимает
index = abs(hash) % 1000  # по модулю
print(index)  # => 700

Как хеширование работает изнутри

Рассмотрим, как работает добавление нового значения в ассоциативный массив. Напомним, в Python он представлен типом данных Dictionary. Напишем такой код:

data = {}
data["key"] = "value"

Такой простой код запускает целый сложный процесс. Для простоты рассмотрим его на Python, хотя в реальности все это происходит на более низком уровне. Опишем процесс хеширования без деталей и с упрощенным кодом.

1. Мы создаем ассоциативный массив. Внутри интерпретатора происходит инициализация индексированного массива:

internal = []

2. Далее мы присваиваем значение:

data['key'] = "value"

3. Затем интерпретатор хэширует ключ. Результатом хеширования становится число:

hash = zlib.crc32(b'key')

4. Далее интерпретатор берет число из предыдущего шага и преобразует его в индекс массива:

index = abs(hash) % 1000

5. В конце интерпретатор ищет по индексу значение внутреннего индексированного массива и записывает его в еще один массив. Первым элементом нового массива становится ключ 'key', а вторым — значение 'value':

internal[index] = ["key", "value"]

Теперь посмотрим, как работает чтение данных:

data = {}
data["key"] = "value"
print(data["key"])  # => "value"

Разберем, как этот код работает изнутри:

1. Интерпретатор хеширует ключ. Результатом хеширования становится число:

hash = zlib.crc32(b'key')

2. Число, полученное на предыдущем шаге, преобразуется в индекс массива:

index = abs(hash % 1000)

3. Если индекс существует, то интерпретатор извлекает массив и возвращает его наружу:

return internal[index] # ['key', 'value']

В следующем разделе приведены примеры использования хеш-таблиц.

Примеры использования хеш-таблиц

Хеш-таблицы повсеместно используют на практике. Рассмотрим некоторые примеры.

Хеш-таблица для поиска

В смартфоне есть удобная встроенная телефонная книга. С каждым именем связывается номер телефона. Предположим, вы хотите построить такую телефонную книгу. Имена людей в этой книге связываются с номерами. Телефонная книга должна поддерживать следующие функции:

• добавление имени человека и номера телефона, связанного с этим именем;
• получение номера телефона, связанного с введенным именем.

Такая задача идеально подходит для хеш-таблиц! Хеш-таблицы отлично работают, когда вы хотите:

• создать связь, отображающую один объект на другой;
• найти значение в списке.

Построить телефонную книгу, в общем-то, несложно. Начнём с создания хеш-таблицы:

phone_book = {}

Добавим в телефонную книгу несколько номеров:

phone_book["Иван"] = 8654329
phone_book["Саша"] = 8656654
phone_book["Маша"] = 8658321

Теперь предположим, что вы хотите найти номер телефона Ивана. Просто передайте ключ хешу:

print(phone_book["Иван"]) # => 8654329

Представьте, то же самое пришлось бы реализовывать через массив. Как бы вы это сделали? Хеш-таблицы упрощают моделирование отношений между объектами. Хеш-таблицы используются для поиска соответствий в гораздо большем масштабе. Например, вы хотите перейти на веб-сайт – допустим, ashtana.ru Ваш компьютер должен преобразовать символьное имя ashtana.ru в IP-адрес: ashtana.ru — 216.198.79.1

Для любого веб-сайта его имя преобразуется в IP-адрес: google.com — 142.250.185.238 dzen.ru — 83.222.28.15 vk.com — 87.240.137.164

Связать символьное имя с IP-адресом? Идеальная задача для хеш-таблиц! Этот процесс называется преобразованием DNS. Хеш-таблицы — всего лишь один из способов реализации такой функциональности. На компьютерах существует кэш DNS, в котором хранятся подобные сопоставления для недавно посещенных сайтов.

Исключение дубликатов

Предположим, вы проводите голосование. Естественно, каждый голосующий может проголосовать только один раз. Как проверить, что он не голосовал повторно? Когда человек приходит голосовать, вы узнаёте его полное имя, а затем проверяете по списку уже проголосовавших. Если имя входит в список, значит, этот человек уже проголосовал! В противном случае вы добавляете имя в список и разрешаете ему проголосовать. Далее предположим, что желающих проголосовать много и список уже проголосовавших достаточно велик. Каждый раз, когда кто-то приходит голосовать, вы вынуждены просматривать этот гигантский список и проверять, голосовал ли человек или нет. Однако, существует более эффективное решение: воспользоваться хешем! Сначала создадим хеш-таблицу для хранения информации об уже проголосовавших людях:

voted = {}

Когда кто-то приходит голосовать, проверьте, присутствует ли его имя в хеше:

vote = "Александр Сергеевич Пушкин" in voted

Переменная vote принимает значение True, если такой ключ "Александр Сергеевич Пушкин" есть в хеш-таблице. В противном случае она принимает значение False. С помощью этой функции можно проверить, голосовал ли человек ранее или нет!

Примерный код может выглядеть так:

voted = {}

def check_voter(name):
  if name in voted:
    print("Уже голосовал!")
  else:
    voted[name] = True
    print("Допустить к голосованию!")

Протестируем на нескольких примерах:

check_voted("Иван") # Допустить к голосованию!
check_voted("Алесандр") # Допустить к голосованию!
check_voted("Иван") # Уже голосовал!

Когда Иван голосует первый раз, программа разрешает ему проголосовать. Потом приходит Александр, который также допускается к голосованию. Но вдруг снова приходит Иван, чтобы проголосовать снова! И на этот раз у него ничего не получится!

Если бы имена проголосовавших хранились в списке, то выполнение функции со временем замедлилось бы, потому что функции пришлось бы проводить простой поиск по всему списку. Но имена хранятся в хеш-таблице, а она почти мгновенно сообщает, присутствует ли человек в списке голосовавших или нет. Проверка дубликатов происходит очень быстро!

Использование хеш-таблицы как кэша

Последний пример: кэширование. Если вы создаёте веб-сайт, то вероятно, уже слышали о пользе кэширования. Общая идея кэширования такова: допустим, вы заходите на сайт.

1. Вы обращаетесь с запросом к серверу;
2. Сервер ненадолго задумывается, генерирует веб-страницу и отправляет её вам;
3. Вы получаете и просматриваете веб-страницу.

Например, VK сервер может собирать информацию о действиях всех ваших друзей, чтобы представить её вам. На то, чтобы собрать всю информацию и представить её вам требуется пара секунд. Сервер просто заранее сам вычисляет, запоминает, а когда вы делаете запрос просто выдаёт готовый ответ. Так работает механизм кэширования. Сайт просто запоминает данные заранее, и вместо того чтобы их пересчитывать, выдаёт сразу ответ пользователю. Такой механизм как кэширование обладает следующими преимуществами:

• Вы получаете документ, например веб-страницу, намного быстрее, как и в том случае, когда вы заранее запомнили ответ на вопрос;
• Серверу сайта с механизмом кэширования приходится выполнять меньше работы при очередном одинаковом запросе от пользователей.

Когда вы посещаете сайт у которого настроено кэширование, сервер сайта сначала проверяет, хранится ли страница в кэше. Вот примерный псевдокод на Python как это может быть:

cache = {}
def get_page(url):
  if url in cache:
    return cache[url]
  else:
    data = get_data_from_server(url)
    cache[url] = data
    return data

Такой сервер выполняет работу только в том случае, если URL не хранится в кэше. Однако перед тем, как возвращать данные, вы сохраняете их в кэше. Когда пользователь в следующий раз запросит тот же URL-адрес, данные(хорошо бы ещё проверять при условии, что они не изменились!) отправляются пользователю из кэша(вместо вычислений на сервере).

Коллизии

Прежде чем понять какое быстродействие у хеш-таблиц, необходимо понять, что такое коллизия. Ключом в ассоциативном массиве или хеш-таблицы может быть абсолютно любая строка, любой длины и содержания. Но здесь есть одно противоречие:

• Все возможные ключи — это бесконечное множество;
• В качестве результата хеш-функция выдает строку фиксированной длины, то есть все выходные значения — это конечное множество.

Из этого факта следует, что не для всех входных данных найдется уникальный хеш. На каком-то этапе могут появиться дубли: под одним хешем будут лежать несколько разных значений.

Такую ситуацию принято называть коллизией. Есть несколько способов разрешения коллизий. Каждому способу соответствует свой тип хеш-таблицы:

# Пример коллизии
# Хеш-функция возвращает одинаковый хеш для разных строчных данных
import zlib
zlib.crc32(b"aaaaa0.462031558722291")  # 1938556049
zlib.crc32(b"aaaaa0.0585754039730588")  # 1938556049

Простейший способ разрешения коллизий — это открытая адресация. Она предполагает последовательное перемещение по слотам хеш-таблицы в поисках первого свободного слота, куда значение будет записано.

Второй простейший способ разрешения коллизий выглядит так: если несколько "ключей" хеш-таблицы отображаются после хеш-функции на один элемент, то по этому адресу сначала создаётся связанный список, а затем оба элемента по которым происходит коллизия сохраняются в этот список. Например, у нас в хеш-таблице строки "апельсины" и "яблоки", отображаются на один элемент после работы хш-функции, тогда в элементе хеш-таблицы создаётся связанный список. Если в дальнейшем потребуется узнать цену "апельсинов" или "яблок", работа пойдёт чуть медленнее так как провести поиск необходимо будет ещё и по связанному списку, чтобы найти уже в нём цену "апельсинов" или "яблок". Если связанный список мал, это не так страшно – поиск будет ограничен тремя или четырьмя элементами. Но если после работы хеш-функции все данные окажутся в одном связанном списке, то ситуация не лучше той, когда все элементы сразу бы хранились в связанном списке. Из этого следуют два вывода:

• выбор хеш-функции действительно очень важен. В идеале хеш-функция должна распределять ключи по всему хешу – равномерно;
• если связанные списки становятся слишком длинными, работа с хеш-таблицей сильно замедляется.

Хеш-функции играют важнейшую роль! Хорошая хеш-функция создаёт минимальное количество коллизий! Как выбрать хорошую хеш-функцию?

Быстродействие

В среднем хеш-таблицы выполняют любые операции за время O(1). Время O(1) называется постоянным временем выполнения. Это время означает, что операции выполняются почти мгновенно, само время выполнения зависит только от того как его выдаст исполнитель операции и является постоянным независимо от размера хеш-таблицы. При любом размере хеш-таблицы — 1 элемент или 1 миллиард элементов — выборка данных займёт одинаковое время. Ещё как пример постоянного времени выполнения: выборка элемента из массива по индексу. При сравнении хеш-таблицы с массивами и списками получается, что хорошие хеш-таблицы не уступают в скорости массивам при получении данных. А при вставке и удалении они также быстры как связанные списки! Получается что они берут лучшее из этих обеих структур! Но в худшем же случае они медленно выполняют все операции! Поэтому важно избегать худших случаев при работе с хеш-таблицами. А для этого следует избегать коллизий. Для предотвращения коллизий необходимы:

• Хорошая хеш-функция;
• Низкий коэффициент заполнения хеш-таблицы.

Коэффициент заполнения

Коэффициент заполнения хеш-таблицы вычисляется по простой формуле: количество элементов в таблице разделить на общее всех элементов.

Хеш-таблицы используют массив для хранения данных, поэтому для вычисления коэффициента заполнения можно подсчитать количество заполненных элементов в массиве(количество элементов в массиве разделить на размер массива).

Предположим, в хеш-таблице нужно сохранить цены 100 товаров и хеш-таблица состоит из 100 элементов. В лучшем случае каждому товару будет выделен отдельный элемент. Коэффициент заполнения этой хеш-таблицы тогда будет равен 1. А если хеш-таблица состоит всего из 50 элементов? Тогда её коэффициент заполнения будет равен 2. Выделить под каждый товар отдельный элемент ни при каких условиях не удастся, потому что элементов попросту не хватит. Коэффициент заполнения больше 1 означает, что количество элементов превышает количество свободных для них мест. С ростом коэффициента заполнения размер хеш-таблицы нужно изменить. Хеш-таблицу необходимо расширить. Расширение начинается с создания массива большего размера. Обычно в таком случае создаётся массив вдвое большего размера. Затем все элементы необходимо заново вставить в новую хеш-таблицу через её же хеш-функцию. С меньшим коэффициентом заполнения число коллизий также уменьшается! Хорошее приближённое правило: расширять хеш-таблицу если коэффициент заполнения приближается к 0.7. Но ведь на изменение размеров может уйти много времени и и вычислительных ресурсов? Да, и поэтому изменение размера не должно происходить часто! В среднем же хеш-таблицы работают за время O(1) даже с изменением размеров.

Хорошая хеш-функция

Вот мы и добрались до финального понимания хорошей хеш-функции! Хорошая хеш-функция должна обеспечивать равномерное распределение значений в хеш-таблице! Плохая хеш-функция создаёт скопления и порождает множество коллизий! Какую же хеш-функцию считать хорошей? Опять спросите вы. Думаю, нам никогда не придётся об этом беспокоиться — пусть об этом думают умные люди в тёмных кабинет Google, Yandex и т.п. компаний. Если вам действительно интересно, рассмотрите фукнцию например, CityHash. Именно её использует Google Abseil. Abseil — это набор библиотек C++ с открытым исходным кодом, созданных на основе самых фундаментальных элементов внутренней кодовой базы Google. Abseil лежит в основе кода, который пишут в Google, поэтому если в ней используется такая хеш-функция как CityHash, можно быть уверенным, что это функция как минимум неплоха. Смело применяйте её для своей хеш-таблицы!

Очень важно, чтобы хеш-функция обеспечивала хорошее распределение! Она должна распределять значения как можно шире! Худший случай — хеш-функция, которая отображает все входные строки на одну позицию в хеш-таблице!

Предположим, имеются четыре хеш-функции, которые получают строки.

1. Функция возвращает 1 для любого входного значения.
2. Функция возвращает длину строки в качестве ключа хеш-таблицы.
3. Функция возвращает первый символ строки в качестве индекса. Таким образом, все строки, начинающиеся с "а", хешируются в одну позицию.
4. Функция сначала ставит в соответствие каждой букве простое число: a = 1, b = 2, c = 3 и т.д. Для строки хеш-функцией далее становится остаток от деления суммы всех значений на размер хеша. Например, если размер хеша равен 10, то для строки "age" будет вычислен индекс или ключ (1 + 7 + 5) % 10 = 13 % 10 = 3.

Попробуйте сами запустить код в окне ниже с интерпретатором Python и повторите примеры из статьи чтобы самим увидеть и понять как всё это работает. Для этого в ячейке с кодом нажмите клавиши на клавиатуре Shift+Enter или запустите код через кнопку Run по значку ▶.