Какая средняя асимптотическая сложность поиска в хеш таблице где n количество элементов в таблице

Обновлено: 08.07.2024

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

Быстро считается — за линейное от размера объекта время;
Имеет не очень большие значения — влезающие в 64 бита;
«Детерминировано-случайная» — если хеш может принимать $n$ различных значений, то вероятность того, что хеши от двух случайных объектов совпадут, равна примерно $\frac$.

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

Для некоторых задач удобнее работать с хешами, чем с самими объектами. Пусть даны $n$ строк длины $m$, и нас просят $q$ раз проверять произвольные две на равенство. Вместо наивной проверки за $O(q \cdot n \cdot m)$, мы можем посчитать хеши всех строк, сохранить, и во время ответа на запрос сравнивать два числа, а не две строки.

Применения в реальной жизни

Чек-суммы. Простой и быстрый способ проверить целостность большого передаваемого файла — посчитать хеш-функцию на стороне отправителя и на стороне получателя и сравнить.
Хеш-таблица. Класс unordered_set из STL можно реализовать так: заведём $n$ изначально пустых односвязных списков. Возьмем какую-нибудь хеш-функцию $f$ с областью значений $[0, n)$. При обработке .insert(x) мы будем добавлять элемент $x$ в $f(x)$-тый список. При ответе на .find(x) мы будем проверять, лежит ли $x$-тый элемент в $f(x)$-том списке. Благодаря «равномерности» хеш-функции, после $k$ добавлений ожидаемое количество сравнений будет равно $\frac$ = $O(1)$ при правильном выборе $n$.
Мемоизация. В динамическом программировании нам иногда надо работать с состояниями, которые непонятно как кодировать, чтобы «разгладить» в массив. Пример: шахматные позиции. В таком случае нужно писать динамику рекурсивно и хранить подсчитанные значения в хеш-таблице, а для идентификации состояния использовать его хеш.
Проверка на изоморфизм. Если нам нужно проверить, что какие-нибудь сложные структуры (например, деревья) совпадают, то мы можем придумать для них хеш-функцию и сравнивать их хеши аналогично примеру со строками.
Криптография. Правильнее и безопаснее хранить хеши паролей в базе данных вместо самих паролей — хеш-функцию нельзя однозначно восстановить.
Поиск в многомерных пространствах. Детерминированный поиск ближайшей точки среди $m$ точек в $n$-мерном пространстве быстро не решается. Однако можно придумать хеш-функцию, присваивающую лежащим рядом элементам одинаковые хеши, и делать поиск только среди элементов с тем же хешом, что у запроса.

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

Это зависит от того, какую структуру данных использовать.

В односвязном списке - линейная сложность.

В отсортированном массиве или в двоичном дереве поиска - логарифмическая сложность.

В хэш-таблице - сложность константная. Но это в лучшем случае. А в худшем … стремится к линейной…

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

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

Идеально! Поговорим о том, как это сделать.
Кстати, на курсе «Алгоритмы и структуры данных» на платформе OTUS у нас есть отдельный модуль, посвящённый вопросам создания хэш-таблиц.

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

Взял, такой, хэш-код слова “dog”, вычислил хэш-функцию, поколдовал ещё немножко, и, вуаля, в руках уже «собака» на ~~поводке~~ указателе!

Как такое возможно?

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

Если же ограничиваться простейшей хэш-функцией вида «(A * k + B) % P % N» , с возможностью подбора лишь двух коэффициентов A и В , то создать “волшебную” биекцию вряд ли удастся - коллизий не избежать. В этой формуле:
k - хэшкод уникального ключа,
P - заранее заданное простое число, большее любого возможного ключа k ,
N - размер хеш-таблицы, то есть количество всех ключей.

Идея идеального хэширования заключается в двухэтапном хэшировании.

На первом этапе находим «квартиру», а на втором этапе - «комнату», где располагается искомое значение.

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

Первый этап

Минимизация количества «комнат» в «квартирах».

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

Например, за 100 итераций подбора коэффициентов для словаря из 10.000 ключей максимальное количество коллизий для одного элемента не превышает 10.

Итак, на первом этапе мы подбираем глобальные коэффициенты А и В для хэш-функции вида «(A * k + B) % P % N» . Эта функция вычисляет номер «квартиры», в которой находится значение для заданного ключа. При этом минимизируется максимальное количество «комнат» (коллизий) в каждой «квартире».

