С какой вычислительной сложностью выполняются операции поиска удаления и вставки в хеш таблицах

Обновлено: 07.07.2024

Цель лекции: изучить построение функции хеширования и алгоритмов хеширования данных и научиться разрабатывать алгоритмы открытого и закрытого хеширования при решении задач на языке C++.

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

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

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

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

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

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

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

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

Хеш-таблицы должны соответствовать следующим свойствам.

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

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

Методы разрешения коллизий

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

метод цепочек (внешнее или открытое хеширование );
метод открытой адресации (закрытое хеширование ).

Метод цепочек. Технология сцепления элементов состоит в том, что элементы множества , которым соответствует одно и то же хеш- значение , связываются в цепочку- список . В позиции номер i хранится указатель на голову списка тех элементов, у которых хеш- значение ключа равно i ; если таких элементов в множестве нет, в позиции i записан NULL . На рис. 38.1 демонстрируется реализация метода цепочек при разрешении коллизий . На ключ 002 претендуют два значения, которые организуются в линейный список .

Рис. 38.1. Разрешение коллизий при помощи цепочек

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

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

При предположении, что каждый элемент может попасть в любую позицию таблицы с равной вероятностью и независимо от того, куда попал любой другой элемент, среднее время работы операции поиска элемента составляет O(1+k) , где k – коэффициент заполнения таблицы.

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

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

Рис. 38.2. Разрешение коллизий при помощи открытой адресации

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

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

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

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

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

Определение «Коллизия»

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

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

Пример Пример 1- хеш-таблица

Вероятности коллизии

Пример Пример 2- вероятность коллизий для примера 1

Разрешение коллизий

С коллизиями можно и нужно бороться. Существует несколько способов разрешения коллизий: [Источник 2]

Метод цепочек

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

Определение «Коэффициент заполнения таблицы»

Открытая адресация

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

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

Рисунок 3 - Пример хеш-таблицы с открытой адресацией

Основные типы последовательностей проб

Ниже приведены некоторые распространенные типы последовательностей проб. [Источник 3]

Линейное пробирование

Определение «Линейное пробирование»

Линейным пробированием называется метод разрешения коллизий в хеш-таблице с открытой адресацией, при котором i-ый элемент последовательности проб это h a s h ( x ) + i k m o d n , где n - размер таблицы, k - некоторая фиксированная константа.

Утверждение Об ограничениях на k Пример Пример 3- линейное пробирование

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

Квадратичное пробирование

Определение «Квадратичное пробирование»

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

Двойное хеширование

Определение «Двойное хеширование»

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

Заключение

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

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

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

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

Если я использую стандартные хеш-таблицы на таком языке, как C ++ или Java, какова будет временная сложность?

Хеш-таблицы - это O(1) среднее значение и амортизированная сложность дела, однако она страдает от O(n) наихудшего случая временной сложности. [И я думаю, что именно в этом ваше замешательство]

Хеш-таблицы страдают от O(n) наихудшей временной сложности по двум причинам:

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

Тем не менее, это считается O(1) средним и амортизированным случаем, потому что:

Очень редко многие элементы будут хешироваться с одним и тем же ключом [если вы выбрали хорошую хеш-функцию и у вас нет слишком большого баланса нагрузки.
Операция повторного хеширования, которая является O(n) , может произойти самое большее после n/2 операций, которые все предполагаются O(1) : Таким образом, когда вы суммируете среднее время на операцию, вы получаете: (n*O(1) + O(n)) / n) = O(1)

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

РЕДАКТИРОВАТЬ: Другая проблема с хеш-таблицами: кеш.
Другая проблема, при которой вы можете увидеть потерю производительности в больших хэш-таблицах, связана с производительностью кеша. Хеш-таблицы страдают от плохой производительности кеша , и, следовательно, для большой коллекции время доступа может занять больше времени, так как вам нужно перезагрузить соответствующую часть таблицы из памяти обратно в кеш.

Зависит от того, как вы реализуете хеширование, в худшем случае он может перейти к O (n), в лучшем случае это 0 (1) (обычно вы можете достичь, если ваш DS не такой большой)

