Как понимать и кодировать хеш-таблицы
Введение
По данным statista, общий объем данных по всему миру в 2020 году равен 149 зеттабайтам. При таком большом объеме глобальных данных, который с каждым годом растет быстрее, очевидно, что способность эффективно хранить данные стала одной из ключевых проблем в компьютерных науках. В этой статье мы рассмотрим одну из наиболее часто используемых структур для хранения данных: хеш-таблицу.
Что такое хеш-таблица?
Хеш-таблица - это структура данных, которая используется для хранения данных. Первоначально он очень похож на массив или список, но отделяется от них, позволяя очень быстро извлекать данные, независимо от их количества.
Хеш-таблица выполняет это с помощью хеш-функции. Это функция, которая сопоставляет индекс хеш-таблицы со значением хранимых данных. Это означает, что в отличие от других структур данных временная сложность поиска элементов всегда равна единице.
Давайте посмотрим на пример хеш-таблицы в сравнении с линейным массивом / списком. Изначально эти двое выглядят совершенно одинаково.
Однако, если мы хотим найти Криса в этом примере, разница между этими двумя станет очень очевидной. В массиве мы не знаем заранее, где хранится Крис. Это означает, что нам придется просматривать каждый индекс, пока он не будет соответствовать нашим критериям поиска.
На то, чтобы найти Криса, потребовалось три попытки. Это может показаться небольшим, но в большем массиве это может занять намного больше времени. Особенно, если данные, которые мы ищем, хранятся в конце массива. Вот здесь и пригодится хеш-таблица. Для простоты давайте рассмотрим тот же пример, что и раньше.
Потребовалась одна попытка найти Криса с помощью хеш-таблицы. Более того, всегда потребуется одна попытка найти любой элемент в любой хеш-таблице. Это из-за хэш-функции, которая показывает расположение элемента на основе значения элемента.
Хеш-функции
Предыдущий пример показал, что магия хеш-таблицы проистекает из магии хеш-функции. Есть много способов создать хэш-функцию, но общая цель всегда состоит в том, чтобы использовать значение данных в качестве входных и получать индекс в качестве выходных. В этом примере мы будем использовать это как хеш-функцию:
index = ((буквенное значение первой буквы) - 1)% 5
С помощью этой хеш-функции мы можем создать хеш-таблицу. Имейте в виду, что «алфавитное значение первой буквы» относится к тому месту в алфавите, где эта буква может быть найдена. Итак, для a это значение равно 1, для b это значение равно 2 и т. Д.
В этом примере показано, как заполняется хеш-таблица с помощью хеш-функции. Однако в этом примере также показана хеш-таблица, которая заполнена идеально, причем два разных хеш-значения никогда не совпадают. К сожалению, это не всегда так. Фактически, довольно часто две разные хеш-функции генерируют один и тот же индекс. Это называется столкновением.
Столкновения
Коллизия возникает, когда две разные хеш-функции генерируют один и тот же индекс. Это проблема, потому что один индекс не может содержать несколько значений. Для решения этой проблемы существует несколько доступных методов.
Первый возможный метод называется открытая адресация. Этот метод разрешает конфликты, просматривая массив в поисках неиспользуемого индекса. Есть несколько способов сделать это, но наиболее распространенный из них называется линейным зондированием. Этот метод использует линейный поиск для поиска пустого адреса.
Например, если мы хотим добавить «эрл» в нашу хеш-таблицу, возникнет коллизия по индексу 4. Это можно разрешить с помощью линейного зондирования. Используя эту технику, мы находим пустой адрес в индексе 6, поэтому мы можем добавить «Earl».
Имейте в виду, что хеш-функция «Earl» по-прежнему указывает на индекс 4. Это означает, что для извлечения данных вам также необходимо выполнить линейный поиск после хеширования, чтобы найти «Earl» в хеш-таблице. Это снижает скорость извлечения данных, что является недостатком открытой адресации.
Второй метод называется сцеплением (также называемым закрытой адресацией) . По сути, этот метод преобразует хеш-таблицу из одномерного массива в двухмерный массив. Таким образом, каждый индекс может содержать несколько значений, что делает невозможными коллизии.
Например, если мы хотим добавить «эрл» в нашу хеш-таблицу, столкновения с индексом 4 не будет. Это связано с тем, что (в отличие от предыдущего примера) индекс 4 теперь может содержать несколько значений.
Последний доступный вариант - изменить размер хеш-таблицы и дать ей больше адресов, чем это действительно нужно. Это снижает вероятность коллизии, потому что для каждого фрагмента данных, который необходимо сохранить, доступно несколько адресов. Хороший способ измерить это - коэффициент загрузки, который рассчитывается путем деления количества элементов, которые необходимо сохранить, на размер хеш-таблицы.
В заключение
Хеш-таблицы - отличный способ хранить данные, особенно если вы хотите хранить большие объемы данных, которые вы хотите часто использовать. Однако важно отметить, что дизайн хеш-таблицы, хеш-функции и управление конфликтами играют большую роль в качестве этой структуры данных.
Код
Хэш-таблицу легко реализовать на Python. В этом примере хеш-таблица создана с использованием объектно-ориентированного подхода. Коллизии решаются с помощью линейного зондирования, которое является вариантом открытой адресации.