Второй этап

Для размещения K элементов в одной «квартире» мы резервируем K² «комнат». Такая «квадрокомнатная квартира» позволит без особого труда подобрать коэффициенты A и B для размещения K элементов без единой коллизии, потому что значения всех ключей известно заранее (напомним, что хэш-коды всех ключей различны). Коэффициенты подбираются для каждой «квартиры» отдельно и хранятся в каждом элементе первой хэш-таблицы, вместе с количеством «комнат».

Для поиска любого элемента в идеальной хэш-таблице необходимо выполнить следующие действия:

Найти номер «квартиры» i по хэш-коду ключа k: «(A * k + B) % P % N» .

Взять коэффициенты для вычисления номера комнаты: Ai , Bi , K² .

Найти номер «комнаты» по формуле: «(Ai * k + Bi) % P % K²»

Вернуть значение из найденной «комнаты».

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

Расход памяти

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

Возьмём, для примера, хэш-таблицу из N = 10 элементов. В каждом элементе может быть от 0 до 10 коллизий. Вычислим вероятность коллизий, умножим на затраты по памяти и найдём математическое ожидание объёма памяти для размещения одного элемента.

Итого: для хранения “квартир” нужно N ячеек памяти, для хранения “комнат” - примерно 1.9 * N . Суммарный расход памяти: 2.9 * N = О(N) - линейный.

Заключение

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

А теперь небольшой бонус. 15 января я проведу Demo Day курса "Алгоритмы и структуры данных" на платформе OTUS, приглашаю всех желающих узнать подробно о курсе и задать вопросы лично.

Также хочу посоветовать еще несколько статей из своего блога, которые уже успели получить хороший отклик у читателей:

Существует два основных вида хеш-таблиц: с цепочками и открытой адресацией. Хеш-таблица содержит некоторый массив [math]H[/math] , элементы которого есть пары (хеш-таблица с открытой адресацией) или списки пар (хеш-таблица с цепочками).

Выполнение операции в хеш-таблице начинается с вычисления хеш-функции от ключа. Хеш-код [math]i = h(key)[/math] играет роль индекса в массиве [math]H[/math] , а зная индекс, мы можем выполнить требующуюся операцию (добавление, удаление или поиск).

Количество коллизий зависит от хеш-функции; чем лучше используемая хеш-функция, тем меньше вероятность их возникновения.

Вероятность коллизий при вставке в хеш-таблицу превышает 50%

Пусть хеш-таблица имеет размер [math]len[/math] и в нее добавляют [math]n[/math] элементов. Рассмотрим [math]

'(n)[/math] — вероятность того, что не возникнет ни одной коллизии. Добавим два любых элемента в нашу хеш-таблицу. Вероятность того, что они не попадут в одну и ту же ячейку таблицы равна [math]1 - \dfrac[/math] . Возьмем еще один элемент. Тогда вероятность того, что третий элемент не попадет в одну из уже занятых ячеек равна [math]1 - \dfrac[/math] . Рассуждая аналогичным образом, получим формулу: [math]

'(n) = \left( 1 - \dfrac\right )\cdot \left( 1 - \dfrac\right )\dots\left( 1 - \dfrac\right ) = \dfrac> = \dfrac \cdot \left (len - n \right)!>[/math]

Тогда [math]

(n)[/math] — вероятность возникновения коллизии равна: [math]p(n) = 1 -

'(n)[/math] ,

Способ разрешения коллизий — важная составляющая любой хеш-таблицы.

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

Если мы поделим число хранимых элементов на размер массива [math]H[/math] (число возможных значений хеш-функции), то узнаем коэффициент заполнения хеш-таблицы (англ. load factor). От этого параметра зависит среднее время выполнения операций.

Хеширование (англ. hashing) — класс методов поиска, идея которого состоит в вычислении хеш-кода, однозначно определяемого элементом с помощью хеш-функции, и использовании его, как основы для поиска (индексирование в памяти по хеш-коду выполняется за [math]O(1)[/math] ). В общем случае, однозначного соответствия между исходными данными и хеш-кодом нет в силу того, что количество значений хеш-функций меньше, чем вариантов исходных данных, поэтому существуют элементы, имеющие одинаковые хеш-коды — так называемые коллизии, но если два элемента имеют разный хеш-код, то они гарантированно различаются. Вероятность возникновения коллизий играет немаловажную роль в оценке качества хеш-функций. Для того чтобы коллизии не замедляли работу с таблицей существуют методы для борьбы с ними.

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

