В чем преимущество хеш таблиц перед списком

Обновлено: 06.07.2024

Прежде чем говорить о хеш-таблицах, давайте поговорим о технологии хеширования.
Что такое технология хеширования? Одним словом,Технология хеширования - это технология поиска, и это технология поиска "за один шаг".
Почему это можно сделать за один шаг?
Прежде чем говорить о технологии хеширования, давайте вспомним двоичный поиск по таблице последовательностей, интерполяционный поиск, как работают эти методы поиска.
В этих методах поиска мы сначала определяем ключ значения для поиска, затем сравниваем элементы в наборе элементов для поиска, а затем находим индекс элемента, который нужно найти.
А как работает технология хеширования?
В технологии поиска по хешам нет необходимости сравнивать одно за другим. После определения ключа значения для поиска ключ передается в вычисление через функцию f. Результатом вычисления является поиск индекса позиции элемента
Подведем итоги:
Порядок / Дихотомия / Поиск различий: чтобы найти элемент, нажмите клавишу -> Сравните с элементом в наборе, который нужно найти -> Найдите индекс позиции элемента, который нужно найти
Поиск по хэшу: чтобы найти элемент, ключ-> напрямую вычислить позицию индекса элемента, который нужно найти, с помощью функции f

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

1.2 Преимущества и недостатки хеш-таблиц

преимущество:
1. Процесс сравнения упрощен, а эффективность значительно повышена.

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

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

1.3 Ключевой проблемой хеш-таблицы является построение хеш-функции.

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

1.4 Ключевой проблемой хеш-таблицы является обработка хеш-конфликтов.

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

1.5 Анализ производительности хеш-таблицы

2.1 Определение узла

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

Исходный код реализации узла выглядит следующим образом

2.2 Итератор

2.3 Структура данных

Сначала посмотри на этоПараметры шаблона,
Есть много параметров шаблона, включая следующие

В файле <stl_hash_fun.h> есть несколько готовых хэш-функций, которые используются для вычисления местоположения поискового элемента.
, а затем смотрим на негореализация ведер, Вы видите, что ведра - это по сути вектор
Наконец, мы должны обратить внимание на один момент. Хотя метод адресации цепочки не требует, чтобы размер таблицы был простым числом, SGI STL по-прежнемуСоздайте размер таблицы с помощью простых чисел
и вычислить 28 простых чисел для доступа в любое время, чтобы запросить простое число, которое ближе всего к определенному числу и превышает его из 28 простых чисел.

3.1 Конфигуратор пространства

Конфигуратор выделенного узла определен в HashTable для лучшего открытия пространства в единицах узлов

функция конфигурации узла,

Функция освобождения узла

3.2 Конструктор

Например, если я хочу построить хеш-таблицу с 50 узлами, я создаю ее следующим образом

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

по сути вызывает initialize_buckets, давайте посмотрим, как выполняется initialize_buckets

Примечание. Функция next_size (n) возвращает простые числа, близкие к n, но больше n в таблице простых чисел.
Видно, что в initialize_buckets сначала вычисляется размер области сегментов простых чисел, близких к n, а затем в него заполняется нулевой указатель типа node *

3.3 Вставить функцию Insert

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

Исходный код всего процесса реконструкции выглядит следующим образом

Если вам не нужно перестраивать или после того, как перестройка завершена, перейдите кВыполните операцию вставки нового узла (нужно убедиться, что вставленный узел не повторяется)

3.4 Функция определения адреса элемента bkt_num

Решение адреса элемента заключается в том, чтобы выяснить, в каком сегменте находится элемент. Изначально это задача hash_function. SGI инкапсулирует эту задачу на одном уровне и сначала передает ее bkt_num.
затем вызовите hash_function из этой функции, чтобы получить исполняемый файл,
Почему вы хотите это сделать? Поскольку некоторые элементы, такие как строки, нельзя использовать для непосредственной модуляции размера hash_table. В настоящее время некоторые преобразования должны выполняться с помощью функции bkt_num.

Вышеупомянутый вызов <stl_hash_fun.h> определяет несколько готовых хеш-функций.
ничего не делает для хэш-функции целочисленного типа, такой как char int long, но возвращает исходное значение
Существует процесс преобразования для массива символов const char *, см. исходный код ниже

Как видно из вышеизложенного, хеш-таблица не может обрабатывать элементы, отличные от перечисленных выше типов.
Например, строка double float, x хочет обрабатывать эти типы, вы должны сами определить для них hash fu

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

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

Мотивация использовать хеш-таблицы

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

Контейнер \ операция	insert	remove	find
Array	O(N)	O(N)	O(N)
List	O(1)	O(1)	O(N)
Sorted array	O(N)	O(N)	O(logN)
Бинарное дерево поиска	O(logN)	O(logN)	O(logN)
Хеш-таблица	O(1)	O(1)	O(1)

Все данные при условии хорошо выполненных контейнерах, хорошо подобранных хеш-функциях

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

Понятие хеш-таблицы

