Как работает unordered map

Классы unordered_map и unordered_multimap: ассоциативные массивы

Класс unordered_map реализует ассоциативный массив, в котором каждому ключу соответствует одно значение. Чтобы получить доступ к элементу, необходимо указать ключ, который использовался при сохранении элемента. В отличии от класса map для быстрого поиска элементов используется хеш-таблица, значения которой состоят из целых чисел (тип size_t ). Класс unordered_multimap реализует ассоциативный массив, в котором одному ключу могут соответствовать несколько значений. Работа с классами производится аналогичным образом, поэтому в этом разделе мы рассмотрим только возможности класса unordered_map .

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

Класс hash: хеш

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

При объявлении переменной после названия класса внутри угловых скобок указывается элементарный тип данных или тип указателя. Чтобы получить хеш следует передать значение внутри круглых скобок. Для одного и того же значения хеш всегда будет одинаковым:

В других заголовочных файлах существуют реализации для классов string , wstring , u16string , u32string , vector<bool> , bitset , unique_ptr , shared_ptr и др. Пример получения хеша для строки:

Создание объекта

Объявление класса unordered_map :

Основные псевдонимы для типов:

Создать экземпляр класса unordered_map можно следующими способами (полный список конструкторов смотрите в документации):

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

Внутри угловых скобок после типов данных ключа и значения можно дополнительно указать функцию для получения хеша и функцию сравнения для ключа:

указать объект класса unordered_map внутри круглых скобок или после оператора = (доступны конструкторы копирования и перемещения):

указать диапазон внутри контейнера с помощью итераторов. В первом параметре передается итератор, указывающий на начало диапазона, а во втором параметре — итератор, указывающий на конец диапазона. Пример:

указать список инициализации, состоящий из объектов класса pair :

Вместо объектов класса pair можно указать ключи и значения через запятую внутри фигурных скобок:

Над двумя объектами класса unordered_map определены операции == и != . Кроме того, один объект можно присвоить другому объекту. В этом случае выполняется поэлементное копирование (оператор копирования) или перемещение элементов (оператор перемещения). Пример:

Доступно также присваивание элементов из списка инициализации:

Вставка элементов

Вставить элемент можно указав ключ внутри квадратных скобок. Значение элемента задается после оператора присваивания. Если ключ уже существует, то вместо вставки элемента производится изменение значения. Пример:

Вставить элементы позволяют следующие методы:

insert() — вставляет один или несколько элементов. Прототипы метода:

Первые два прототипа вставляют экземпляр класса pair и возвращают объект того же класса. Через свойство first будет доступен итератор, указывающий на вставленный элемент, а через свойство second — логическое значение true , если элемент вставлен, и false — в противном случае. Обратите внимание на то, что вставить можно только элемент, ключ которого не содержится в словаре. Пример:

Обратите внимание на то, что метод insert() в классе unordered_multimap возвращает итератор, а не объект класса pair . Прототипы метода в классе unordered_multimap :

Можно вставить элементы, имеющие одинаковый ключ:

Третий и четвертый прототипы позволяют подсказать позицию вставки с помощью итератора. Эта позиция может быть проигнорирована, т. к. ключи всегда следуют в строгом порядке. В качестве результата возвращается итератор, указывающий на вставленный элемент. Пример:

Пятый прототип вставляет элементы из диапазона, ограниченного итераторами first и last :

Шестой прототип вставляет элементы из списка инициализации:

emplace() — создает элемент и вставляет его в словарь. Метод возвращает объект класса pair . Через свойство first будет доступен итератор, указывающий на вставленный элемент, а через свойство second — логическое значение true , если элемент вставлен, и false — в противном случае. Обратите внимание на то, что вставить можно только элемент, ключ которого не содержится в словаре. Прототип метода:

Обратите внимание на то, что метод emplace() в классе unordered_multimap возвращает итератор, а не объект класса pair . Прототип метода в классе unordered_multimap :

Можно вставить элементы, имеющие одинаковый ключ:

emplace_hint() — аналогичен методу emplace() , но дополнительно позволяет подсказать позицию вставки с помощью итератора. Метод возвращает итератор на вставленный элемент или на существующий элемент (вставить элемент с одинаковым ключом нельзя). Прототип метода:

swap() — меняет элементы двух контейнеров местами. Прототип метода:

Вместо метода swap() можно воспользоваться одноименной функцией:

Определение количества элементов

Для определения количества элементов предназначены следующие методы:

size() — возвращает количество элементов в словаре. Прототип метода:

empty() — возвращает значение true , если словарь не содержит элементов, и false — в противном случае. Прототип метода:

max_size() — возвращает максимальное количество элементов, которое теоретически может содержаться в словаре. Прототип метода:

Удаление элементов

Для удаления элементов предназначены следующие методы:

erase() — удаляет один элемент или элементы из диапазона. Прототипы метода:

Первый прототип удаляет элемент с указанным ключом и возвращает количество удаленных элементов:

Второй прототип удаляет элемент на который указывает итератор:

Третий прототип удаляет элементы из диапазона, ограниченного итераторами first и last . Удалим все элементы:

clear() — удаляет все элементы. Прототип метода:

Доступ к элементам

К любому элементу словаря можно обратиться как к элементу массива. Достаточно указать его ключ внутри квадратных скобок. Можно как получить значение, так и изменить его. Если производится присваивание значения по ключу и ключа не существует, то производится вставка элемента. Если элемент уже существует, то его значение изменяется на новое. Если производится получение значения по ключу и ключа не существует, то элемент вставляется со значением по умолчанию для типа, а затем это значение возвращается. Пример:

Для доступа к элементам предназначены следующие методы:

at() — возвращает ссылку на элемент, ключ которого соответствует значению k . Метод позволяет как получить значение, так и изменить его. Если ключ не существует, то генерируется исключение out_of_range . Прототипы метода:

count() — возвращает количество элементов, у которых ключ соответствуют значению k . Прототип метода:

find() — возвращает итератор, установленный на элемент, ключ которого соответствует значению k . Если элемент не найден, то метод возвращает итератор, указывающий на позицию после последнего элемента. Прототипы метода:

equal_range() — возвращает экземпляр класса pair . Через свойство first будет доступен итератор, ссылающийся на первый элемент с указанным ключом, а через свойство second — итератор, ссылающийся на позицию после последнего элемента с указанным ключом. Если ключ отсутствует в словаре, то оба итератора будут ссылаться на значение, возвращаемое методом end() . Прототипы метода:

begin() , end() , cbegin() и cend() — возвращают итераторы (см. разд. 16.1.1). Обратите внимание: обратные итераторы не поддерживаются. Перебор возможен только в прямом порядке. Выведем ключ и значение первого элемента:

Обратите внимание: итераторы не поддерживают операторы + , — и — . Для перемещения итератора нужно использовать оператор ++ или функцию advance() . Пример доступа к третьему элементу словаря:

Вместо методов begin() и end() можно воспользоваться одноименными функциями. Выведем ключ и значение первого элемента:

Перебор элементов

Перебрать все элементы можно с помощью цикла for each , итераторов и алгоритма for_each() . Обратите внимание: перебор элементов возможен только в прямом направлении, кроме того, порядок следования элементов может быть произвольным. Пример использования цикла for each (внутри тела цикла можно изменить значение элемента, но ключ изменить нельзя):

Пример перебора элементов с помощью итераторов и цикла for :

Пример перебора элементов с помощью итераторов и цикла while :

С помощью алгоритма for_each() умножим значение каждого элемента на 2 , а затем выведем все ключи и значения в окно консоли:

Учебник C++ (Qt Creator и MinGW) в формате PDF

Помощь сайту

ПАО Сбербанк:
Счет: 40817810855006152256
Реквизиты банка:
Наименование: СЕВЕРО-ЗАПАДНЫЙ БАНК ПАО СБЕРБАНК
Корреспондентский счет: 30101810500000000653
БИК: 044030653
КПП: 784243001
ОКПО: 09171401
ОКОНХ: 96130
Скриншот реквизитов

Какой map быстрее, и есть ли альтернатива Judy

Кадр из Top Gear: USA (серия 2)

В своих самых высоконагруженных сервисах мы в Badoo используем язык C и иногда C++. Зачастую эти сервисы хранят в памяти сотни гигабайт данных и обрабатывают сотни тысяч запросов в секунду. И нам важно использовать не только подходящие алгоритмы и структуры данных, но и производительные их реализации.

Практически с самого начала в качестве реализации ассоциативных массивов мы использовали Judy. У неё есть C-интерфейс и множество преимуществ. Мы даже используем обёртку для PHP, так как в версиях PHP до 7.0 Judy сильно выигрывает по количеству потребляемой памяти по сравнению со встроенными мапами.

Однако время идёт, и с момента последнего релиза Judy прошло немало лет – самое время посмотреть на альтернативы.

Меня зовут Марко, я – системный программист Badoo в команде «Платформа». Мы с коллегами провели небольшое исследование в поисках альтернатив Judy, сделали выводы и решили поделиться ими с вами.

Ассоциативный массив

Если вы знаете, что такое ассоциативный массив, дерево и хеш-таблица, этот раздел можете смело пропускать. Для остальных – небольшое введение в тему.

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

Для примера можем взять банальный связный список. На put мы обойдём его весь от начала до конца, чтобы убедиться, что у нас ещё нет такого элемента, а если нет, то добавим его в конец списка; на get – просто обойдём список от начала до конца в поисках нужного элемента. Алгоритмическая сложность поиска и добавления элемента в такой ассоциативный массив – O(n), что не очень хорошо.

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

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

Хеш-таблица

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

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

Как? Вариантов множество. Первое, что приходит в голову, — использовать это число в качестве индекса в обычном массиве. Массиве, в котором лежат наши значения. Но этот вариант не будет работать как минимум по двум причинам:

Область значений хеш-функции, скорее всего, больше, чем размер массива, который бы нам хотелось хранить выделенным в памяти.

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

Как? Вариантов, опять же, много. Например, взять остаток от деления на размер массива или просто взять нужное количество младших бит числа, если размер массива у нас является степенью двойки (остаток от деления – значительно более медленная операция для процессора по сравнению со сдвигом, так что обычно предпочтение отдаётся именно массивам с размером, являющимся степенью двойки).

Я привёл в пример один из распространённых способов реализации хеш-таблицы, но вообще их великое множество. И в зависимости от выбранного способа борьбы с коллизиями мы получим разную производительность. Если же говорить об алгоритмической сложности для хеш-таблиц, то в среднем у нас будет O(1), а в вырожденных случаях (worst case) может получиться и O(n).

Деревья

С деревьями всё довольно просто. Для реализации ассоциативных массивов используются различные бинарные деревья – такие, как, например, красно-чёрное дерево. В случае если дерево сбалансировано, мы получим O(log n) на операцию.

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

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

На что смотрим?

Мир ассоциативных массивов, конечно, не чёрно-белый: у каждой реализации есть как преимущества, так и недостатки.

Разные реализации могут отличаться не только производительностью, но и набором предоставляемых функций. К примеру, какие-то реализации позволяют обходить элементы в порядке возрастания или убывания ключа, а какие-то – нет. И это ограничение связано с внутренней архитектурой, а не прихотями автора.

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

Прошли времена, когда О-нотации Кнута было достаточно для сравнения двух алгоритмов. Реальный мир гораздо сложнее. Современное железо, на котором работают наши программы, имеет многоуровневую память, доступ к разным уровням которой сильно отличается, и учёт этого может ускорить алгоритм в разы или на столько же его замедлить.

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

Паузы, максимальная задержка (latency) и отзывчивость тоже играют важную роль. Некоторые реализации ассоциативных массивов требуют одномоментного дорогостоящего перестроения своих внутренних структур при добавлении элемента, которому не повезло, а другие – «размазывают» эти задержки во времени.

Участники исследования

Judy (или Judy Array) – структура, придуманная Дугласом Баскинсом, реализующая упорядоченный ассоциативный массив. Реализация написана на C и крайне сложна. Автор попытался учесть современную архитектуру и использовать кеши процессора по максимуму.

Judy представляет из себя дерево, а не хеш-таблицу. И не просто дерево, а так называемое префиксное дерево. Для нас, потребителей, это означает, что, используя Judy, мы получаем сжатие ключей и возможность бежать по элементам в порядке возрастания или убывания ключа.

Judy предоставляет несколько вариаций «ключ/значение»:

Вариация	Ключ	Значение
Judy1	uint64_t	bit
JudyL	uint64_t	uint64_t
JudySL	null-terminated string	uint64_t
JudyHS	array of bytes	uint64_t

Judy1 удобно использовать для больших разреженных bitmap‘ов. JudyL является базовым типом, который мы в C-сервисах Badoo чаще всего и используем. JudySL, как видно, удобно использовать для строк, а JudyHL – просто для какого-то набора байт.

std::unordered_map

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

Это именно хеш-таблица, так что обход ключей по возрастанию или убыванию недоступен.

google::sparse_hash_map

Как видно из названия, sparse hash был разработан в Google и заявляет минимальный оверхед в размере всего два бита на значение. Он также реализован на C++ и сделан в виде шаблона (и это, на мой взгляд, несомненное преимущество реализаций на C++).

Кроме всего прочего, sparse hash умеет сохранять своё состояние на диск и загружаться с него.

google::dense_hash_map

Кроме sparse hash, Google сделала вариант под названием dense hash. Скорость у него (а особенно скорость get‘а) заметно выше, но за это приходится платить большим расходом памяти. Также, из-за того, что внутри у dense_hash_map плоские массивы, периодически требуется дорогое перестроение. Кстати, о таких проблемах и нюансах хеш-таблиц отлично рассказал Константин Осипов в своём докладе на HighLoad++. Рекомендую к изучению.

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

Аналогично sparse hash dense hash является хеш-таблицей и шаблоном. То есть, повторюсь, никакого прохождения по ключам в порядке возрастания, но при этом возможность использовать любые типы в качестве ключей и значений.

Также аналогично своему собрату sparse_hash_map dense_hash_map умеет сохранять своё состояние на диск.

spp::sparse_hash_map

И, наконец, последний претендент от одного из разработчиков google sparse hash. Автор взял за основу sparse hash и переосмыслил его, добившись минимального оверхеда в один бит на запись.

Всё то же самое: хеш-таблица и шаблон. Реализация на C++.

Претенденты представлены – пришло время проверить, на что они способны.

Ещё два фактора

Но сначала замечу, что на производительность и потребление памяти будут влиять ещё две вещи.

Хеш-функция

Все участники нашего исследования, являющиеся хеш-таблицами, используют хеш-функции.

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

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

В дополнение к стандартной хеш-функции из C++ я посмотрю, как справятся xxhash и t1ha.

Аллокация памяти

Второй фактор, который обязательно повлияет на наши результаты, — аллокатор памяти. От него напрямую зависят и скорость работы, и количество потребляемой памяти. Стандартный аллокатор из libc – это jack of all trades. Он хорош для всего, но ни для чего не идеален.

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

Результаты

Ниже представлены результаты теста по рандомному поиску среди десяти миллионов элементов. Два параметра, которые меня больше всего интересуют, – время выполнения теста и максимальная потреблённая память (RSS процесса в пике).

В качестве ключа я использовал 32-битное целое, а в качестве значения – указатель (64 бита). Именно такие размеры ключей и значений мы чаще всего используем.

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

Самым быстрым ассоциативным массивом оказался dense hash от Google. Следом идёт spp, и затем – std::unordered_map.

Однако если посмотреть на память, видно, что dense_hash_map потребляет её больше всех других реализаций. Собственно, именно это сказано в документации. Более того, если бы у нас в тесте были конкурирующие чтение и запись, мы бы, скорее всего, столкнулись со stop-the-world-перестроением. Таким образом, в приложениях, где важна отзывчивость и много записей, dense hash использовать нельзя.

Также я посмотрел на альтернативные реализации хеш-функций. Но, как оказалось, стандартная std::hash быстрее.

Коллега случайно заметил, что в случае 32- или 64-битных ключей std::hash по сути просто identity. То есть на входе и выходе – одно и то же число, или, другими словами, функция ничего не делает. хxhash и t1ha же честно считают хеш.

В плане производительности jemalloc полезен. Практически все реализации становятся быстрее.

Однако по потреблению памяти jemalloc не настолько хорош.

Исходный код и железо

Исходный код бенчмарков я выложил на github. При желании вы можете повторить мои тесты или расширить их.

Я же проводил тестирование на своём домашнем десктопе:

Ubuntu 17.04
Linux 4.10.0
Intel® Core(TM) i7-6700K CPU @ 4.00GHz
32 GiB DDR4 memory
GCC 6.3.0
Флаги компилятора: -std=c++11 -O3 -ffast-math

Краткие выводы и заключительные слова

Наши тесты показали хороший потенциал spp в качестве замены Judy. spp оказался быстрее на рандомных get‘ах, а его оверхед по памяти не слишком велик.

Мы сделали простенькую обёртку над C++ для C и в ближайшее время попробуем spp в одном из своих высоконагруженных сервисов.

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

Класс unordered_map

Шаблон класса описывает объект, который управляет последовательностью элементов типа std::pair<const Key, Ty> с переменной длиной. Последовательность слабо упорядочена хэш-функцией, которая разделяет последовательность в упорядоченный набор подпоследовательностей, называемых блоками. В каждом блоке функция сравнения определяет, упорядочена ли каждая пара элементов соответствующим образом. Каждый элемент содержит два объекта: ключ и значение сортировки. Последовательность представляется в виде, позволяющем выполнять поиск, вставку и удаление произвольного элемента несколькими операциями, которые могут не зависеть от числа элементов в последовательности (постоянное время), по крайней мере, когда все блоки имеют примерно одинаковую длину. В худшем случае, когда все элементы находятся в одном блоке, количество операций пропорционально количеству элементов в последовательности (линейное время). Кроме того, вставка элементов не делает итераторы недействительными, а при удалении элементов недействительными становятся только итераторы, указывающие на удаленный элемент.

Синтаксис

Параметры

Ty
Сопоставленный тип.

Hash
Тип объекта хэш-функции.

Pred
Тип объекта функции сравнения на предмет равенства.

Alloc
Класс распределителя.

Элементы

Определение типа	Описание
allocator_type	Тип распределителя для управления хранилищем.
const_iterator	Тип постоянного итератора для управляемой последовательности.
const_local_iterator	Тип постоянного итератора блока для управляемой последовательности.
const_pointer	Тип постоянного указателя на элемент.
const_reference	Тип постоянной ссылки на элемент.
difference_type	Тип расстояния со знаком между двумя элементами.
hasher	Тип хэш-функции.
iterator	Тип итератора для управляемой последовательности.
key_equal	Тип функции сравнения.
key_type	Тип ключа упорядочения.
local_iterator	Тип итератора блока для управляемой последовательности.
mapped_type	Тип сопоставленного значения, связанного с каждым ключом.
pointer	Тип указателя на элемент.
reference	Тип ссылки на элемент.
size_type	Тип беззнакового расстояния между двумя элементами.
value_type	Тип элемента.

Функция-член	Описание
at	Поиск элемента с заданным ключом.
begin	Задает начало управляемой последовательности.
bucket	Получает номер блока для значения ключа.
bucket_count	Получает количество блоков.
bucket_size	Получает размер блока.
cbegin	Задает начало управляемой последовательности.
cend	Задает конец управляемой последовательности.
clear	Удаляет все элементы.
count	Определяет количество элементов, соответствующих заданному ключу.
contains C++20	Проверьте наличие элемента с указанным ключом в элементе unordered_map .
emplace	Добавляет элемент, созданный на месте.
emplace_hint	Добавляет элемент, созданный на месте, с подсказкой.
empty	Проверяет отсутствие элементов.
end	Задает конец управляемой последовательности.
equal_range	Находит диапазон, соответствующий указанному ключу.
erase	Удаляет элементы в указанных позициях.
find	Определяет элемент, соответствующий указанному ключу.
get_allocator	Возвращает сохраненный объект распределителя.
hash_function	Получает сохраненный объект хэш-функции.
insert	Добавляет элементы.
key_eq	Получает сохраненный объект функции сравнения.
load_factor	Подсчитывает среднее число элементов в блоке.
max_bucket_count	Получает максимальное количество блоков.
max_load_factor	Возвращает или задает максимальное количество элементов в блоке.
max_size	Возвращает максимальный размер управляемой последовательности.
rehash	Повторно создает хэш-таблицу.
size	Подсчитывает количество элементов.
swap	Меняет местами содержимое двух контейнеров.
unordered_map	Создает объект контейнера.

Оператор	Описание
unordered_map::operator[]	Находит или вставляет элемент с указанным ключом.
unordered_map::operator=	Копирует хэш-таблицу.

Объект упорядочивает последовательность, которая управляется путем вызова двух сохраненных объектов, объекта функции сравнения типа unordered_map::key_equal и объекта хэш-функции типа unordered_map::hasher . Вы обращаетесь к первому сохраненного объекта, вызывая функцию-член unordered_map::key_eq () ; и обращаетесь ко второму сохраненного объекта, вызывая функцию-член unordered_map::hash_function () . В частности, для всех значений X и Y типа Key вызов key_eq()(X, Y) возвращает значение true, только если два значения аргументов имеют соответствующий порядок; вызов hash_function()(keyval) создает распределение значений типа size_t . В отличие от класса шаблона unordered_multimap класса, объект типа unordered_map гарантирует, что key_eq()(X, Y) всегда имеет значение false для всех двух элементов управляемой последовательности. (Ключи уникальны).

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

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

Объект выделяет и освобождает хранилище для последовательности, хранящейся в объекте распределителя типа unordered_map::allocator_type . Такой объект распределителя должен иметь тот же внешний интерфейс, что и объект типа allocator . Обратите внимание, что сохраненный объект распределителя не копируется, когда назначается объект контейнера.