Динамическое — добавляем, удаляем и смотрим на наличие нужных элементов.

На поиск элемента в хеш-таблице в худшем случае, может потребоваться столько же времени, как и в списке, а именно [math]\Theta(n)[/math] , но на практике хеширование более эффективно. При некоторых разумных допущениях математическое ожидание времени поиска элемента в хеш-таблице составляет [math]O(1)[/math] . А все операции (поиск, вставка и удаление элементов) в среднем выполняются за время [math]O(1)[/math] . При этом не гарантируется, что время выполнения отдельной операции мало́, так как при достижении некоторого значения коэффициента заполнения необходимо перехешировать таблицу: увеличить размер массива [math]H[/math] и заново добавить в новую хеш-таблицу все пары.

Почти во всех современных языках присутствуют классы, реализующие хеширование. Рассмотрим некоторые из них.

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

Хеширование – преобразование ключей к числам.

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

Хеш-функция ― преобразование по детерминированному алгоритму входного массива данных произвольной длины (один ключ) в выходную битовую строку фиксированной длины (значение). Результат вычисления хеш-фукнции называют «хешем».

Хеш-функция должна иметь следующие свойства:

Всегда возвращать один и тот же адрес для одного и того же ключа;
Не обязательно возвращает разные адреса для разных ключей;
Использует все адресное пространство с одинаковой вероятностью;
Быстро вычислять адрес.

Коллизией хеш-функции H называется два различных входных блока данных X и Y таких, что H(x) = H(y) .

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

Число хранимых элементов, делённое на размер массива (число возможных значений хеш-функции), называется коэффициентом заполнения хеш-таблицы (load factor). Обозначим его α = N/M .

Этот коэффициент является важным параметром, от которого зависит среднее время выполнения операций.

Парадокс дней рождений. При вставке в хеш-таблицу размером 365 ячеек всего лишь 23-х элементов вероятность коллизии уже превысит 50 % (если каждый элемент может равновероятно попасть в любую ячейку).

Хеш-таблицы различаются по методу разрешения коллизий. Основные методы разрешения коллизий:

Метод цепочек.
Метод открытой адресации.

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

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

Время работы: В лучшем случае – O(1) . В худшем случае – если не требуется проверять наличие дубля, то O(1) – иначе – O(N)

Вычисляем значение хеш-функции удаляемого ключа – h .
Находим A[h] – указатель на список ключей.
Ищем в списке удаляемый ключ и удаляем его.

Время работы: В лучшем случае – O(1) . В худшем случае – O(N) .

Вычисляем значение хеш-функции ключа – h .
Находим A[h] – указатель на список ключей.
Ищем его в списке.

Время работы: В лучшем случае – O(1) . В худшем случае – O(N) .

Среднее время работы операций поиска, вставки (с проверкой на дубликаты) и удаления в хеш-таблице, реализованной методом цепочек – O(1 + α) , где α – коэффициент заполнения таблицы.

Среднее время работы.

Среднее время работы операций поиска, вставки (с проверкой на дубликаты) и удаления в хеш-таблице, реализованной методом цепочек – O(1 + α), где α – коэффициент заполнения таблицы.

Доказательство. Среднее время работы – математическое ожидание времени работы в зависимости от исходного ключа. Время работы для обработки одного ключа T(k) зависит от длины цепочки и равно 1 + Nh(k) , где Ni – длина i-ой цепочки. Предполагаем, что хеш-функция равномерна, а ключи равновероятны.

Среднее время работы

Метод открытой адресации

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

При поиске элемента систематически проверяем ячейки до тех пор, пока не найдем искомый элемент или не убедимся в его отсутствии.

Вычисляем значение хеш-функции ключа – h .
Систематически проверяем ячейки, начиная от A[h] , до тех пор, пока не находим пустую ячейку.
Помещаем вставляемый ключ в найденную ячейку. В п.2 поиск пустой ячейки выполняется в некоторой последовательности. Такая последовательность называется «последовательностью проб».

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

Важно, чтобы для каждого ключа k последовательность проб h(k, 0), h(k, 1), . , h(k, M − 1) представляла собой перестановку множества 0,1, . , M − 1 , чтобы могли быть просмотрены все ячейки таблицы.

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

