c++ - hashmap 的内存高效数据结构 (c++)

Question

场景比较简单。

我得到一个值，范围在 0 和 2^x (x~27) 之间。现在我想将此值也用作 HashMap 的键。然后在 HashMap 中我只存储一个索引(值的来源)。 x 也可能大于 27，所以我必须使用内存高效的数据结构。
我首先尝试了一个 unordered_multimap，但是有很大的开销，取消了它的资格。然后我尝试了一个 unordered_map vector 。但是通过增加 map 中的 vector 数量，开销也太大了。所以我想到了只使用二维数组重新分配动态大小。
但是正如我在 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 个元素？有没有办法在这个结构上做一个realloc？或者你是否知道一个更好的结构来满足我的意图？

编辑 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

很简单:不要重新发明轮子，有一个std::unordered_map<int, int>映射你需要的东西。很高兴您了解指针，但您实际上不需要调用 malloc大多数情况下直接。