Как std :: unordered_map возвращает правильное значение из корзины
у меня есть std::unordered_map<std::string, int> map;
Затем вставляем в него тонны элементов, но строковые ключи уникальны.
Возможен ли следующий сценарий и как с ним справляются?
map[x] = 5;
map[y] = 3;
Давайте предположим, x а также y это разные строки, но они дают одинаковый хеш, поэтому 5 и 3 помещаются в одно и то же ведро.
Когда мы пытаемся получить значение с map[x] как карта возвращает правильное значение 5? хеширования x даст корзину с двумя элементами 5, 3, но я не вижу, как она получает правильное значение, не имея самого ключа для сравнения.
Что мне не хватает?
Решение
Полная декларация unordered_map выглядит так:
template <
class Key,
class T,
class Hash = std::hash<Key>,
class KeyEqual = std::equal_to<Key>,
class Allocator = std::allocator<std::pair<Key const, T>>
> class unordered_map;
Заметьте, что для типа ключа требуется как хеш-функция, так и средство сравнения на равенство.
При поиске элемента с определенным ключом контейнер сначала найдет правильную корзину, используя хэш-функцию, а затем обойдёт элементы в этой корзине, сравнив ключ каждого элемента с помощью средства сравнения равенства.
Другие решения
Ведро — это просто ведро. unordered_map на самом деле является шаблоном, в котором, помимо прочего, используется тип ключа и значения, а также функция, которая проверяет ключи на равенство (по умолчанию std::equal_to<KeyType>) Он использует сравнение на равенство, чтобы найти элемент в корзине, который соответствует значению, которое вы ищете.
Хеш-таблицы в общем случае вырождаются в линейное или логарифмическое время, если вы полностью злой и кормите их ключами со значительным количеством коллизий, на практике они обычно близки к O (1).