Хеш-таблица — это контейнер, который используют, если хотят быстро выполнять операции вставки/удаления/нахождения. В языке C++ хеш-таблицы скрываются под флагом unoredered_set и unordered_map. В Python вы можете использовать стандартную коллекцию set — это тоже хеш-таблица.
Реализация у нее, возможно, и не очевидная, но довольно простая, а главное — как же круто использовать хеш-таблицы, а для этого лучше научиться, как они устроены.

Для начала объяснение в нескольких словах. Мы определяем функцию хеширования, которая по каждому входящему элементу будет определять натуральное число. А уже дальше по этому натуральному числу мы будем класть элемент в (допустим) массив. Тогда имея такую функцию мы можем за O(1) обработать элемент.

Теперь стало понятно, почему же это именно хеш-таблица.

Проблема коллизии

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

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

Решения проблемы коллизии методом двойного хеширования

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

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

Мы будем рассматривать сначала элемент s, потом s + t, затем s + 2*t и т.д. Естественно, чтобы не выйти за границы массива, мы обязаны смотреть на номер элемента по модулю (остатку от деления на размер массива).

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

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

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

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

Помня о данной проблеме построим наш класс.

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

Из необходимых методов осталось еще реализовать динамическое увеличение, расширение массива — метод Resize.

Увеличиваем размер мы стандартно вдвое.

Немаловажным является поддержание асимптотики O(1) стандартных операций. Но что же может повлиять на скорость работы? Наши удаленные элементы (deleted). Ведь, как мы помним, мы ничего не можем с ними сделать, но и окончательно обнулить их не можем. Так что они тянутся за нами огромным балластом. Для ускорения работы нашей хеш-таблицы воспользуемся рехешом (как мы помним, мы уже выделяли под это очень странные переменные).

Теперь воспользуемся ими, если процент реальных элементов массива стал меньше 50, мы производим Rehash, а именно делаем то же самое, что и при увеличении таблицы (resize), но не увеличиваем. Возможно, это звучит глуповато, но попробую сейчас объяснить. Мы вызовем наши хеш-функции от всех элементов, переместим их в новых массив. Но с deleted-элементами это не произойдет, мы не будем их перемещать, и они удалятся вместе со старой таблицей.

Но к чему слова, код все разъяснит:

Ну теперь мы уже точно на финальной, хоть и длинной, и полной колючих кустарников, прямой. Нам необходимо реализовать вставку (Add), удаление (Remove) и поиск (Find) элемента.

Начнем с самого простого — метод Find элемент по значению.

Далее мы реализуем удаление элемента — Remove. Как мы это делаем? Находим элемент (как в методе Find), а затем удаляем, то есть просто меняем значение state на false, но сам Node мы не удаляем.

Ну и последним мы реализуем метод Add. В нем есть несколько очень важных нюансов. Именно здесь мы будем проверять на необходимость рехеша.

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

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

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

Недостатки

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

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

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

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

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

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

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

Оригинал: Hash Tables-Theory and Practice
Автор: Mihalis Tsoukalos
Дата публикации: 12 октября 2015 г.
Перевод: A.Панин
Дата перевода: 13 октября 2015 г.

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

Постановка задачи

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

В следующем выводе приводится информация о количестве слов в каждом из упомянутых файлов:

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

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

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

Теоретическая информация

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

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

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

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

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

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

В хэш-таблице с "корректным" количеством корзин средняя цена каждой операции поиска значения не зависит от количества элементов таблицы.

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

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

Хэш-таблицы также имеют некоторые недостатки:

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

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

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

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

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

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

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

Рисунок 1. Простая хэш-таблица

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

Не следует создавать слишком большое количество корзин; следует создавать ровно столько корзин, сколько требуется.

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

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

Каждая корзина должна содержать одно и то же количество ключей или, по крайней мере, их сопоставимые количества (это очень желательное свойство).

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

Добавление, удаление и поиск элементов

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

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

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

Реализация на языке программирования C

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

В Листинге 1 показан исходный код приложения на языке C из файла ht1.c.

Листинг 1. ht1.c

Более удачная реализация хэш-таблицы на языке программирования C

Код второй реализации хэш-таблицы будет сохранен в файле с именем ht2.c. В данной реализации также используются отдельные цепочки. Большая часть кода на языке C данной реализации полностью идентична коду из файла с именем ht1.c, за исключением кода хэш-функции. Код модифицированной хэш-функции выглядит следующим образом:

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

Тестирование производительности

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

Все программы компилируются с помощью следующей команды:

Надежная утилита time вывела следующую информацию после четырехкратного исполнения программы ht1 с использованием четырех различных размеров хэш-таблицы:

На Рисунке 2 представлен график времени исполнения программы на основе исходного кода из файла ht1.c с четырьмя различными значениями константы TABLESIZE. Проблема реализации хэш-таблицы из файла ht1.c заключается в том, что производительность хэш-таблицы с 101 корзиной практически равна производительности хэш-таблицы с 1001 корзиной!