Удаление ключа. Алгоритм удаления достаточен сложен. Нельзя при удалении ключа из ячейки i просто пометить ее значением NIL . Иначе в последовательности проб для некоторого ключа (или некоторых) возникнет пустая ячейка, что приведет к неправильной работе алгоритма поиска. Решение. Помечать удаляемые ячейки спец. значением «Deleted» . Нужно изменить методы поиска и вставки. В методе вставки проверять «Deleted» , вставлять на его место. В методе поиска продолжать поиск при обнаружении «Deleted» .

Вычисление последовательности проб. Желательно, чтобы для различных ключей k последовательность проб h(k, 0), h(k, 1), . , h(k, M − 1) давала большое количество последовательностей- перестановок множества 0,1. , M − 1 .

Обычно используются три метода построения h(k, i) :

Линейное пробирование.
Квадратичное пробирование.
Двойное хеширование.

h(k, i) = (h′(k) + i) mod M

Основная проблема – кластеризация. Последовательность подряд идущих занятых элементов таблицы быстро увеличивается, образуя кластер. Попадание в элемент кластера при добавлении гарантирует «одинаковую прогулку» для различных ключей и проб. Новый элемент будет добавлен в конец кластера, увеличивая его.

h(k, i) = (h1(k) + ih2(k)) mod M.

Требуется, чтобы последовательность проб содержала все индексы 0, .. , M–1 . Для этого все значения h2(k) должны быть взаимно простыми с M .

M может быть степенью двойки, а h2(k) всегда возвращать нечетные числа.
M простое, а h2(k) меньше M .

Общее количество последовательностей проб O(M^2) .

Лучший случай	В среднемю Метод цепочек.	В среднем. Метод открытой адресации.	Худший случай.
Поиск	O(1)	O(1 + a)	O(1 / 1 - a)	O(n)
Вставка	O(1)	O(1 + a)	O(1 / 1 - a)	O(n)
Удаление	O(1)	O(1 + a)	O(1 / 1 - a)	O(n)

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

Для запуска необходиа java версии 1.8 и Apache Maven версии 3.5.0. Для компиляции необходимо в корне проекта выполнить команду

А для запуска программы

Оба параметра являются обязательными.

Во время выполнения в консоль будут выведены выполненные команды.

Формат входных данных

Примеры: add 10 20 search 15 print min

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

<> - отдельная ячейка массива, в которой храниться список ключей. А для хеш-таблиц с открытой адресацией вывод будет выглядеть так:

Hash table: [ 755 D __ 855 __ 942 __ 346 __ 588 __ 576 ]

__ - пустая ячейка, D - удаленная ячейка.

Формат выходных данных

В выходной файл выводятся результаты исполнения программы.

Команда print должна отражать внутреннее строение структуры данных

Команда search выводит error, в случае, когда значение не было найдено, или значение найденное по ключу в противном случае.

Команда add добавляет значение в таблицу (Ничего не выводит).

Команда delete удаляетя число, или ничего не делает, если значение не было найдено (Ничего не выводит).

Команда min выводит минимальное число в таблице, или empty, если таблица пустая.

Команда max выводит максимальное число в таблице,или empty, если таблица пустая.

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

1.Юнит тесты, проверящие корректность работы методов каждой хеш-таблицы

Тесты находятся в ./src/test/java/tests/

2.Юнит тесты для провеки времени выполнения большого числа операций добавления, поиска и удаления.

Тесты находятся в ./src/test/java/tests/

3.Файлы с входными данными и правильными ответами.

На вход программе подается два файла.

Заитем выходной файл с результатами исполнения программы сравнивается с файлом в котором находятся правильные ответы

Тесты находятся в ./tests/

Подробное описание тестов

1.Простая проверка всех операций кроме print

2.Проверка корректной работы add, delete(удаление элементов по несушествуюшему ключу) и print

3.Проверка корректной работы add, delete(удаление элементов по сушествуюшему ключу) и print

4.Проверка корректной работы search(поиск элементов по несушествуюшему ключу)

5.Проверка корректной работы search(поиск элементов по сушествуюшему ключу)

Сравнение времени работы

Время работы рачитываем тестом с 1000000 операций каждого типа.

Search time: 354

Delete time: 255

Search time: 281

Delete time: 365

Search time: 273

Delete time: 377

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

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

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

План выполнения домашнего задания

You can’t perform that action at this time.

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.

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