无序地图占用大量空间

Question

我创建了unit64_t到uint64_t的映射。这是我为评估空间复杂度而编写的代码：

#include <bits/stdc++.h>
#include "sparsehash/internal/sparseconfig.h"
#include "sparsehash/sparse_hash_map"

using namespace std;

int main(int argc, char *argv[]){

    std::string input,reference;

    while (getline(cin,input)) {
    reference += input;
    input.clear();
    }

    cout<<"length of reference = "<<reference.length()<<endl;
    unordered_map<uint64_t, uint64_t> m;
    //google::sparse_hash_map<uint64_t, pair<short,long>> m;

    for (auto it = reference.begin(); it != reference.end(); it++) {
        m[it-reference.begin()]= it-reference.begin();
    }

    return 0;
}

当我使用 /usr/bin/time 运行此命令时，这是程序产生的输出：

length of reference = 4641652
    Command being timed: "./a.out"
    User time (seconds): 2.97
    System time (seconds): 0.15
    Percent of CPU this job got: 99%
    Elapsed (wall clock) time (h:mm:ss or m:ss): 0:03.13
    Average shared text size (kbytes): 0
    Average unshared data size (kbytes): 0
    Average stack size (kbytes): 0
    Average total size (kbytes): 0
    Maximum resident set size (kbytes): 251816
    Average resident set size (kbytes): 0
    Major (requiring I/O) page faults: 0
    Minor (reclaiming a frame) page faults: 68259
    Voluntary context switches: 1
    Involuntary context switches: 104
    Swaps: 0
    File system inputs: 0
    File system outputs: 0
    Socket messages sent: 0
    Socket messages received: 0
    Signals delivered: 0
    Page size (bytes): 4096
    Exit status: 0

无序地图似乎占用了250MB的空间。这似乎异常高。为什么会出现这种情况。与google稀疏哈希相同的代码只需要89MB的空间，比较合理。

我不明白为什么C++无序映射占用这么多空间？

Answer 1

您有

4641652

条条目。所以总的原始数据大小是

4641652*2*8 byte ~= 74 MB

。

关于哈希表有一个重要事实。哈希桶数量多的哈希表速度快，哈希桶数量少的哈希表速度慢。

这基本上都归结为哈希冲突。如果你有很多哈希桶（并且你有一个很好的哈希函数），那么哈希冲突就很少发生。因此查找速度真的非常快。 另一方面，如果您的表很小（哈希桶不多），则哈希冲突会定期发生。因此查找功能要慢得多。

现在

std::unordered_map

被设计为一个快速哈希表，所以它有相当大的开销。哈希桶的数量比条目多得多。在这种情况下，开销约为

250 / 74 ~= 3.3x

，这似乎很正常。

但是

sparsehash

的设计目标是尽可能减少开销（每个条目大约 2 位）。但这当然意味着速度要慢得多。

如果您使用哈希映射，您应该始终考虑是想要速度还是想要提高内存效率。

Answer 2

两个值的总和 这个问题来自 CSES 问题集，使用 std::map 提供 AC 并给出带有 std::unordered_map 的 TLE。所以hashmap肯定需要更大的内存