Рисунок 2. Время исполнения программы на основе исходного кода из файла ht1.c при использовании четырех различных значений константы TABLESIZE

А это результаты исполнения программы на основе исходного кода из файла ht2.c:

На Рисунке 3 показан график времени исполнения программы на основе исходного кода из файла ht2.c при использовании пяти различных значений константы TABLESIZE. Все значения размера хэш-таблицы являются простыми числами. Причина использования простых чисел заключается в том, что они лучше подходят для выполнения операций деления с остатком. Это объясняется тем, что простое число не имеет положительных делителей кроме единицы и самого себя. В результате произведение простого числа и другого целого числа будет иметь меньше положительных делителей, чем произведение не являющегося простым числа и другого целого числа.

Рисунок 3. График времени исполнения программы на основе исходного кода из файла ht2.c при использовании пяти различных значений константы TABLESIZE

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

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

На Рисунке 4 показано количество ключей в каждой корзине двух хэш-таблиц: с 97 корзинами и с 997 корзинами. Хэш-таблица с 997 корзинами соответствует требованиям к равномерному заполнению корзин, в то время, как в хэш-таблице с 97 корзинами наблюдается еще более равномерное распределение ключей. Тем не менее, в каждой из корзин хэш-таблиц большего размера всегда размещается меньшее количество ключей, что подразумевает размещение меньшего количества ключей в каждом из связанных списков, которое положительно влияет на на время поиска ключей.

Рисунок 4. Количество ключей в каждой корзине двух хэш-таблиц с различным количеством корзин

Заключение

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

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

Давайте рассмотрим следующую проблему. В массиве хранится набор разных строк:

То есть в среднем такие операции поиска весьма медленны.

Здесь и приходят на помощь хеш-таблицы.

Как это получается?

Массиву без разницы, какие конкретно элементы записаны в каких конкретно смещениях.

В хеш-таблице дела обстоят не так. Для каждого элемента там вычисляется своё уникальное смещение, которое нельзя выбрать произвольно. Если мы добавим в хеш-таблицу несколько элементов подряд, то их смещения могут получиться не 0, 1, 2, 3. а, например, 0, 54, 16, 11, 2. и никак иначе.

Занимается вычислениям смещений специальная хеш-функция . Она берёт значение элемента и делает из него хеш (hash). Это переводится как "крошить", "рубить", "путать". В общем, я бы назвал это окрошкой.

Как именно функция получает хеш, мы рассмотрим позже. Пока можно считать её "чёрным ящиком", который для каждого уникального значения (числа, строки, объекта) выдаёт другое уникальное значение в виде целого числа. Это целое число и будет смещением в массиве.

Таким образом, поиск в массиве элемента по его значению теперь занимает всего одну итерацию:

Получить из значения хеш → взять элемент со смещением, равным хешу

Теперь рассмотрим, как устроена

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

Вот самый примитивный пример:

Допустим, у нас есть 10 строк разной длины (от 1 символа до 10). Тогда в качестве хеша можно взять длину строки. Строка с длиной 1 даст хеш 1, строка с длиной 2 даст хеш 2, и т.д.

Другой вариант: каждая строка начинается с разной буквы. Тогда строка, которая начинается с "A", даст хеш 0, строка, которая начинается с "B", даст хеш 1, и т.д.

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

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

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

Значит, если просто взять строку и представить её как целое число, то это число и будет смещением, куда нужно записать строку.

Но возникает проблема

Строка длиной 8 символов – это 64-битное число. Массив для хранения смещений таких строк должен состоять из 2^64 элементов, что просто невозможно. И ведь это всего 8 символов, а строки имеют неограниченную длину.

Поэтому поступают следующим образом:

Для массива хеш-таблицы выбирается какая-то длина. Можно выделить 10 элементов, или 1000, или миллион, это неважно. Сколько есть – столько и есть.

Вычислив хеш строки (N-битное число), мы берём остаток от деления этого числа на длину нашего массива. Что это дает: какое бы ни было число N, остаток от деления на M всегда находится в пределах от 0 до M-1, то есть всегда помещается в диапазон возможных смещений в нашем массиве.

Но возникает другая проблема

Очевидно, что если взять, например, 100 чисел и вычислить от каждого остаток от деления на 10, то мы получим совпадающие остатки. Например, у чисел 0..9 остаток от деления на 10 равен 0..9. У чисел 10..19 остаток от деления на 10 также равен 0..9, и т.д.

То есть, для 100 уникальных чисел 0..99 мы получили только 10 уникальных хешей 0..9. Это значит, что возникла

Коллизия хешей

Коллизия – это столкновение. Она возникает, когда у двух разных чисел вычисляется один и тот же хеш.

Мы должны записать в массив значение с соответствующим ему смещением, но там уже записано какое-то другое значение с таким же смещением.

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

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

Что-то напоминает, да? Ведь мы с этого и начали. Была проблема перебора элементов в массиве, и мы хотели уйти от неё с помощью хеш-таблицы, но снова вернулись к перебору.

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

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

Читайте также: