哈希图的内存高效数据结构（C++）

Question

场景很简单。

我得到一个值，范围在

0 and 2^x (x~27)

之间。现在我想使用这个值作为哈希图的键。然后，在哈希图中，我只存储一个索引（值的来源）。 x 也可能大于 27，所以我必须使用内存高效的数据结构。
我首先尝试了 unordered_multimap，但开销很大，因此取消了它的资格。然后我尝试了向量的 unordered_map 。但是增加地图中的向量数量，开销也太大了。所以我想到只使用二维数组并重新分配动态大小。
但正如我在 stackoverflow 上了解到的那样，调用 2^27 次“malloc()”也会产生开销，所以我尝试了这个：

uint64_t length = (uint64_t) pow(2.0,27);
uint64_t ** hashmap;
hashmap = (uint64_t **) malloc(sizeof * hashmap * length);
uint64_t * values = (uint64_t *) malloc(sizeof * values * 3 * length);


for(int i = 0;i<length;i++)
    hashmap[i] = values + 3 * i;

//Destroys the whole datastructure
hashmap[0] = (uint64_t *) realloc(hashmap[0],sizeof*hashmap[0]*4);

我分配

3 * siezof * values

来跟踪桶的实际长度和最大长度。
但正如评论所说，重新分配会破坏整个数组，也许是因为指针上没有簿记（通过 malloc），它只存储 3 个元素？ 有没有办法对此结构进行重新分配？或者你知道一个更好的结构来满足我的意图吗？

编辑dau_sama的回答原因：

使用以下代码时，我遇到性能问题（运行时和内存）：

std::unordered_map <uint64_t, std::vector<uint64_t>> m;
uint64_t length = 1UL<<22;
for(int i = 0 ; i<length;i++)
{
    m.emplace(i,vector<uint64_t>());
    m.at(i).push_back(i);
}

我将长度减少到 2^22，因为我在 7 分钟的运行时间和约 8GB 的内存使用量下中止了 2^27 实现。
该代码片段的运行时间为 60 秒，内存使用量约为 1.7GB。与上面的数组实现相比，数组占用了约 4GB 的内存，运行时间为 1.7 秒（2^27 个元素）。也许我做错了什么？

Answer 1

对不同地图进行了很好的比较： https://1ykos.github.io/patchmap/

Answer 2

很简单： 不要重新发明轮子，有一个

std::unordered_map<int, int>

来映射您需要的内容。很高兴您了解指针，但大多数情况下您实际上不需要直接调用

malloc

。