Каждый язык называет их по-своему. В Python мы говорим о словарях. Руби, это хеши. JavaScript, мы говорим об объектах. В Java мы говорим о картах. По сути, все это встроенная в язык реализация хеш-таблицы.
Хеш-таблица - это структура данных, которая используется для хранения пар ключ-значение. Как и все в жизни, когда что-то кажется таким простым, за этим, вероятно, стоит много дисциплины и тяжелой работы. Хеш-таблицы ничем не отличаются. На самом деле это метод, используемый для преобразования диапазона значений ключа в диапазон индексов массива. (Это еще одна структура данных, с которой мы все хорошо знакомы). Хеши используются по многим причинам, в том числе:
- защита данных
- хранение данных
- аутентификация пользователя
- криптография (криптографические хэши - это совсем другая история, на которую я еще не набрался храбрости, чтобы разобраться в ней ... мы отложим это на другой раз)
- криптовалюта
В отличие от массивов, хеш-таблицы не упорядочены, и поэтому хеш-таблицы намного быстрее, чем массивы, при поиске значений, добавлении новых значений и удалении значений (O (1) vs O (n)) . (** Важно отметить, что, хотя хеш-таблицы быстро выполняют эти операции, они плохо работают, когда дело доходит до поиска, например, при нахождении минимального и максимального значений в наборе данных. Здесь более подходящим будет двоичное дерево поиска.) Хеш-таблица использует хеш-функцию для определения индекса для каждой пары "ключ-значение", где пара затем сохраняется в массиве "слотов", где можно найти желаемое значение.
Что делает хэш хорошим?
Когда дело доходит до реализации использования хеш-таблицы, есть 3 ключевых понятия.
- Хеш-код должен быть быстрым. Хеш-код должен иметь значение "О" (1) или постоянное время. Это означает, что по мере увеличения размера хэша не требуется больше времени для доступа к паре "ключ-значение". Время, необходимое для доступа к любой паре в хэше, постоянно.
- Хэш не кластеризует выходные данные по определенному индексу, а вместо этого равномерно распределяет каждую пару "ключ-значение" по своим слотам.
- Хэш детерминирован, то есть каждый раз один и тот же ключ дает один и тот же индекс.
Реализация хеш-функции
Давайте перейдем к хорошему. Задача хеш-функции - взять ключ и преобразовать его в число, которое будет индексом, в котором будет храниться пара ключ-значение. В JavaScript ключи по своей сути являются строками, поэтому функциональная хеш-функция преобразует строки в целые числа. Я использовал функцию charCodeAt(), чтобы получить кодовую точку UTF-16 для каждого символа в строке. Я собираюсь показать вам мой мыслительный процесс до конца реализации.
Вот три реализации (SPOILER: они плохие) для хеш-функции. Первая функция - лучшая из всех трех, но она медленная. Эта функция должна пройти множество раз (O (n)) в зависимости от количества слотов, доступных для ключа. Вторая функция - это просто кластер. Каждому ключу будет присвоен индекс 0. Последняя функция недетерминированная. Он присваивает случайное число каждый раз, когда проходит ключ. Это означает, что вы не всегда получите один и тот же индекс для одного и того же ключа.
Функциональный и лучший подход к хэш-функции также будет использовать печать кода UTF-16 каждого символа в строке, но также умножает значение на простое число и использует остаток от деления суммы.
…какие?
Простые числа и почему они работают
Да, вы правильно прочитали. Ниже я использовал число 31, но подойдет любое простое число. Известно, что наиболее оптимальными являются 31, 33, 37 и 41. Причина довольно сложна, но мы идем:
Простые числа не делятся ни на какие другие числа. Хеширование работает путем выдачи значения (пары «ключ-значение») в один из множества слотов, которые есть в хеш-коде для последующего быстрого извлечения. Способность хэшей определять, в каком слоте необходимо хранить значение, важна, поскольку хеши извлекают информацию (или должны извлекать информацию) за постоянное время, O (1). Самый простой способ получить информацию за постоянное время - это найти способ генерировать уникальные числа из пар "ключ-значение". Простые числа уникальны, и, следовательно, произведение простого числа на любое другое число имеет наилучшие шансы на то, чтобы быть уникальным, потому что для его создания используется простое число. Исследователи обнаружили, что использование простого числа дает лучшее распределение пар ключ-значение и меньшее количество конфликтов.
Еще одна вещь, на которую следует обратить внимание, - это использование арифметики по модулю. Это распространено в хэш-функциях, поскольку результат хеш-функции должен соответствовать диапазону слотов. Использование остатка от общего количества, разделенного на количество слотов, гарантирует, что выходные данные хэш-функции (и, следовательно, размещение значений) будут в правильном диапазоне.
Столкновения
Я уже упоминал о коллизиях, но они являются важной частью хеш-таблиц. Даже при наличии эффективной хеш-функции два ключа могут выдавать одно и то же значение. Приведенная выше хеш-функция - хороший тому пример. В реализацию следует добавить стратегию обработки коллизий. Могут быть созданы функции, которые будут принимать значение из хеш-функции и сохранять значение в этой позиции ПОСЛЕ проверки отсутствия коллизии. Мы можем использовать отдельную цепочку (чтобы каждая ячейка хеш-таблицы указывала на связанный список записей с одинаковым значением хеш-функции) или линейное зондирование (зондирование слотов до тех пор, пока пустой найден).
Используя отдельную цепочку, мы сохраняем значения, используя более сложную структуру данных, например связанный список. Это позволяет нам хранить несколько пар ключ-значение в одном индексе. При линейном зондировании ни одна пара "ключ-значение" не сохраняется в одном индексе. Мы ищем в массиве слотов, чтобы найти следующий пустой слот, если индекс для ключа уже был занят.
Реализация
Вот надежная реализация хеш-таблицы. Вы увидите нашу хеш-функцию сверху. У меня также есть функция set and get, помогающая с коллизиями. Функция set сохраняет пару ключ-значение через отдельную цепочку с использованием вложенного массива, а функция get извлекает значение из ключа или возвращает undefined, если ключ не найден.
Возвращаясь к тому, что является хорошим хешем, эта реализация обеспечивает все три фактора. Во-первых, наш хеш извлекает, добавляет и удаляет данные за постоянное время. Во-вторых, с помощью отдельной цепочки мы уменьшаем количество столкновений. Наконец, распределение индексов детерминировано. (** Edit: это не лучшая реализация. Пользователь, octree, дает в комментариях несколько отличных советов по улучшению этого. Я все еще учусь и ценю любые другие советы!)
Из всех структур данных хеш-таблица (и, возможно, массивы тоже) настолько широко используются, что большинство языков программирования имеют их встроенные реализации. Но понимание того, как структура данных работает под капотом, делает вас на один шаг ближе к написанию быстрого и эффективного кода. Хеш-таблицы не всегда являются ответом для вашего проекта, но они являются отличной отправной точкой, и для большинства проектов выполняйте свою работу!
Источники:
