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

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

Так как же это на самом деле выглядит на низком уровне? Сначала учтите, что наш список значений нужно хранить в виде массива на компьютере:

Хэш-таблица работает, позволяя нам найти правильный индекс для определенного значения из ключа, который является гораздо более описательным, чем числовой индекс.

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

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

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

Например, поиск нашей хеш-таблицы может выглядеть так:

«Джейн» —› 41523563 —› 1 —› {Телефон: 123–555–3344, компания: Big Oil}

Зачем использовать хэш-таблицу вместо простого массива

Может быть не сразу понятно, почему это так полезно.

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

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

Допустим, у нас только что были все статьи в несортированном массиве. Как мы могли найти статью? Нам придется просматривать массив поэлементно, пока мы не найдем статью, соответствующую нашему заголовку. Это займет невероятно много времени, особенно если нам нужно проверить большое количество статей.

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

Это делает хэш-таблицы одной из самых важных частей создания любого программного обеспечения. Этот словарный формат хранения данных и доступа к ним лучше всего подходит для того, как на самом деле работают приложения!

Столкновения и отдельные цепочки

Хорошо, теперь я на самом деле немного солгал, когда сказал, что время, необходимое для поиска в хеш-таблице, не зависит от размера таблицы.

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

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

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

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

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

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

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

Что дальше?

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

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

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

Какие у вас есть вопросы о Hash Tables, дайте нам знать ниже, и мы постараемся ответить на них!

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