Как std :: unordered_map обрабатывает конфликты?

Question

std::unordered_map гарантирует поиск времени (1), но как он управляет столкновением?

Cppreference претензии

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

Предполагая, что все коды хэша одинаковы, как происходит столкновение внутри?

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

Какой подход выполняет функция хеш-функции std::unordered_map, чтобы гарантировать O (1) поиск?

Answer 1

Это не гарантирует O (1), это O (1) в среднем ... В худшем случае это может быть O (n), когда есть много столкновений. Пожалуйста, смотрите ссылку ниже, для получения дополнительной информации:

https://stackoverflow.com/a/2771398/5874704

Update

Поскольку вопрос был отредактирован, и теперь спрашивает конкретно о столкновениях на std::unordered_map, пожалуйста, посмотрите на следующий ответ:

https://stackoverflow.com/a/21519560/5874704

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

Answer 2

Был упущение из вашего поста, что важно понять: std::unordered_map имеет среднего случаяO(1) поиска. Для извлечения элемента может потребоваться до O(n) количество элементов на карте.

Что касается функции хеша, которую она использует - это зависит от пользователя. По умолчанию используется std::hash.

Единственное требование на хэш-функции по отношению к обработке столкновений

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

Answer 3

станд :: unordered_map гарантирует O (1) поиск по времени, но как это удается столкновение?

Он использует открытую адресацию/отдельную цепочку, см. here.

Cppreference утверждает

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

Предполагая, что все коды хэша одинаковы, как происходит столкновение внутри?

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

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

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

Какой подход делает зЬй: : функция хэш-функции unordered_map принимает, чтобы гарантировать O (1) поиск?

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