С++ - неупорядоченная сложность

Мне нужно создать функцию поиска, где пара (X, Y) соответствует определенному значению Z. Одним из основных требований для этого является то, что мне нужно сделать это как можно ближе к O (1) сложности. Мой план состоит в том, чтобы использовать unordered_map.

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

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

Я очень благодарен за помощь.

Ответ 1

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

Чтобы количество элементов в ковше было небольшим, вы должен убедиться, что функция хеширования эффективна. Какие эффективное средство зависит от того, какие типы и значения хэшируются. (В реализации MS используется FNV, который является одним из лучших общие хэш вокруг, но если у вас есть специальные знания о фактические данные, которые вы увидите, вы, возможно, сможете сделать лучше.) Еще одна вещь, которая может помочь уменьшить количество элементов за ковш должен вытеснять больше ведер или использовать меньший коэффициент нагрузки. Во-первых, вы можете передать минимальное начальное число ведра в качестве аргумента конструктору. Если вы знаете общее количество элементов, которые будут на карте, вы можете таким образом, контролируйте коэффициент нагрузки. Вы также можете форсировать минимальную сумму количество ведер, как только таблица будет заполнена, путем вызова rehash. В противном случае существует функция std::unordered_map<>::max_load_factor, который вы можете использовать. Это не гарантирует ничего, но в любом разумном реализация, будет. Обратите внимание, что если вы используете его уже заполненный unordered_map, вам, вероятно, придется позвонить unordered_map<>::rehash после.

(Есть несколько вещей, которые я не понимаю о стандарте unordered_map: почему коэффициент нагрузки равен float, а не double; почему это не требует эффекта; и почему это автоматически не вызывает rehash для вас.)

Ответ 2

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

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

Итак, как немного длинный ответ на ваш вопрос, пока функция хэширования является разумной, вы получите O(1) lookup, при этом ей придется перебирать (в среднем) O(M/N) ключи, чтобы дать вы "отрицательный" результат.

Ответ 3

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

http://www.cplusplus.com/reference/unordered_map/unordered_map/find/

СложностьСредний случай: постоянный. Наихудший случай: линейный размер контейнера.

Возвращаемое значениеИтератор к элементу, если найденное указанное значение ключа, или unordered_map:: end, если указанный ключ не найден в контейнере.

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

Я думаю, что документация для unordered_map:: count более информативна:

Ищет контейнер для элементов с ключом k и возвращает количество найденных элементов. Поскольку контейнеры unordered_map не позволяют дублировать ключи, это означает, что функция фактически возвращает 1, если в контейнере существует элемент с этим ключом и ноль в противном случае.