Как std :: unordered_map хранит и сравнивает свои ключи для обеспечения быстрого доступа к элементам без упорядочения?

Question

Как я знаю, std :: unordered_map используется для быстрого доступа к элементам. Это достигается путем сохранения и сравнения хэша ключа вместо самого ключа. Кроме того, неупорядоченный означает, что элементы в нем не отсортированы. Но быстрый доступ к элементам требует, чтобы элементы были отсортированы, чтобы можно было найти запрошенный элемент с помощью бинарного поиска.

• Означает ли это, что элементы в unordered_map отсортированы по хэш-ключ и единственная причина, по которой unordered_map быстрее, чем карта для доступа к элементам сравнивает хеш-значения обычно намного быстрее, чем сравнение значений ключей?
• Если это так, выбор между unordered_map и map зависит от типа ключ. Я прав?

• И последний вопрос: почему unordered_map не получает Сравнение? параметр шаблона, например, что делает карта? Как работает unordered_map сравнить ключевые хэши просто оператором равенства?

  template <class Key,
            class T,
            class Compare = less<Key>,
            class Alloc = allocator<pair<const Key,T> >
            > class map;
  
  template <class Key,
            class T,
            class Hash = hash<Key>,
            class Pred = equal_to<Key>,
            class Alloc = allocator< pair<const Key,T> >
            > class unordered_map;
  

Answer 1

Быстрый доступ к элементу требует определенной формы заказа. Unordered_map называется так, потому что порядок может не иметь смысла для человека и может не оставаться стабильным при добавлении или удалении элементов.

unordered_map не быстрее, чем map, потому что сравнение хэшей один в один быстрее, чем сравнение произвольных объектов один в один. Это быстрее, потому что это не нуждается в сравнении вообще. Вот почему ему не нужен compare параметр шаблона.

Типичная реализация unordered_map - это хеш-таблица. Хеш-таблица - это в основном обычный массив пар ключ-значение, который использует хитрый трюк, чтобы помочь вам быстро найти элемент, который вы ищете.

Идеальная хеш-функция распределена равномерно: если вы выбираете хеш из любого случайного объекта, значение hash % N для некоторого целого числа N должно быть примерно одинаковым (делая вид, что на секунду по модулю смещения *) 1014 * не существует). Если вы выбираете N в качестве размера вашего массива пар ключ-значение, вы можете использовать hash(key) % size в качестве индекса массива для быстрого поиска.

Поскольку предполагается, что значение хеш-функции должно быть равномерно распределено, разные объекты обычно будут иметь разные индексы, поэтому обычно все будет работать в вашу пользу. Тем не менее, все еще возможно, что hash(key) % N это то же самое для двух объектов. В этом случае хеш-таблица должна обрабатывать коллизии: существует несколько стратегий, но все они обычно переходят к линейному поиску по ключам, попавшим в одно и то же хеш-хранилище (и по этой причине хеш-таблица должна также содержать ключ, а не только хеш-ключ). Вот почему наихудшее время доступа к хеш-таблице составляет O (n), и это подчеркивает важность наличия хорошей хеш-функции.

В некоторых случаях это может быть причиной для предпочтения map над unordered_map, поскольку производительность доступа map (O (log n)) очень предсказуема.

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

Answer 2

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

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

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

Тип хеша, который использует unordered_map, указан как size_t, который является просто целым числом, поэтому он может просто использовать стандартные целочисленные операции для сравнения и выполнения вычислений с хешами.