hashtable — сложность unordered_map
Мне нужно создать функцию поиска, где пара (X, Y) соответствует определенному значению Z. Одним из основных требований для этого является то, что мне нужно сделать это как можно ближе к сложности O (1). Мой план — использовать unordered_map.
Я обычно не использую хеш-таблицу для поиска, так как время поиска никогда не было для меня важным. Правильно ли я считаю, что до тех пор, пока я построил unordered_map без коллизий, мое время поиска будет O (1)?
В таком случае меня интересует, какая сложность становится, если там нет ключа на неупорядоченной карте. Если я использую unordered_map :: find ():, например, чтобы определить, присутствует ли ключ в моей хеш-таблице, как он даст мне ответ? Действительно ли он перебирает все ключи?
Я очень ценю помощь.
Решение
Стандарт более или менее требует использования ковшей для столкновения
разрешение, что означает, что фактическое время поиска будет
вероятно, будет линейным по отношению к числу элементов в
ведро, независимо от того, присутствует элемент или нет.
Можно сделать это O (LG N), но это обычно не делается,
потому что количество элементов в ведре должен быть маленьким,
если хеш-таблица используется правильно.
Чтобы убедиться, что количество элементов в ведре мало, вы
должен гарантировать, что функция хеширования эффективна. Какие
эффективное средство зависит от типов и значений, которые хэшируются.
(Реализация MS использует FNV, который является одним из лучших
общие хэши, но если у вас есть специальные знания о
фактические данные, которые вы увидите, вы могли бы сделать лучше.)
Еще одна вещь, которая может помочь уменьшить количество элементов в
ковш предназначен для форсирования большего количества ковшей или использования меньшего коэффициента загрузки.
Для первого вы можете передать минимальное начальное количество
ведра в качестве аргумента для конструктора. Если вы знаете
Общее количество элементов, которые будут на карте, вы можете
контролировать коэффициент загрузки таким образом. Вы также можете получить минимум
количество сегментов после заполнения таблицы путем вызова
rehash, В противном случае есть функция
std::unordered_map<>::max_load_factor который вы можете использовать. Это
не гарантировано ничего делать, но в любом разумном
реализация, это будет. Обратите внимание, что если вы используете его на уже
заполненный unordered_mapВам, вероятно, придется позвонить
unordered_map<>::rehash после этого.
(Есть несколько вещей, которые я не понимаю в стандарте
unordered_map: почему коэффициент загрузки float, вместо
double; почему не требуется иметь эффект; и почему это
не звонит автоматически rehash для тебя.)
Другие решения
Отсутствие коллизий в хешированной структуре данных невероятно сложно (если не невозможно для данной хеш-функции и любого типа данных). Это также потребовало бы размера таблицы, точно равного количеству ключей. Нет, это не должно быть так строго. Пока хеш-функция распределяет значения относительно равномерно, вы будете иметь O(1) сложность поиска.
Хеш-таблицы, как правило, представляют собой просто массивы со связанными списками, учитывающими коллизии (это метод цепочки — существуют другие методы, но это, вероятно, наиболее используемый способ борьбы со коллизиями). Таким образом, чтобы найти, содержится ли значение в сегменте, он должен (потенциально) перебрать все значения в этом сегменте. Так что, если хеш-функция дает вам равномерное распределение, и есть N ведра, и в общей сложности M значения должны быть (в среднем) M/N значения на ведро. Пока это значение не слишком велико, это позволяет O(1) уважать.
Таким образом, в качестве длинного многословного ответа на ваш вопрос, если функция хеширования является разумной, вы получите O(1) поиск, с этим приходится перебирать (в среднем) O(M/N) ключи, чтобы дать вам «отрицательный» результат.
Как и в любой хэш-таблице, наихудший случай — это линейная сложность (Изменить: если вы построили карту без каких-либо коллизий, как вы указали в исходном посте, то вы никогда не увидите этот случай):
http://www.cplusplus.com/reference/unordered_map/unordered_map/find/
сложность
Средний случай: постоянный.
В худшем случае: линейный по размеру контейнера.Возвращаемое значение
Итератор элемента, если указанное значение ключа найдено, или unordered_map :: end, если указанный ключ не найден в контейнере.
Однако, поскольку unordered_map может содержать только уникальные ключи, вы увидите среднюю сложность постоянного времени (контейнер сначала проверяет хеш-индекс, а затем перебирает значения по этому индексу).
Я думаю, что документация для unordered_map :: Количество Функция более информативна:
Ищет в контейнере элементы с ключом k и возвращает
количество найденных элементов. Потому что контейнеры unordered_map не
учитывайте дубликаты ключей, это означает, что функция на самом деле
возвращает 1, если элемент с этим ключом существует в контейнере, и
ноль в противном случае.
detector