Возможно, вы смотрели на космическую сложность? Это O (n). Остальные сложности, как и ожидалось, связаны с записью хеш-таблицы. Сложность поиска приближается к O (1) по мере увеличения количества сегментов. Если в худшем случае у вас есть только одна корзина в хеш-таблице, то сложность поиска будет O (n).

Изменить в ответ на комментарий Я не думаю, что правильно говорить, что O (1) - это средний случай. Это действительно (как говорится на странице википедии) O (1 + n / k), где K - размер хеш-таблицы. Если K достаточно велико, то результат будет фактически O (1). Но предположим, что K равно 10, а N равно 100. В этом случае каждая корзина будет иметь в среднем 10 записей, поэтому время поиска определенно не равно O (1); это линейный поиск до 10 записей.

Некоторые хеш-таблицы (хеширование с кукушкой) гарантировали поиск O (1)

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

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

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

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

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

В wiki, поиске и удалении есть O (n) (я думал, что точка хеш-таблиц должна иметь постоянный поиск, так что точка, если поиск - O (n)).

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

Если я использую стандартные хеш-таблицы на языке С++ или Java, что я могу ожидать от сложности времени?

Хэш-таблицы - это O(1) средний и amortized сложность, однако она страдает от сложности O(n) наихудшего случая. [И я думаю, что это где твоя путаница]

Хэш-таблицы страдают от O(n) худшей сложности по двум причинам:

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

Однако он считается O(1) средним и амортизированным, потому что:

Очень редко многие элементы будут хэшироваться с одним и тем же ключом [если вы выбрали хорошую хэш-функцию, и у вас слишком большой баланс нагрузки.
Операция rehash, которая O(n) , может произойти после n/2 ops, все из которых считаются O(1) : Таким образом, когда вы суммируете среднее время на op, вы получаете: (n*O(1) + O(n)) / n) = O(1)

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

РЕДАКТИРОВАТЬ: Проблема с остальными с хеш-таблицами: cache
Еще одна проблема, когда вы видите потерю производительности в больших хэш-таблицах, связана с производительностью кеша. Таблицы Hash страдают от плохой производительности кэша, и, следовательно, для большой коллекции - время доступа может занять больше времени, так как вам нужно перезагрузить соответствующую часть таблицы из памяти обратно в кеш.

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

в wiki поиск и удаление-Это O (n) (я думал, что точка хэш-таблиц должна иметь постоянный поиск, так что в чем смысл, если поиск O (n)).

в некоторых заметках курса от некоторое время назад я вижу широкий спектр сложностей в зависимости от некоторых деталей, включая один со всеми O(1). Зачем использовать любую другую реализацию, если я могу получить все O (1)?

Если я используя стандартные хэш-таблицы на языке C++ или Java, что я могу ожидать от сложности времени?

хэш-таблицы are O(1) средний и амортизированной сложность случая, однако она страдает от O(n) в худшем случае сложность времени. [И я думаю, что это то, где ваше замешательство]

хэш-таблицы страдают от O(n) худшая сложность времени по двум причинам:

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

однако, говорят, что это O(1) средний и амортизированный случай, потому что:

очень редко, что многие элементы будут хэшироваться на один и тот же ключ [если вы выбрали хорошую хэш-функцию, и у вас нет слишком большого баланса нагрузки.
операция rehash, которая является O(n) , может произойти после n/2 ops, которые все предполагается O(1) : таким образом, когда вы суммируете среднее время за ОП, вы получаете: (n*O(1) + O(n)) / n) = O(1)

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

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

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

например, представьте строки и "Зеленые яйца и ветчина" оба привели к хэш-значению 123 .

когда первая строка вставлена, она помещается в ведро 123. Когда вторая строка вставлена, она увидит, что значение уже существует для bucket 123 . Затем он сравнил бы новое значение с существующим значением и увидел, что они не равны. В этом случае для этого ключа создается массив или связанный список. На этом этапе получение этого значения становится O(n) поскольку hashtable должен перебирать каждое значение в этом ведре, чтобы найти желаемое.

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

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