Кроме случаев, когда они не ...
Предыстория. Хеш-таблицы - это здорово, не правда ли? При правильной реализации они кажутся окончательной структурой данных выбора. Что может не понравиться с впечатляющим средним поиском, вставкой и удалением Θ (1)?
Что ж, не так уж много, если все идеально и вариант использования правильный. В худшем случае хеш-таблицы работают так же или медленнее, чем все другие структуры данных:
Компромисс. Хеш-таблицы содержат проблемы. Что-то резко замедляет наш туз пик, и теперь наша задача - понять, что именно. Короткий ответ - коллизии, более длинный ответ - вы вообще используете хеш-функцию?
Хеш-функция: Ах, хеш-функция. Короче говоря, именно эта магическая функция дает нам постоянный средний случай. При наличии некоторого ключа ввода эта функция пытается вернуть некий уникальный индекс. Реализация этой функции решает, насколько хорошей или плохой будет временная сложность нашей реализации хеш-таблицы.
Итак, что же делает хеш-функцию хорошей?
Нам нужно минимизировать коллизии и заполнить наш базовый массив как можно более равномерно.
Краткое изложение причин:
В хеш-таблицах используются сегменты. Сегменты - это индексы в массиве. Наша хеш-функция берет ключ из данных, которые мы вставляем или ищем, и генерирует этот индекс. Это позволяет нам сделать поиск постоянным, поскольку нам больше не нужно перемещаться по нашему массиву, вместо этого мы переходим к его точному индексу.
Коллизия - это когда наша хеш-функция возвращает один и тот же индекс для нескольких ключей. Это проблема, которая иногда неизбежна для очень больших наборов данных. К счастью, эту проблему можно решить несколькими способами, используя разрешение столкновений. Разрешение коллизий относится к различным методам, используемым для обработки коллизий.
Одно из популярных решений - отдельная цепочка. Идея состоит в том, чтобы сделать так, чтобы каждая корзина хеш-таблицы указывала на связанный список данных, которые имеют одинаковое значение хеш-функции. Простой. Задача решена.
НОВАЯ ПРОБЛЕМА:
Все, что мы вставили, хешируется до одного и того же значения хеш-функции. Наша хеш-функция не очень хороша:
Кто-то забыл закончить наш оператор возврата, и теперь у нас остается то, что по сути является связанным списком:
Частично отсюда и происходит наш худший линейный случай! Как и в связанном списке, поиск и удаление по значению теперь стали O (n) *.
* Обратите внимание, что в приведенной выше таблице сложности предполагается, что удаляемый узел известен и указатель на узел доступен для связанных списков, следовательно, временная сложность O (1) *
Вставка O (n) происходит по совершенно другому сценарию. Этот случай возникает, когда хеш-таблица достигает своего коэффициента загрузки. Коэффициент загрузки - это предел того, насколько заполнена наша хеш-таблица перед изменением размера. Изменение размера необходимо, чтобы избежать коллизий по мере роста нашей таблицы, но требует от нас создания новой таблицы большего размера с большим количеством сегментов и повторного хеширования нашей таблицы. Существуют передовые практики, позволяющие избежать частых повторений и при этом избежать столкновений. Вы можете узнать больше по теме по ссылке выше.
Пока что может показаться, что большинство недостатков нашей любимой хеш-таблицы могут быть возложены на нас. Причина номер 1 не использовать хеш-таблицы:
1. Вы терпите неудачу в хэш-таблицах, не зная их в худшем случае.
Мрачный. Я знаю. К счастью, этого можно избежать, если больше узнать об этом предмете.
Вторую часть этого раздела мы не контролируем. Давайте обсудим некоторые унаследованные недостатки хеш-таблицы.
Когда и почему. Даже в идеальном состоянии хеш-таблицы не всегда являются решением. Мне потребовалось много времени, чтобы понять это. Вы тоже можете поверить, что идеальную хеш-таблицу можно использовать для ускорения всего. Мы обсудим, почему это не так, но сначала давайте разберемся, когда их следует использовать:
Используйте хеш-таблицы, когда магия хеш-таблиц работает на вас. Хеш-таблицы очень полезны для хранения взаимосвязей между данными. Если вы пытаетесь сохранить значения в ключах, следует внимательно изучить хеш-таблицы. Классический пример этого - словари и картография. Временная сложность Θ (1) делает их идеальными для работы с большим количеством значений. Хеш-таблицы часто могут быть наиболее эффективным методом решения многих вопросов на собеседовании. Перейдите по этой ссылке, чтобы узнать о некоторых проблемах, которые можно решить с помощью хеш-таблиц!
Когда их не следует использовать:
- Перебор ключей по порядку.
- Сортировка или упорядочивание предметов.
- Поиск пересечений и различий.
- Нахождение наибольших / наименьших значений.
- Реализация «первым пришел - первым ушел» и «первым пришел - последний ушел». Вместо этого используйте очереди и стопки.
Причина номер 2 не использовать хеш-таблицы:
2. Хеш-таблицы не помогут, если вы не знаете их ограничений.
Как и в случае с любой другой структурой данных, важно знать об ограничениях и передовых методах реализации. Эти знания помогут вам различить, когда использовать хеш-таблицу или искать в другом месте!
Следите за моими приключениями в коде здесь: https://github.com/Codeofsanju
