C++ 比较预保留哈希映射 (std::unordered_map) 与整数键和连续数据数组 (std::vector)
C++ comparing a pre-reserved hash map(std::unordered_map) with integer key and contiguous data array(std::vector)
假设使用具有 int 键类型的 散列映射 结构：
std::unordered_map<int, data_type> um;
此外，当元素的总数（或最大）数N已知时，可以提前构造散列table。
um.reserve(N); // This will chainly call rehash() function...
这里，据我所知，整数本身可以用作哈希 table 的 identity(hash) 函数。
同时，对于连续数据集（即std::vector，或者一个简单的数组），它可以是随机访问 从最前面数据的地址位移。
两个容器都使用 int 作为访问密钥，如下所示：
um[1] = data_type(1); //std::unordered_map<int, data_type>
v[1] = data_type(1); //std::vector<data_type>
那么，构造的hash table和std::vector在内存使用、搜索mechanism/performance或者其他方面有什么不同吗？
让我们把问题具体化。
如果我知道0,5,99873个key肯定用到，但是key1~9986不一定用用过。
如果我知道集合中没有密钥会大于 10000，那么使用 std::vector 大小 10000 将保证访问随机数据的时间复杂度为 O(1)，但是会浪费内存。
在这种情况下，std::unordered_map 是否为问题提供了更好的解决方案？
*我的意思是，尽可能多地节省内存，同时将时间复杂度保持在同一水平的解决方案。
一切都不一样了。
一个unordered_map有buckets-
的概念
A bucket is a slot in the container's internal hash table to which elements are assigned based on the hash value of their key. Buckets are numbered from 0 to (bucket_count-1).
一个unordered_map计算指向一个bucket的key的hash值。所需的值在该存储桶中。现在请注意，多个键可以指向一个桶。在您的情况下，甚至可能 um[0]、um[5] 和 um[9987] 都位于同一个桶中！桶内搜索在时间上是线性的。
In this situation, does std::unordered_map produce a better solution for the problem?
如果您的数据稀疏，请使用 unordered_map 但要有适当的保留（或者根本没有保留并使用默认分配策略）。如果您执行 myMap.reserve(MAX_ELEMENTS) 是没有意义的，因为那将再次导致内存浪费。
否则，使用向量。您将获得有保证的 O(1) 查找。由于它是线性的，所以它超级 cache-friendly。而在 unordered_map 上，您可能会得到 O(N)
的最坏情况查找
此外，当元素的总数（或最大）数N已知时，可以预先构造散列table。
um.reserve(N); // 这将链式调用 rehash() 函数...
Here, an integer itself can be used as an identity(hash) function for a hash table, as far as I know.
这是正确的，并且在两种截然不同的情况下是合理的：1) 当值非常连续且可能有一些缺失值时，或 2) 当值非常随机时。在许多其他情况下，如果您不提供有意义的散列函数，您可能会冒过多散列 table 冲突的风险。
Then, is there any difference between the constructed hash table and std::vector, in memory usage or in searching mechanism/performance, or in anything else?
是的。在你的 .reserve(N) 之后，散列 table 为至少 N 个“桶”分配了一个连续的内存块（基本上是一个数组）。如果我们考虑 GCC 实现，N 将四舍五入为素数。每个桶 可以 将迭代器存储到 forward-linked 列表 pair<int, data_type> 节点中。
因此，如果您实际上将 N 个条目放入散列 table，您有...
sizeof(forward-list-iterator) 大小的 >= N 个元素的数组- N 内存分配 >=
sizeof(pair<int, data_type>) + sizeof(next-pointer/iterator for forward-list)
...而 vector 仅使用大约 N * sizeof(data_type) 字节的内存：可能是散列 table 使用的内存的一小部分，以及向量的所有内存因为 data_types 是连续的，您更有可能受益于与您当前尝试访问的元素相邻的 CPU 缓存元素，这样以后访问它们的速度就会快得多。
另一方面，如果您没有将很多元素放入散列中 table，那么使用内存的主要对象是包含迭代器的桶数组，通常是指针的大小（例如每个 32 或 64 位），而 data_type 的向量 - 如果你 reserve(N) 也在那里 - 已经分配了 N * sizeof(data_type) 字节的内存 - 对于大 data_type 可能远远超过散列 table。尽管如此，您仍然可以经常分配虚拟内存，并且如果您没有对内存页进行错误处理以致于它们需要物理后备内存，则不会对您的程序或计算机造成有意义的内存使用或性能损失。 （至少对于 64 位程序，虚拟地址 space 实际上是无限的）。
If I know that 3 keys 0,5, 9987 are certainly used, but keys 1~9986 may or may not be used.
If I know no key in the set would be bigger than 10000, then using std::vector of size 10000 will guarantee O(1) time complexity for accessing random data, but memory would be wasted.
In this situation, does std::unordered_map produce a better solution for the problem? *I mean, a solution that saves as much memory as possible while maintaining the time complexity in the same level.
在这种情况下，如果你在前面 reversed(10000) 而 data_type 并不明显大于 iterator/pointer，那么 unordered_map看待。如果您不预先保留，散列 table 只会为少数几个桶分配 space，并且您使用的虚拟地址 space 会比 vector 有 10000 个元素（即使 data_type 是 bool）。
如果你只有 3 个元素要打包，最好的解决方案是使用 std::vector<std::pair<int, data_type>> :) 它占用的内存比 std::unordered_map<int, data_type> 更少（实际上分配了几个 vectors-buckets），由于常量非常小，查找性能对于少量元素也是最好的。
对于较大的地图，O(1) 复杂度由 std::vector<data_type> 和 std::unordered_map<int, data_type> 保证，但隐藏在 O 中的常量对于向量来说要低得多，因为它不需要根据桶中的其他元素检查元素。我建议总是喜欢 vector 除非你没有内存来适应它，在这种情况下你可以通过牺牲一点性能来使用 unordered_map 来节省内存。
假设使用具有 int 键类型的 散列映射 结构：
std::unordered_map<int, data_type> um;
此外，当元素的总数（或最大）数N已知时，可以提前构造散列table。
um.reserve(N); // This will chainly call rehash() function...
这里，据我所知，整数本身可以用作哈希 table 的 identity(hash) 函数。
同时，对于连续数据集（即std::vector，或者一个简单的数组），它可以是随机访问 从最前面数据的地址位移。
两个容器都使用 int 作为访问密钥，如下所示：
um[1] = data_type(1); //std::unordered_map<int, data_type>
v[1] = data_type(1); //std::vector<data_type>
那么，构造的hash table和std::vector在内存使用、搜索mechanism/performance或者其他方面有什么不同吗？
让我们把问题具体化。
如果我知道0,5,99873个key肯定用到，但是key1~9986不一定用用过。
如果我知道集合中没有密钥会大于 10000，那么使用 std::vector 大小 10000 将保证访问随机数据的时间复杂度为 O(1)，但是会浪费内存。
在这种情况下，std::unordered_map 是否为问题提供了更好的解决方案？
*我的意思是，尽可能多地节省内存，同时将时间复杂度保持在同一水平的解决方案。
一切都不一样了。
一个unordered_map有buckets-
的概念A bucket is a slot in the container's internal hash table to which elements are assigned based on the hash value of their key. Buckets are numbered from 0 to (bucket_count-1).
一个unordered_map计算指向一个bucket的key的hash值。所需的值在该存储桶中。现在请注意，多个键可以指向一个桶。在您的情况下，甚至可能 um[0]、um[5] 和 um[9987] 都位于同一个桶中！桶内搜索在时间上是线性的。
In this situation, does std::unordered_map produce a better solution for the problem?
如果您的数据稀疏，请使用 unordered_map 但要有适当的保留（或者根本没有保留并使用默认分配策略）。如果您执行 myMap.reserve(MAX_ELEMENTS) 是没有意义的，因为那将再次导致内存浪费。
否则，使用向量。您将获得有保证的 O(1) 查找。由于它是线性的，所以它超级 cache-friendly。而在 unordered_map 上，您可能会得到 O(N)
此外，当元素的总数（或最大）数N已知时，可以预先构造散列table。
um.reserve(N); // 这将链式调用 rehash() 函数...
Here, an integer itself can be used as an identity(hash) function for a hash table, as far as I know.
这是正确的，并且在两种截然不同的情况下是合理的：1) 当值非常连续且可能有一些缺失值时，或 2) 当值非常随机时。在许多其他情况下，如果您不提供有意义的散列函数，您可能会冒过多散列 table 冲突的风险。
Then, is there any difference between the constructed hash table and std::vector, in memory usage or in searching mechanism/performance, or in anything else?
是的。在你的 .reserve(N) 之后，散列 table 为至少 N 个“桶”分配了一个连续的内存块（基本上是一个数组）。如果我们考虑 GCC 实现，N 将四舍五入为素数。每个桶 可以 将迭代器存储到 forward-linked 列表 pair<int, data_type> 节点中。
因此，如果您实际上将 N 个条目放入散列 table，您有...
sizeof(forward-list-iterator)大小的 >= N 个元素的数组- N 内存分配 >=
sizeof(pair<int, data_type>) + sizeof(next-pointer/iterator for forward-list)
...而 vector 仅使用大约 N * sizeof(data_type) 字节的内存：可能是散列 table 使用的内存的一小部分，以及向量的所有内存因为 data_types 是连续的，您更有可能受益于与您当前尝试访问的元素相邻的 CPU 缓存元素，这样以后访问它们的速度就会快得多。
另一方面，如果您没有将很多元素放入散列中 table，那么使用内存的主要对象是包含迭代器的桶数组，通常是指针的大小（例如每个 32 或 64 位），而 data_type 的向量 - 如果你 reserve(N) 也在那里 - 已经分配了 N * sizeof(data_type) 字节的内存 - 对于大 data_type 可能远远超过散列 table。尽管如此，您仍然可以经常分配虚拟内存，并且如果您没有对内存页进行错误处理以致于它们需要物理后备内存，则不会对您的程序或计算机造成有意义的内存使用或性能损失。 （至少对于 64 位程序，虚拟地址 space 实际上是无限的）。
If I know that 3 keys 0,5, 9987 are certainly used, but keys 1~9986 may or may not be used.
If I know no key in the set would be bigger than 10000, then using std::vector of size 10000 will guarantee O(1) time complexity for accessing random data, but memory would be wasted.
In this situation, does std::unordered_map produce a better solution for the problem? *I mean, a solution that saves as much memory as possible while maintaining the time complexity in the same level.
在这种情况下，如果你在前面 reversed(10000) 而 data_type 并不明显大于 iterator/pointer，那么 unordered_map看待。如果您不预先保留，散列 table 只会为少数几个桶分配 space，并且您使用的虚拟地址 space 会比 vector 有 10000 个元素（即使 data_type 是 bool）。
如果你只有 3 个元素要打包，最好的解决方案是使用 std::vector<std::pair<int, data_type>> :) 它占用的内存比 std::unordered_map<int, data_type> 更少（实际上分配了几个 vectors-buckets），由于常量非常小，查找性能对于少量元素也是最好的。
对于较大的地图，O(1) 复杂度由 std::vector<data_type> 和 std::unordered_map<int, data_type> 保证，但隐藏在 O 中的常量对于向量来说要低得多，因为它不需要根据桶中的其他元素检查元素。我建议总是喜欢 vector 除非你没有内存来适应它，在这种情况下你可以通过牺牲一点性能来使用 unordered_map 来节省内存。