Какая средняя асимптотическая сложность поиска в хеш таблице где n количество элементов в таблице
Это зависит от того, какую структуру данных использовать.
В односвязном списке - линейная сложность.
В отсортированном массиве или в двоичном дереве поиска - логарифмическая сложность.
В хэш-таблице - сложность константная. Но это в лучшем случае. А в худшем … стремится к линейной…
А можно ли создать идеальную хэш-таблицу, чтобы сложность поиска элемента даже в худшем случае оставалась константной?
В общем случае - нет. Но если список всех ключей установлен заранее и не изменяется, а хэш-коды у всех ключей различны, то можно построить идеальную хэш-таблицу без коллизий, где поиск любого элемента происходит за несколько тривиальных операций, причём, количество этих операций не зависит от размера хэш-таблицы.
Идеально! Поговорим о том, как это сделать.
Кстати, на курсе «Алгоритмы и структуры данных» на платформе OTUS у нас есть отдельный модуль, посвящённый вопросам создания хэш-таблиц.
Представьте англо-русский словарь. Английские слова являются ключами, а перевод - значениями. Время поиска любого слова в таком словаре может происходить за константное время, как если бы мы обращались к элементу массива по индексу!
Взял, такой, хэш-код слова “dog”, вычислил хэш-функцию, поколдовал ещё немножко, и, вуаля, в руках уже «собака» на
поводкеуказателе!
3 ответа 3
Вопрос №1: Правильно ли я понимаю, что алгоритмическая сложность данного метода будет O(1)? Т.к. внутри используется HashMap со сложностью поиска и добавления O(1).
Да, с оговоркой про то, что вставка/поиск в хеше на неудачных данных может деградировать до O(n),
Здесь стоит оговориться, что для хеша с адекватной хеш-функции, подходящем размере таблицы и при квазислучайных входных данных вероятность худшего случая пренебрежимо мала, но всегда существует такой набор данных, который этот случай даст. Зачастую его можно специально подобрать и даже использовать для DOS-атаки.
Кроме того при обычной реализации динамически расширяемой хеш-таблицы map.put может потребовать перестроения индекса хеша, сложность которого также O(n), но этого можно избежать заранее выделив под таблицу достаточный объём данных.
Вопрос №2: Общая сложность системы будет равна O(n) ?
Да, с аналогичной оговоркой, в худшем случае время составит O(n²).
В случае динамически расширяемой хеш таблицы в типовой реализации также необходимо увеличивать её размер и пересчитывать хеши порядка log(N) раз и время соответственно может ухудшиться до O(N*log(N)) в среднем случае, но этот эффект будет проявляться только для относительно больших N и зачастую его так или иначе можно нивелировать (выделяя заведомо больше памяти).
А теперь заменим HashMap на TreeMap:
Вопрос №3: Сложность метода будет равна O(log(n)) ?
Вопрос №4: Сложность всей системы будет равен O(n) ? Т.к. он сложится из O(n) + O(log(n)) -> O(n) т.к. она растет быстрее чем логарифм.
Нет, здесь не верно: нужно N раз сделать операцию сложностью O(log(n)), где n в среднем равно N/2 . т.е. сложность будет O(N*log(N)).
Почему я продолжаю видеть различные сложности выполнения для этих функций в хэш-таблице?
в 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 должен перебирать каждое значение в этом ведре, чтобы найти желаемое.
по этой причине при использовании хэш-таблицы важно использовать ключ с действительно хорошей хэш-функцией, которая является быстрой и не часто приводит к дублированию значений для различных объекта.
какие факторы я должен учитывать, когда мне нужно выбрать между хэш-таблицей или сбалансированным двоичным деревом для реализации набора или ассоциативного массива?
на этот вопрос, боюсь, вообще нельзя ответить.
проблема в том, что существует множество типов хэш-таблиц и сбалансированных двоичных деревьев, и их характеристики сильно различаются.
Итак, наивный ответ: это зависит от функциональности. Используйте хэш-таблицу, Если вам не нужен порядок и сбалансированное двоичное дерево в противном случае.
для более подробного ответа рассмотрим некоторые альтернативы.
Хэш-Таблицы (см. Запись Википедии для некоторых основ)
- не все хэш-таблицы используют связанный список в качестве ведра. Популярной альтернативой является использование" лучшего " ведра, например двоичного дерева или другой хэш-таблицы (с другой хэш-функцией).
- некоторые хэш-таблицы вообще не используют ведра: см. Open Addressing (они поставляются с другими проблемами, очевидно)
- есть что-то, называемое линейным повторным хэшированием (это качество детали реализации), которое позволяет избежать ловушка" останови-мир-и-повтори". В основном на этапе миграции вы вставляете только" новую " таблицу, а также перемещаете одну "старую" запись в "новую" таблицу. Конечно, этап миграции означает двойной поиск и т. д.
- повторное балансирование дорого, вы можете рассмотреть список пропусков (также лучше для многопоточного доступа) или дерево Splay.
- хороший распределитель может "упаковать" узлы вместе в памяти (лучшее поведение кэширования), даже хотя это не облегчает проблему поиска указателя.
- B-Tree и варианты также предлагают "упаковку"
Не будем забывать, что O(1) является асимптотической сложностью. Для нескольких элементов коэффициент обычно более важен (с точки зрения производительности). Что особенно верно, если ваша хэш-функция медленная.
наконец, для множеств вы также можете рассмотреть вероятностные структуры данных, такие как Блум Фильтры.
хэш-таблицы обычно лучше, если нет необходимости хранить данные в какой-либо последовательности. Двоичные деревья лучше, если данные должны быть отсортированы.
достойный момент в современной архитектуре: хэш-таблица обычно, если ее коэффициент загрузки низкий, имеет меньше чтения памяти, чем двоичное дерево. Поскольку доступ к памяти, как правило, довольно дорогостоящий по сравнению с циклами записи ЦП, хэш-таблица часто быстрее.
в следующем двоичном дереве предполагается самобалансировка, как красное черное дерево, дерево AVL или как treap.
с другой стороны, если вам нужно переделывать все в хэш-таблице когда вы решите продлить его, это может быть дорогостоящая операция, которая происходит (амортизируется). Бинарные деревья не имеют этого ограничения.
двоичные деревья легче реализовать на чисто функциональных языках.
бинарные деревья имеют естественный порядок сортировки и естественный способ ходить по дереву для всех элементов.
когда коэффициент загрузки в хэш-таблице низкий, вы можете тратить много места в памяти, но с двумя указателями двоичные деревья, как правило, занимают больше пространство.
хэш-таблицы почти O (1) (в зависимости от того, как вы обрабатываете коэффициент загрузки) против деревьев Bin O (lg n).
деревья, как правило, являются"средним исполнителем". Они не делают ничего особенно хорошего, но и не делают ничего особенно плохого.
двоичное дерево поиска требует отношения общего порядка между ключами. Для хэш-таблицы требуется только отношение эквивалентности или идентичности с согласованной хэш-функцией.
Если доступно отношение общего порядка, то отсортированный массив имеет производительность поиска, сопоставимую с двоичными деревьями, производительность вставки в худшем случае в порядке хэш-таблиц и меньшую сложность и использование памяти, чем оба.
сложность вставки в худшем случае для хэш-таблицы может быть слева в O(1)/O (log K) (с K количество элементов с тем же хэшем), если допустимо увеличить сложность поиска в худшем случае до O(K) или O (log K), если элементы могут быть отсортированы.
инварианты для деревьев и хэш-таблиц дорого восстанавливать, если ключи меняются, но меньше O(N log N) для отсортированных массивов.
Это факторы, которые необходимо учитывать при принятии решения о том, какую реализацию использовать:
- наличие общего заказа отношение.
- наличие хорошей функции хэширования для отношения эквивалентности.
- a-priory знание количества элементов.
- знания о скорости вставки, удаления и поиска.
- относительная сложность функций сравнения и хэширования.
хэш-таблицы быстрее поиска:
- вам нужен ключ, который генерирует равномерное распределение (в противном случае вы пропустите много и должны полагаться на что-то другое, кроме хэша; например, линейный поиск).
- хэши могут использовать много пустого пространства. Вы можете зарезервировать 256 записей, но вам нужно только 8 (пока).
- детерминировано. O (log n) я думаю.
- не требуется дополнительное пространство, как хэш-таблицы может
- должны быть отсортированы. Добавление элемента в середину означает перемещение остальных.
Если вам нужны только отдельные элементы, хеш-таблицы лучше. Если вам нужен диапазон элементов, у вас просто нет другого варианта, кроме двоичных деревьев.
чтобы добавить к другим большим ответам выше, я бы сказал:
используйте хэш-таблицу, если объем данных не изменится (например, хранение констант); но, если объем данных изменится, используйте дерево. Это связано с тем, что в хэш-таблице после достижения коэффициента загрузки хэш-таблица должна изменяться. Операция изменения размера может быть очень медленной.
один момент, который я не думаю, был рассмотрен, заключается в том, что деревья намного лучше для постоянные структуры данных. То есть неизменные структуры. Стандартная хэш-таблица (т. е. та, которая использует один массив связанных списков) не может быть изменена без изменения всей таблицы. Одна из ситуаций, в которой это актуально, - если две параллельные функции имеют копию хэш-таблицы, и одна из них изменяет таблицу (если таблица изменчива, это изменение будет видно другой тоже). Другая ситуация была бы примерно такой:--4-->
с изменяемой таблицей мы не можем гарантировать, что таблица, которую получает вызов функции, останется этой таблицей на протяжении всего ее выполнения, потому что другие вызовы функций могут ее изменить.
таким образом, изменчивость иногда не является приятной вещью. Теперь, способ обойти это было бы сохранить таблицу неизменяемой, и обновления возвращают новая таблица без изменения старого. Но с хэш-таблицей это часто будет дорогостоящим O (n) операция, так как весь базовый массив должен быть скопирован. С другой стороны, при сбалансированном дереве новое дерево может быть создано только с помощью O ( log n) узлы, которые необходимо создать (остальная часть дерева идентична).
это означает, что эффективное дерево может быть очень удобным, когда требуются неизменяемые карты.
Если у вас будет много слегка разных экземпляров наборов, вы, вероятно, захотите, чтобы они разделяли структуру. Это легко с деревьями (если они неизменяемы или копируются при записи). Я не уверен, насколько хорошо вы можете сделать это с помощью хэш-таблиц; это, по крайней мере, менее очевидно.
по моему опыту, hastables всегда быстрее, потому что деревья страдают слишком много эффектов кэша.
здесь вы можете увидеть сравнение производительности наиболее распространенных библиотек hashtable, tree и trie.
одно замечание о прохождение, минимального и максимального элемента. Хэш-таблицы не поддерживают какой-либо упорядоченный обход или доступ к минимальным или максимальным элементам. Если эти возможности важны, бинарное дерево является лучшим выбором.
Я много раз заглядывал на просторы интернета, нашел много интересных статей о хеш-таблицах, но вразумительного и полного описания того, как они реализованы, так и не нашел. В связи с этим мне просто нетерпелось написать пост на данную, столь интересную, тему.
Возможно, она не столь полезна для опытных программистов, но будет интересна для студентов технических ВУЗов и начинающих программистов-самоучек.
Проблема коллизии
Естественно, возникает вопрос, почему невозможно такое, что мы попадем дважды в одну ячейку массива, ведь представить функцию, которая ставит в сравнение каждому элементу совершенно различные натуральные числа просто невозможно. Именно так возникает проблема коллизии, или проблемы, когда хеш-функция выдает одинаковое натуральное число для разных элементов.
Существует несколько решений данной проблемы: метод цепочек и метод двойного хеширования. В данной статье я постараюсь рассказать о втором методе, как о более красивом и, возможно, более сложном.
Понятие хеш-таблицы
Хеш-таблица — это контейнер, который используют, если хотят быстро выполнять операции вставки/удаления/нахождения. В языке C++ хеш-таблицы скрываются под флагом unoredered_set и unordered_map. В Python вы можете использовать стандартную коллекцию set — это тоже хеш-таблица.
Реализация у нее, возможно, и не очевидная, но довольно простая, а главное — как же круто использовать хеш-таблицы, а для этого лучше научиться, как они устроены.
Для начала объяснение в нескольких словах. Мы определяем функцию хеширования, которая по каждому входящему элементу будет определять натуральное число. А уже дальше по этому натуральному числу мы будем класть элемент в (допустим) массив. Тогда имея такую функцию мы можем за O(1) обработать элемент.
Теперь стало понятно, почему же это именно хеш-таблица.
Мотивация использовать хеш-таблицы
Для наглядности рассмотрим стандартные контейнеры и асимптотику их наиболее часто используемых методов.
Контейнер \ операция | 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) |
Все данные при условии хорошо выполненных контейнерах, хорошо подобранных хеш-функциях
Из этой таблицы очень хорошо понятно, почему же стоит использовать хеш-таблицы. Но тогда возникает противоположный вопрос: почему же тогда ими не пользуются постоянно?
Ответ очень прост: как и всегда, невозможно получить все сразу, а именно: и скорость, и память. Хеш-таблицы тяжеловесные, и, хоть они и быстро отвечают на вопросы основных операций, пользоваться ими все время очень затратно.
Как такое возможно?
Предположим, в словаре 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) - линейный.
Как такое возможно?
Предположим, в словаре 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) - линейный.
Решения проблемы коллизии методом двойного хеширования
Мы будем (как несложно догадаться из названия) использовать две хеш-функции, возвращающие взаимопростые натуральные числа.
Одна хеш-функция (при входе 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 с нашим вставляемым значением.
Заключение
Если вы уже закончили работу над крупным проектом, все настройки которого хранятся в хэш-таблице, то вы можете выписать список всех-всех-всех параметров (ключей) и создать идеальную хэш-таблицу для их хранения, чтобы увеличить скорость доступа к этим элементам.
А теперь небольшой бонус. 15 января я проведу Demo Day курса "Алгоритмы и структуры данных" на платформе OTUS, приглашаю всех желающих узнать подробно о курсе и задать вопросы лично.
Также хочу посоветовать еще несколько статей из своего блога, которые уже успели получить хороший отклик у читателей:
Исходные данные: файл, с одной единственной колонкой, в которой находятся числа от 0 до Integer.MAX_INT.
Нужно написать алгоритм, который будет подсчитывать количество повторений цифр в этом файле.
Будем считать, что у нас бесконечное количество памяти. Напишем такой метод, а по завершению просто распечатаем entries у этой коллекции:
Вопрос №1: Правильно ли я понимаю, что алгоритмическая сложность данного метода будет O(1)? Т.к. внутри используется HashMap со сложностью поиска и добавления O(1).
Вопрос №2: Общая сложность системы будет равна O(n) ?
А теперь заменим HashMap на TreeMap :
Вопрос №3: Сложность метода будет равна O(log(n)) ?
Вопрос №4: Сложность всей системы будет равен O(n) ? Т.к. он сложится из O(n) + O(log(n)) -> O(n) т.к. она растет быстрее чем логарифм.
Читайте также: