В чем преимущество хеш таблиц перед списком
Оригинал: Hash Tables-Theory and Practice
Автор: Mihalis Tsoukalos
Дата публикации: 12 октября 2015 г.
Перевод: A.Панин
Дата перевода: 13 октября 2015 г.
Хэш-таблицы могут быть реализованы с помощью любого языка программирования, включая Awk. Однако, выбор языка программирования не является важным по сравнению с другими возникающими в ходе их реализации кардинальными решениями. Хэш-таблицы используются при реализации компиляторов, баз данных, систем кэширования данных, ассоциативных массивов и других механизмов и программных продуктов. Хэш-таблицы являются одними из наиболее важных структур данных, изучаемых в рамках курсов компьютерных наук.
Более удачная реализация хэш-таблицы на языке программирования C
Код второй реализации хэш-таблицы будет сохранен в файле с именем ht2.c. В данной реализации также используются отдельные цепочки. Большая часть кода на языке C данной реализации полностью идентична коду из файла с именем ht1.c, за исключением кода хэш-функции. Код модифицированной хэш-функции выглядит следующим образом:
Данная функция имеет преимущество перед функцией из прошлого примера, которое заключается в том, что учитываются значения всех символов строки, а не только ее первого символа. Исходя из этого, генерируемое число, соответствующее позиции ключа в хэш-таблице, будет больше, что подразумевает возможность использования преимуществ хэш-таблицы с большим количеством корзин.
Заключение
Хэш-таблицы являются важной частью курсов компьютерных наук и могут продуктивно использоваться при разработке программных продуктов. Я надеюсь, что данная статья поможет вам оценить их важность и понять особенности их создания и использования.
1. Основным преимуществом хэш-таблиц перед другими структурами табличных данных является скорость. Это преимущество более очевидно, когда количество записей велико. Хэш-таблицы особенно эффективны, когда максимальное количество записей может быть заранее спрогнозировано, так что массив корзин (buckets) может быть выделен один раз с оптимальным размером и никогда не изменяться в размере.
2. Если набор пар ключ-значение фиксирован и известен заранее (поэтому вставки и удаления не допускаются), можно уменьшить среднюю стоимость поиска путем тщательного выбора хэш-функции, размера таблицы сегментов и внутренних структур данных. В частности, можно разработать хэш-функцию, которая не будет иметь коллизий или даже будет совершенной. В этом случае ключи не должны храниться в таблице.
Недостатки
1. Хотя операции с хэш-таблицей в среднем занимают постоянное время, стоимость хорошей хэш-функции может быть значительно выше, чем внутренний цикл алгоритма поиска для последовательного списка или дерева поиска. Таким образом, хэш-таблицы не эффективны, когда количество записей очень мало. (Однако в некоторых случаях высокая стоимость вычисления хэш-функции может быть уменьшена путем сохранения значения хэш-функции вместе с ключом.)
2. Для некоторых приложений обработки строк, таких как проверка орфографии, хэш-таблицы могут быть менее эффективными, чем попытки, конечные автоматы или массивы Джуди. Кроме того, если не слишком много возможных ключей для хранения, то есть если каждый ключ может быть представлен достаточно малым количеством битов, то вместо хэш-таблицы можно использовать ключ непосредственно в качестве индекса в массиве значений. Обратите внимание, что в этом случае нет коллизий.
3. Записи, хранящиеся в хэш-таблице, могут быть эффективно перечислены (с постоянной стоимостью за запись), но только в некотором псевдослучайном порядке. Следовательно, не существует эффективного способа найти запись, ключ которой ближе всего к данному ключу. Для перечисления всех n записей в определенном порядке обычно требуется отдельный шаг сортировки, стоимость которого пропорциональна log(n) для каждой записи. Для сравнения, упорядоченные деревья поиска имеют стоимость поиска и вставки, пропорциональную log(n), но позволяют находить ближайший ключ примерно с той же стоимостью, и упорядоченное перечисление всех записей с постоянными затратами на запись.
4. Если ключи не сохранены (поскольку хэш-функция не содержит коллизий), может быть нелегко перечислить ключи, которые присутствуют в таблице в любой данный момент.
5. Хотя средняя стоимость операции постоянна и довольно мала, стоимость одной операции может быть довольно высокой. В частности, если в хэш-таблице используется динамическое изменение размера, операция вставки или удаления может иногда занимать время, пропорциональное количеству записей. Это может быть серьезным недостатком в реальном времени или для интерактивных приложений.
6. Хэш-таблицы в целом демонстрируют плохую привязку, т.е. данные, к которым осуществляется доступ, по-видимому, случайным образом распределяются в памяти. Поскольку хэш-таблицы вызывают скачкообразное изменение шаблонов доступа, это может вызвать пропуски в кеше микропроцессора, которые вызывают длительные задержки. Компактные структуры данных, такие как массивы осуществляющие линейный поиск, могут быть быстрее, если таблица относительно мала, а ключи компактны. Оптимальная точка производительности варьируется от системы к системе.
7. Хэш-таблицы становятся довольно неэффективными, когда существует много коллизий. В то время как крайне неравномерное распределение хэша крайне маловероятно, случайный злоумышленник со знанием хэш-функции может предоставить информацию хэшу, который создает поведение в худшем случае, вызывая чрезмерные коллизии, что приводит к очень низкой производительности, например, атака отказа в обслуживании. В критических приложениях может использоваться структура данных с лучшими гарантиями наихудшего случая; однако универсальное хэширование - рандомизированный алгоритм, который не позволяет злоумышленнику предсказать, какие входные данные вызывают поведение в наихудшем случае - может быть предпочтительным. Хэш-функция, используемая хэш-таблицей в кэше таблицы маршрутизации Linux, была изменена в Linux версии 2.4.2 в качестве меры противодействия таким атакам.
Хэш-таблицы обычно используются для реализации многих типов таблиц в памяти. Они используются для реализации ассоциативных массивов (массивов, индексами которых являются произвольные строки или другие сложные объекты), особенно в интерпретируемых языках программирования, таких как Ruby, Python и PHP.
При сохранении нового элемента в мультикарте и столкновении хэшей мультикарта безоговорочно сохраняет оба элемента.
При сохранении нового элемента в типичном ассоциативном массиве происходит коллизия хэшей, но сами фактические ключи отличаются, ассоциативный массив также хранит оба элемента. Однако, если ключ нового элемента в точности совпадает с ключом старого элемента, ассоциативный массив обычно стирает старый элемент и перезаписывает его новым элементом, поэтому каждый элемент в таблице имеет уникальный ключ.
Индексирование базы данных
Хэш-таблицы могут также использоваться в качестве дисковых структур данных и индексов базы данных (например, в dbm), хотя B-деревья более популярны в этих приложениях. В многоузловых системах баз данных хэш-таблицы обычно используются для распределения строк между узлами, что снижает сетевой трафик для хэш-соединений.
Хэш-таблицы могут использоваться для реализации кэшей, вспомогательных таблиц данных, которые используются для ускорения доступа к данным, которые в основном хранятся на медленных носителях. В этом приложении коллизии хэша можно обрабатывать, отбрасывая одну из двух коллизирующих записей - обычно стирая старый элемент, который в данный момент хранится в таблице, и перезаписывая его новым элементом, поэтому каждый элемент в таблице имеет уникальное значение хэш-функции.
Наборы (сеты)
Помимо восстановления записи, имеющей данный ключ, многие реализации хэш-таблиц также могут определить, существует ли такая запись или нет.
Следовательно, эти структуры могут использоваться для реализации заданной структуры данных, которая просто записывает, принадлежит ли данный ключ указанному набору ключей. В этом случае структуру можно упростить, исключив все части, связанные со значениями ввода. Хэширование может использоваться для реализации как статических, так и динамических наборов.
Представление объекта
Некоторые динамические языки, такие как Perl, Python, JavaScript, Lua и Ruby, используют хэш-таблицы для реализации объектов. В этом представлении ключи - это имена членов и методов объекта, а значения - указатели на соответствующий член или метод.
Уникальное представление данных
Хэш-таблицы могут использоваться некоторыми программами, чтобы избежать создания нескольких строк символов с одинаковым содержимым. Для этого все строки, используемые программой, хранятся в единственном пуле строк, реализованном в виде хэш-таблицы, которая проверяется всякий раз, когда должна быть создана новая строка. Этот метод был введен в интерпретаторах Lisp под именем согласования хэшей и может использоваться со многими другими типами данных (деревья выражений в системе символьной алгебры, записи в базе данных, файлы в файловой системе, диаграммы двоичных решений и т.д.).
Реализации в языках программирования
Многие языки программирования предоставляют функциональность хэш-таблиц либо в виде встроенных ассоциативных массивов, либо в качестве стандартных библиотечных модулей. Например, в C++ 11 класс unordered_map предоставляет хэш-таблицы для ключей и значений произвольного типа.
Язык программирования Java (включая вариант, используемый в Android) включает в себя общие коллекции HashSet, HashMap, LinkedHashSet и LinkedHashMap.
В PHP 5 и 7 движок Zend 2 и движок Zend 3 (соответственно) используют одну из хэш-функций от Daniel J. Bernstein для генерации хэш-значений, используемых при управлении отображениями указателей данных, хранящихся в хэш-таблице. В исходном коде PHP он помечен как DJBX33A.
Реализация встроенной в Python хэш-таблицы в форме типа dict, а также hash типа (%) в Perl используется внутри для реализации пространств имен и, следовательно, должна уделять больше внимания безопасности, то есть атакам на коллизии. set в Python также использует внутренние хэши для быстрого поиска (хотя они хранят только ключи, а не значения).
В Ruby хэш-таблица использует модель открытой адресации начиная с Ruby 2.4 и далее.
В стандартной библиотеке Rust обобщенные структуры HashMap и HashSet используют линейное пробирование с Robin Hood bucket stealing.
ANSI Smalltalk определяет классы Set/IdentitySet и Dictionary/IdentityDictionary. Все реализации Smalltalk предоставляют дополнительные (еще не стандартизированные) версии WeakSet, WeakKeyDictionary и WeakValueDictionary.
Переменные массива Tcl - это хэш-таблицы, а словари Tcl - это неизменяемые значения, основанные на хэшах. Функциональность также доступна в виде функций библиотеки C Tcl_InitHashTable et al. (для общих хэш-таблиц) и Tcl_NewDictObj et al. (для значений словаря). Производительность была независимо оценена как чрезвычайно конкурентоспособная.
История
Идея хэширования возникла независимо в разных местах. В январе 1953 года Ганс Питер Лун написал внутренний меморандум IBM, в котором использовалось хэширование с цепочкой. Джин Амдаль, Элейн М. Макгроу, Натаниэль Рочестер и Артур Самуэль реализовали программу с использованием хэширования примерно в одно и то же время. Открытая адресация с линейным пробированием (относительно простой степпинг) приписывается Амдалю, но Ершов (в России) придерживался той же идеи.
Хэш-таблица (hash table, hash map) представляет собой структуру данных, которая реализует абстрактный тип данных ассоциативного массива, структуру, которая может отображать ключи в значения. Хэш-таблица использует хэш-функцию для вычисления индекса, также называемого хэш-кодом, в массиве корзин (buckets) или слотов, из которого можно найти требуемое значение.
В идеале хэш-функция будет назначать каждому ключу уникальный корзину (bucket), но в большинстве конструкций хэш-таблиц используется несовершенная хэш-функция, которая может привести к коллизиям хэш-функции, когда хэш-функция генерирует один и тот же индекс для более чем одного ключа. Такие коллизии должны быть учтены каким-либо образом.
В хэш-таблице с большими размерами средняя стоимость (количество инструкций) для каждого поиска не зависит от количества элементов, хранящихся в таблице. Многие схемы хэш-таблиц также допускают произвольные вставки и удаления пар ключ-значение при (амортизированной) постоянной средней стоимости за операцию.
Во многих ситуациях хэш-таблицы оказываются в среднем более эффективными, чем деревья поиска или любая другая структура поиска таблиц. По этой причине они широко используются во многих видах компьютерного программного обеспечения, особенно для ассоциативных массивов, индексации баз данных, кэшей и наборов (сетов).
Хэширование
Идея хэширования состоит в том, чтобы распределить записи (пары ключ/значение) по массиву корзин (buckets). Учитывая ключ, алгоритм вычисляет индекс, который предлагает, где можно найти запись:
Часто это делается в два этапа:
В этом методе хэш не зависит от размера массива, а затем он сводится к индексу (число от 0 до array_size - 1), используя оператор по модулю (%).
В случае, когда размер массива равен степени двух, оставшаяся операция сокращается до маскирования, что повышает скорость, но может увеличить проблемы с плохой хэш-функцией.
Выбор хэш-функции
Основным требованием является то, что функция должна обеспечивать равномерное распределение значений хэш-функции. Неравномерное распределение увеличивает количество коллизий и стоимость их устранения. Однородность иногда трудно обеспечить с помощью дизайна, но ее можно оценить эмпирически, используя статистические тесты, например chi-squared тест Пирсона для дискретных равномерных распределений.
Распределение должно быть равномерным только для размеров таблицы, которые встречаются в приложении. В частности, если используется динамическое изменение размера с точным удвоением и уменьшением вдвое размера таблицы, то хэш-функция должна быть однородной только тогда, когда размер является степенью двойки. Здесь индекс может быть вычислен как некоторый диапазон битов хэш-функции. С другой стороны, некоторые алгоритмы хэширования предпочитают, чтобы размер был простым числом. Операция модуля может обеспечить некоторое дополнительное перемешивание; это особенно полезно с плохой хэш-функцией.
Для схем открытой адресации хэш-функция должна также избегать кластеризации, сопоставления двух или более ключей последовательным слотам. Такая кластеризация может привести к стремительному росту затрат на поиск, даже если коэффициент загрузки низкий, а коллизии нечасты. Утверждается, что популярный мультипликативный хэш обладает особенно плохим поведением кластеризации.
Считается, что криптографические хэш-функции обеспечивают хорошие хэш-функции для таблиц любого размера, либо путем уменьшения по модулю, либо путем маскировки битов. Они также могут быть уместны, если существует риск того, что злоумышленники попытаются саботировать сетевую службу, отправляя запросы, предназначенные для создания большого количества коллизий в хэш-таблицах сервера. Однако риск саботажа также можно избежать с помощью более дешевых методов (таких как применение секретной соли к данным или использование универсальной хэш-функции). Недостаток криптографических хэш-функций заключается в том, что они часто медленнее вычисляются, что означает, что в случаях, когда однородность для любого размера не требуется, некриптографическая хэш-функция может быть предпочтительнее.
Идеальная хэш-функция
Если все ключи известны заранее, можно использовать идеальную хэш-функцию для создания идеальной хэш-таблицы, в которой нет коллизий. Если используется минимальное идеальное хэширование, можно также использовать любое место в хэш-таблице.
Идеальное хэширование позволяет осуществлять поиск в постоянном времени во всех случаях. Это в отличие от большинства методов цепочки и открытой адресации, где время поиска в среднем мало, но может быть очень большим, например, O(n), когда все ключи хэшируют до нескольких значений.
Ключевые статистические данные
Критическая статистика для хэш-таблицы - это коэффициент загрузки, определяемый как
n - количество записей, занятых в хэш-таблице.
k - количество корзин (buckets)
При увеличении коэффициента загрузки хэш-таблица становится медленнее и может даже не работать (в зависимости от используемого метода). Ожидаемое свойство постоянного времени для хэш-таблицы предполагает, что коэффициент загрузки должен быть ниже некоторой границы. Для фиксированного количества сегментов время поиска увеличивается с увеличением количества записей, и, следовательно, желаемое постоянное время не достигается. В некоторых реализациях решение состоит в том, чтобы автоматически увеличивать (как правило, удваивать) размер таблицы при достижении границы коэффициента загрузки, заставляя таким образом повторно хэшировать все записи. Как пример из реальной жизни, коэффициент загрузки по умолчанию для HashMap в Java 10 составляет 0,75, что "предлагает хороший компромисс между временными и пространственными затратами".
Во-вторых, к коэффициенту загрузки, можно исследовать дисперсию количества записей на группу. Например, две таблицы имеют 1000 записей и 1000 корзин; одна имеет ровно одну запись в каждой корзине, а другая - все записи в одной корзине. Очевидно, что хэширование не работает во второй.
Низкий коэффициент загрузки не особенно выгоден. Когда коэффициент загрузки приближается к 0, доля неиспользуемых областей в хэш-таблице увеличивается, но не обязательно происходит какое-либо снижение стоимости поиска. Это приводит к потере памяти.
Я много раз заглядывал на просторы интернета, нашел много интересных статей о хеш-таблицах, но вразумительного и полного описания того, как они реализованы, так и не нашел. В связи с этим мне просто нетерпелось написать пост на данную, столь интересную, тему.
Возможно, она не столь полезна для опытных программистов, но будет интересна для студентов технических ВУЗов и начинающих программистов-самоучек.
Реализация на языке программирования C
Код первой реализации хэш-таблицы будет сохранен в файле с именем ht1.c. Реализация использует отдельные цепочки, так как их наличие вполне обоснованно. Для простоты имена двух используемых файлов заданы на уровне кода программы. После ввода данных и создания хэш-таблицы программа начинает последовательное чтение слов из второго файла с проверкой наличия каждого из этих слов в хэш-таблице.
В Листинге 1 показан исходный код приложения на языке C из файла ht1.c.
Листинг 1. ht1.c
Мотивация использовать хеш-таблицы
Для наглядности рассмотрим стандартные контейнеры и асимптотику их наиболее часто используемых методов.
Контейнер \ операция | 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) |
Все данные при условии хорошо выполненных контейнерах, хорошо подобранных хеш-функциях
Из этой таблицы очень хорошо понятно, почему же стоит использовать хеш-таблицы. Но тогда возникает противоположный вопрос: почему же тогда ими не пользуются постоянно?
Ответ очень прост: как и всегда, невозможно получить все сразу, а именно: и скорость, и память. Хеш-таблицы тяжеловесные, и, хоть они и быстро отвечают на вопросы основных операций, пользоваться ими все время очень затратно.
Постановка задачи
Задача, которую я буду рассматривать в качестве примера в рамках данной статьи, заключается в установлении количества слов из одного текстового файла, присутствующих в другом текстовом файле. Все программы из данной статьи будут использовать один и тот же текстовый файл для заполнения хэш-таблицы (этот текстовый файл будет содержать текст книги "Гордость и предубеждение"). Другой текстовый файл (содержащий текст книги "Приключения Тома Сойера") будет использоваться для тестирования производительности хэш-таблицы. Вы можете загрузить оба текстовых файла с ресурса Project Gutenberg.
В следующем выводе приводится информация о количестве слов в каждом из упомянутых файлов:
Как видите, оба текстовых файла имеют относительно большой размер, что положительно скажется на корректности тестов. В реальной жизни ваши хэш-таблицы не должны содержать такой же большой объем данных. Для того, чтобы удалить различные управляющие символы, а также символы пунктуации и числа, оба текстовых файла должны быть подвергнуты дополнительной обработке:
Причина упрощения содержимого обоих фалов состоит в том, что в случае недостаточно обработки некоторые управляющие символы могут приводить к аварийному завершению программ, созданных с использованием языка программирования C. Ввиду того, что целью данной статьи является демонстрация приемов разработки и использования хэш-таблиц, я решил упростить входные данные, а не тратить время на поиск причины аварийного завершения программы и модификацию кода на языке C.
После создания хэш-таблицы с данными из первого файла (с именем INPUT) данные из второго файла (с именем CHECK) будут использоваться для тестирования хэш-таблицы. Именно таким образом хэш-таблицы чаще всего используются на практике.
Теоретическая информация
Позвольте мне начать с определения хэш-таблицы. Хэш-таблица - это структура данных, которая содержит одну или большее количество пар ключ-значение. Хэш-таблица может содержать ключи любого типа.
Хэш-таблица использует хэш-функцию для вычисления индекса в рамках массива корзин или слотов, в котором может быть найдено корректное значение. В идеальном случае хэш-функция будет размещать каждый ключ в отдельной корзине. К сожалению, такое случается крайне редко. На практике хэш-функции работают таким образом, что в одной корзине размещается более одного ключа. Наиболее важной характеристикой хэш-таблицы является количество корзин. Количество корзин учитывается хэш-функцией. Второй наиболее важной характеристикой хэш-таблицы является используемая хэш-функция. Ключевой задачей хэш-функции является генерация равномерно распределенных хэш-значений.
На основе вышесказанного вы можете сделать вывод о том, что время поиска значения в хэш-таблице будет масштабироваться по формуле O(n/k), где n является количеством ключей, а k - размером массива хэш-таблицы. Несмотря на то, что на первый взгляд сокращение времени поиска значений кажется незначительным, вы должны понимать, что в случае использования хэш-таблицы с массивом из 20 корзин время поиска значения уменьшится в 20 раз.
Важно, чтобы хэш-функция демонстрировала постоянство поведения и генерировала одинаковые хэш-значения для идентичных ключей. Коллизия происходит тогда, когда для двух ключей генерируется одно и то же значение - и это не является чем-то необычным. Существует много способов обработки коллизий.
Хорошим решением является использование отдельных цепочек. Хэш-таблица по своей сути является массивом из указателей, каждый из которых указывает на следующий ключ с тем же хэш-значением. В случае коллизии ключ будет добавлен в течение короткого постоянного промежутка времени в начало связанного списка. Проблема в данном случае будет заключаться в том, что при необходимости поиска ключа на основе хэш-значения вам придется осуществлять поиск ключа по всему связанному списку. В худшем случае может понадобиться обход всего связанного списка - это главная причина, по которой связанный список не должен быть очень большим, исходя из чего можно сделать вывод о необходимости создания большого количества корзин.
Как вы можете предположить, разрешение коллизий связано с использованием какого-либо алгоритма линейного поиска; исходя из этого, вам понадобится хэш-функция, которая минимизирует количество коллизий настолько, насколько это возможно. Другими техниками разрешения коллизий являются открытая адресация, алгоритм Robin Hood hasing и использование двух различных хэш-функций.
В хэш-таблице с "корректным" количеством корзин средняя цена каждой операции поиска значения не зависит от количества элементов таблицы.
Хэш-таблицы особенно эффективны в том случае, если максимальное количество элементов может быть предсказано заранее, благодаря чему фрагмент памяти для хранения массива корзин оптимального размера может резервироваться однократно без последующих операций повторного резервирования.
В том случае, если набор пар ключ-значение является фиксированным и известным заранее (соответственно, операции добавления и удаления элементов не будут позволены), вы можете сократить среднюю цену операции поиска значения, выбрав корректные хэш-функцию, размер таблицы и тип внутренних структур данных.
Хэш-таблицы также имеют некоторые недостатки:
Они не предназначены для хранения отсортированных данных. Использование хэш-таблицы для сортировки данных не является продуктивным.
Хэш-таблицы не эффективны в том случае, если количество элементов очень мало, ведь, несмотря на то, что операции с хэш-таблицами выполняются в течение в среднем равных промежутков времени, цена операции хэширования с использованием качественной хэш-функции может быть значительно выше, чем цена операции поиска на основе алгоритма поиска в списке или в дереве.
При реализации определенных приложений для обработки строк, таких, как приложения для проверки орфографии, хэш-таблицы могут быть менее эффективными, чем деревья или конечные автоматы.
Несмотря на то, что средняя цена операции является постоянной и достаточно малой, цена отдельной операции может оказаться достаточно большой. В частности, если хэш-таблица использует механизм динамического изменения размера массива, для одной из операций удаления или добавления ключа может потребоваться время, пропорциональное количеству элементов таблицы. Эта особенность может превратиться в серьезный недостаток в приложениях, которые должны выводить результаты без промедления.
Хэш-таблицы работают достаточно неэффективно при наличии множества коллизий.
Как вы наверняка поняли, не каждая задача может быть решена с помощью хэш-таблиц одинаково эффективно. В любом случае, вы должны рассматривать и исследовать все доступные структуры для хранения данных перед тем, как принять решение о том, какие из них следует использовать.
На Рисунке 1 схематично изображена простая хэш-таблица с ключами и значениями. В качестве хэш-функции используется функция вычисления остатка при делении на 10; исходя из этого, потребуются десять корзин, так как при делении на 10 остаток может быть представлен лишь 10 значениями. Использование десяти корзин не является достаточно хорошей идеей, особенно в том случае, если в таблицу будет добавляться большое количество элементов, но для иллюстрации принципа работы хэш-таблицы использование такого количества корзин вполне допустимо.
Рисунок 1. Простая хэш-таблица
Подводя итог, можно сказать, что при создании хэш-таблицы необходимо следовать следующим принципам:
Не следует создавать слишком большое количество корзин; следует создавать ровно столько корзин, сколько требуется.
Хэш-функция должна обрабатывать настолько большой объем информации о ключе, насколько возможно. Это не такая уж тривиальная задача.
Хэш-функция должна генерировать различные значения для похожих ключей.
Каждая корзина должна содержать одно и то же количество ключей или, по крайней мере, их сопоставимые количества (это очень желательное свойство).
При соблюдении некоторых принципов можно снизить вероятность возникновения коллизий. Во-первых, количество корзин должно быть представлено простым числом. Во-вторых, чем больше размер массива, тем меньше вероятность возникновения коллизий. Наконец, вы должны убедиться в том, что хэш-функция является достаточно проработанной для распределения возвращаемых значений настолько равномерно, насколько это возможно.
Понятие хеш-таблицы
Хеш-таблица — это контейнер, который используют, если хотят быстро выполнять операции вставки/удаления/нахождения. В языке C++ хеш-таблицы скрываются под флагом unoredered_set и unordered_map. В Python вы можете использовать стандартную коллекцию set — это тоже хеш-таблица.
Реализация у нее, возможно, и не очевидная, но довольно простая, а главное — как же круто использовать хеш-таблицы, а для этого лучше научиться, как они устроены.
Для начала объяснение в нескольких словах. Мы определяем функцию хеширования, которая по каждому входящему элементу будет определять натуральное число. А уже дальше по этому натуральному числу мы будем класть элемент в (допустим) массив. Тогда имея такую функцию мы можем за O(1) обработать элемент.
Теперь стало понятно, почему же это именно хеш-таблица.
Тестирование производительности
Представленные тесты производительности далеки от точных и научных тестов. Они всего лишь иллюстрируют лучшие и худшие, а также корректные и некорректные параметры хэш-таблиц. Помните о том, что установить оптимальный размер хэш-таблицы не всегда просто.
Все программы компилируются с помощью следующей команды:
Надежная утилита 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. Количество ключей в каждой корзине двух хэш-таблиц с различным количеством корзин
Решения проблемы коллизии методом двойного хеширования
Мы будем (как несложно догадаться из названия) использовать две хеш-функции, возвращающие взаимопростые натуральные числа.
Одна хеш-функция (при входе 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 с нашим вставляемым значением.
Добавление, удаление и поиск элементов
Основными операциями, выполняемыми с хэш-таблицами являются добавление, удаление и поиск элементов. Вы можете использовать значение, генерируемое хэш-функцией, для установления того, где в рамках хэш-таблицы следует сохранить ключ. Впоследствии эта же хэш-функция может использоваться для установления того, где в рамках хэш-таблицы следует искать значение данного ключа.
После заполнения хэш-таблицы поиск элементов может осуществляться по аналогии их добавлением. Сначала хэш-функция применяется к значению ключа, после чего осуществляется переход к заданной позиции в массиве, обход соответствующего связанного списка и установление наличия в нем интересующего ключа. Количество шагов в описанном случае будет постоянным O(1). В худшем случае время поиска элемента в хэш-таблице может достигать O(n) тогда, когда все ключи хранятся в одной корзине. Тем не менее, вероятность такого исхода настолько мала, что в общем случае, как в идеальном случае, можно считать количество шагов постоянным O(1).
Вы можете найти множество реализаций хэш-таблиц в сети Интернет или в книгах, посвященных рассматриваемой теме. Наиболее сложным аспектом использования хэш-таблиц является выбор подходящего количества корзин, а также выбор эффективной хэш-функции, которая будет распределять значения настолько равномерно, насколько это возможно. Неравномерное распределение значений приведет к увеличению количества коллизий и, соответственно, к увеличению цены их разрешения.
Проблема коллизии
Естественно, возникает вопрос, почему невозможно такое, что мы попадем дважды в одну ячейку массива, ведь представить функцию, которая ставит в сравнение каждому элементу совершенно различные натуральные числа просто невозможно. Именно так возникает проблема коллизии, или проблемы, когда хеш-функция выдает одинаковое натуральное число для разных элементов.
Существует несколько решений данной проблемы: метод цепочек и метод двойного хеширования. В данной статье я постараюсь рассказать о втором методе, как о более красивом и, возможно, более сложном.
Читайте также: