С++ сравнивает предварительно зарезервированную хеш-карту (std::unordered_map) с целочисленным ключом и непрерывным массивом данных (std::vector)

Кроме того, когда общее (или максимальное) количество элементов N известно, хэш-таблица может быть построена заранее.

гм.резерв(N); // Это по цепочке вызовет функцию rehash()...

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

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

Тогда есть ли разница между построенной хеш-таблицей и std::vector, в использовании памяти или в механизме/производительности поиска или в чем-то еще?

да. После вашего .reserve(N) хеш-таблица выделяет непрерывный блок памяти (по сути, массив) как минимум для N сегментов. Если мы рассмотрим реализацию GCC, N будет округлено до простого числа. Каждое ведро может хранить итератор в прямом списке из pair<int, data_type> узлов.

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

• массив из ›= N элементов размера sizeof(forward-list-iterator)
• N выделений памяти ›= sizeof(pair<int, data_type>) + sizeof(next-pointer/iterator for forward-list)

... в то время как vector использует только около N * sizeof(data_type) байтов памяти: потенциально небольшая часть памяти, используемой хэш-таблицей, и, поскольку вся память вектора для data_types непрерывна, вы, скорее всего, выиграете от кэширования ЦП элементы, соседние с тем, к которому вы пытаетесь получить доступ в данный момент, так что все они будут намного быстрее доступны позже.

С другой стороны, если вы не поместили много элементов в хеш-таблицу, то основное использование памяти — это массив сегментов, содержащих итераторы, которые обычно имеют размер указателей (например, 32 или 64 бита каждый), тогда как вектор data_type - если вы reserve(N) там тоже - уже будет выделено N * sizeof(data_type) байтов памяти - для больших data_type это может быть значительно больше, чем хеш-таблица. Тем не менее, вы часто можете выделить виртуальную память, и если вы не ошиблись со страницами памяти, так что им нужна физическая резервная память, нет никакого значимого использования памяти или потери производительности для вашей программы или компьютера. (По крайней мере, с 64-битными программами виртуальное адресное пространство практически не ограничено).

Если я знаю, что 3 ключа 0,5, 9987 наверняка используются, но ключи 1~9986 могут использоваться или не использоваться.

Если я знаю, что ни один ключ в наборе не будет больше 10000, то использование std::vector размера 10000 гарантирует временную сложность O(1) для доступа к случайным данным, но память будет потрачена впустую.

В этой ситуации дает ли std::unordered_map лучшее решение проблемы? * Я имею в виду решение, которое экономит как можно больше памяти, сохраняя временную сложность на том же уровне.

В этой ситуации, если вы reversed(10000) заранее и data_type не намного больше, чем итератор/указатель, то unordered_map однозначно будет хуже во всех отношениях. Если вы не резервируете заранее, хеш-таблица будет выделять место только для нескольких сегментов, и вы будете использовать гораздо меньше виртуального адресного пространства, чем vector с 10000 элементами (даже если data_type было bool).

Все по-другому.

В unordered_map используется концепция сегментов.

Ведро — это слот во внутренней хеш-таблице контейнера, которому назначаются элементы на основе хеш-значения их ключа. Сегменты нумеруются от 0 до (bucket_count-1).

unordered_map вычисляет хеш-значение ключа, указывающего на ведро. Искомое значение находится в этом сегменте. Теперь обратите внимание, что несколько ключей могут указывать на одно ведро. В вашем случае может даже случиться так, что um[0],um[5] и um[9987] все лежат в одном ведре! Поиск внутри корзины линейен во времени.

В этой ситуации дает ли std::unordered_map лучшее решение проблемы?

Если у вас разреженные данные, используйте unordered_map, но с соответствующим резервом (или вообще без резерва и используйте политику распределения по умолчанию). Нет смысла делать myMap.reserve(MAX_ELEMENTS), так как это снова приведет к потере памяти.

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

Если у вас есть только 3 элемента для упаковки, лучшим решением является использование std::vector<std::pair<int, data_type>> :) Он занимает даже меньше памяти, чем std::unordered_map<int, data_type> (который фактически выделяет несколько векторов-сегментов), и производительность поиска также является лучшей для небольшого количества элементов из-за очень маленькие константы.

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