Хеш-таблицы

1 711
1 Звезда2 Звезды3 Звезды4 Звезды5 Звезд (2 оценок, среднее: 4,00 из 5)
Загрузка...
  • Название: Хеш-таблица (англ. hash-table);
  • Применение: Способ хранения данных;
  • Время выполнения: зависит от реализации;
  • Сложность: Средняя;
  • Входные параметры: Строка, функция, массив;
  • Результат: Сохранения широкого или неизвестного диапазона значений в ограниченном объеме памяти;

Пример из жизни:

Чтобы разобраться что такое хеш-таблицы и для чего они нужны стоит привести очень интересный и показательный пример из жизни. Представьте, что вы работаете в библиотеке и необходимо каждому клиенту оперативно выдавать какую-нибудь книгу. Конечно, можно заранее отсортировать книги по алфавиту и производить поиск, но когда книг действительно много и поиск займет достаточное время, что может сказаться на настроениях читателей. А что если придумать набор правил при котором по названию книги будет производится мгновенный перевод в номер полки или стилажа (например, номер стилажа равен 10+[век в котором творил писатель]). Тоже самое можно сказать про некую базу клиентов спортивного клуба, у которых есть уникальная карта клиента. По фамилии, имени и отчеству можно сразу определить информацию по карте, например, количество оставшихся занятий и т.д. Или быстрый поиск цены на отдельный вид товара или абонента в телефоне. Наконец, еще один показательный пример который приходит в голову — это быстрое преобразование веб-сайта (www.adit.io) в IP — адрес (173.255.248.55) для поиска ресурса в сети.

Итак, все эти задачи объединяет одно  — есть некое правило которое перерабатывает определенный смысловой маркер(вид товара, имя абонента, название книги) в нужное значение (цену, номер телефона абонента, место книги). Для чего это нужно спросите Вы? Во-первых, такой подход призван обеспечить быстрый поиск значений разнообразных данных (даже тех, которые могут вновь добавляться). Во-вторых, выполняется необходимое преобразование или получение «понятного значения» в требуемый вид, как пример с IP-адресом. И в третьих, формируется уникальность или неповторяемость каждого объекта, что крайне важно например в некоторых задачах (таких как сохранение сессий отдельных пользователей на сервере или проверка передачи данных и т.д). Но существует несколько подводный камней такого рода решений.

Как говорится легко сказать — трудно сделать! Как было указано в примере с библиотекой необходимо придумывать некое правило хранения книг по названию. Таким образом, нужно не только прибавить  10 к значению века, в котором творил писатель, но и помнить в каком веке творил писатель. А что если писатель работал в 18 и 19 веках? А не получится ли так, что два писателя работали примерно в одних временных рамках? Конечно получится, поэтому надо очень постараться придумать настолько простое правило, чтобы не требовало больших ресурсов и услий при этом обеспечивало уникальность каждой сущности или объекта.

Определения:

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

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

  • Добавление новой пары ключ-значение
  • Поиск значения по ключу
  • Удаление пары ключ-значение по ключу

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

Теперь, если запросить номер телефона «John Smith» (как показано на рисунке), то хеш-функция обработает данную строку и вернет ключ со значением 2. Обратившись ко второму элементу массива получим номер телефона = 521-1234. 

 

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

  • Возвращала одно и то же значение для одного и того же ключа (обеспечивается уникальность элемента);
  • Работала быстро (cобстенно говоря основное преимущество хеш-таблиц перед теми же связными списками это быстрый доступ к любому элементу, которое должно обеспечиваться за время O(1));
  • Порождала хорошие ключи для равномерного распределения элементов по таблице (последнее требование минимизирует коллизии).

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

Хеширование с цепочками (открытое хеширование) — позволяют множеству элементов занимать одну и ту же позицию в хэш-таблице. Основной смысл данного метода заключается в формировании связного списка в ячейках массива. Таким образом, если для двух разных элементов вычисляется одинаковый хеш, то этот элемент добавляется в связный список. К примеру для двух абонентов: «John Smith» и «Sandra Dee» получился одинаковый хеш = 152, а значит необходимо поместить второй элемент в связный список. Обычно помещается пара ключ-значение для поиска в этом связном списке соотвествующего значения. При поиске, как и при удалении приходится проходить по списку (цепочкам), сравнивая ключи между собой на эквивалентность, пока не доберёмся до нужного.

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

Хеширование с открытой индексацией (закрытое хеширование). В отличии от первого способа происходит сохранение всех элементов в ячейках массива без использования связный списков. Сохранение происходит с помощью процедуры линейного пробирования (исследования). В этом случае при возникновении коллизии следующие за текущей ячейки проверяются одна за другой, пока не найдётся пустая ячейка, куда и помещается наш элемент. Если достигается конец массива, то происходит «перескакивание» в начало массива и продолжается последовательный перебор ячеек. Например, в конкретном случает происходит коллизия двух ключей «John Smith» и «Sandra Dee» при этом в 152 сохраняется «John Smith», а второй элемент начинает «искать» (перебирать) свободное место. К счастью следующая ячейка осказалось пустой и в нее записался объект с ключом «Sandra Dee».

Если 153 ячейка оказалась бы заполненной, то происходил бы последовательный перебор ячеек т.е. 154, 155, 156 и т.д. Как только последующая ячейка оказалось бы пустой, то элемент сохранился бы в эту ячейку. В данном случае может возникнуть так называемая проблема кластеризация. Это явление создания длинных последовательностей занятых ячеек, которое увеличивает среднее время поиска в таблице. Для преодоления этой проблемы используется способ квадратичного пробирования и двойного хеширования.

Квадратичного пробирование. Интервал между ячейками с каждым шагом увеличивается на константу. Вместо использования константного значения “пропуска”, мы используем повторную хэш-функцию, которая инкрементирует хэш-значение на 1, 3, 5, 7, 9 и так далее. Например, Это означает, что если первое хэш-значение равно h, то последующими будут h+1, h+4, h+9, h+16 и так далее.

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

Реализация

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

Метод свертки: хеш-функция формируется на основе деления элементов на состовляющие одинаковой величины. Далее, полученные кусочки (могут инвертироваться т.е. менять порядок разрядов на обратный) складываются вместе и над этой суммой производится целочисленное деление на кол-во всех элементов в hash-таблице. Таким образом, если ключом является строка ее необходимо разбить на отдельные символы и преобразовать в цифровое представление. Если строка содержит числа можно сформировать группы чисел, например, 521-1234 можно представить в виде 52, 11, 23, 4. В случае с «John Smith» преобразуем символы в численное представление 48, 97, 147, 198, 250, 303, 357, 412, 468.

 

 

Замечание: Внимательный читатель обратил вниманине на то, что если строка представляет из себя аннаграмму (слова, которые содержат аналогичные буквы [anna, nana]) , будут всегда порождать коллизии. Для того чтобы избежать этого необходимо умножить каждый элемент на номер позиции буквы в строке.

 

рис.

Шаг 1. Разбиваем элемент на составные части в виде чисел;

Шаг 2. Суммируем полученные числа (если используются анаграммы умножаем каждое число на его позицию);

Шаг 3. Производим целочисленное деление на кол-во элементов хеш-таблицы.

Метод средних квадратов. Напоминает метод свертки только после получения значения в виде суммы элементов производится операция возведения в квадрат и выделение из числа средних цифр (разрядов). Как отмечалось выше 521-1234 можно представить в виде 52, 11, 23, 4. Соотвественно, сумма = 90. Данное число нужно возвести в квадрат = 8100 и выбрать средние значения т.е. 10. После этого произвести деление с остатком.

Шаг 1. Разбиваем элемент на составные части в виде чисел;

Шаг 2. Суммируем полученные числа (если используются анаграммы умножаем каждое число на его позицию);

Шаг 3. Возводим в квадрат получившиеся число и производим выделение средних разрядов;

Шаг 4.Производим целочисленное деление на кол-во элементов хеш-таблицы.

 

Программная разработка:

Хеш-функция. Воспользуемся методом свертки. Для этого определим длину строки на строке (строка 3) и последовательно суммируем целочисленное представление символов (строка 5). Осуществляем целочисленное деление полученной суммы и возвращаем полученный хеш.

Добавление элемента. Добавление элемента происходит следующим образом. Вначале вычисляется хеш-функция для нового элемента (строка 2). Проверяем существует ли такой хеш, если нет, то записываем в хеш-таблицу значение элемента (строка 4) т.е. ячейка пуста и можно сразу записать туда элемент. В противном случае, необходимо произвести поиск элемента по ключу. Для этого «пробегаем» по всем элементам хеш-таблицы, которые находятся в ячейке с вычисленным хешем (строка 10). Если в этом массиве находим такой же элемент, то просто перезаписываем его значение (строка 12). Например, при добавлении первый раз абонента — «John Smith» ($key) с номером телефона  521-1234($value) мы перезапишем его номер телефона, если добавим второй раз такого же абонента  «John Smith»  с номером 522-9871. Соотвественно, поменяем флаг, предусмотрев в логике программы тот факт, что мы уже имеем такой элемент в хеш-таблице. В строках с 16-19 проверяется тот самый флаг $inserted, если элемента в хеш-таблице нет, то производится его добавление в конец массива элемента хеш-таблицы.

Удаление элемента. Чтобы удалить элемент необходимо найти его в хеш-таблицы. В данном случае может существовать два варианта хранения элемента. С одной стороны, один элемент может занимать одну ячейку массива хеш-таблицы (проверка строки 3-5). С другой стороны, в одной ячейке массива может содержаться множество элементов, помещенных в массив (проверка строки 7-10). Как только элемент считается найденным, то немедленно уничтожается.

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

Поделиться

Отправить ответ

avatar
wpDiscuz