c++ - 哈希表需要大量内存

Question

我已经声明并定义了以下 HashTable 类。请注意，我需要一个哈希表的哈希表，因此我的 HashEntry 结构包含一个 HashTable 指针。公共(public)部分没什么大不了的，它具有传统的哈希表函数，因此为简单起见，我删除了它们。

enum Status{ACTIVE, DELETED, EMPTY};
enum Type{DNS_ENTRY, URL_ENTRY};

class HashTable{
private:
    struct HashEntry{
        std::string key;
        Status current_status;
        std::string ip;
        int access_count;
        Type entry_type;
        HashTable *table;

        HashEntry(
                const std::string &k = std::string(),
                Status s = EMPTY,
                const std::string &u = std::string(),
                const int &a = int(),
                Type e = DNS_ENTRY,
                HashTable *t = NULL
                ): key(k), current_status(s), ip(u), access_count(a), entry_type(e), table(t){}
    };

    std::vector<HashEntry> array;
    int currentSize;
public:
    HashTable(int size = 1181, int csz = 0): array(size), currentSize(csz){}
};

我正在使用二次探测，当我点击 array.size()/2 时，我在重新哈希函数中将 vector 的大小加倍。当需要更大的表大小时使用以下列表。

int a[16] = {49663, 99907, 181031, 360461,...}

我的问题是这个类消耗了太多内存。我刚刚用 massif 分析了它，发现它需要 33MB(3300 万字节!)的内存来进行 125000 次插入。说清楚，实际上

1 insertion -> 47352 Bytes

8 insertion -> 48376 Bytes

512 insertion -> 76.27KB

1000 insertion 2MB (array size increased to 49663 here)

27000 insertion-> 8MB (array size increased to 99907 here)

64000 insertion -> 16MB (array size increased to 181031 here)

125000 insertion-> 33MB (array size increased to 360461 here)

这些可能是不必要的，但我只是想向您展示内存使用如何随着输入而变化。如您所见，重新散列完成后，内存使用量翻倍。例如，我们的初始数组大小为 1181。我们刚刚看到 125000 个元素 -> 33MB。

为了调试问题，我将初始大小更改为 360461。现在 127000 插入不需要重新散列。我看到这个初始值使用了 20MB 的内存。这仍然很大，但我认为这表明重新散列存在问题。以下是我的 rehash 函数。

void HashTable::rehash(){
    std::vector<HashEntry> oldArray = array;

    array.resize(nextprime(array.size()));
    for(int j = 0; j < array.size(); j++){
        array[j].current_status = EMPTY;
    }
    for(int i = 0; i < oldArray.size(); i++){
        if(oldArray[i].current_status == ACTIVE){
            insert(oldArray[i].key);
            int pos = findPos(oldArray[i].key);
            array[pos] = oldArray[i];
        }
    }
}
int nextprime(int arraysize){
    int a[16] = {49663, 99907, 181031, 360461, 720703, 1400863, 2800519, 5600533, 11200031, 22000787, 44000027};
    int i = 0;
    while(arraysize >= a[i]){i++;}
    return a[i];
}

这是在重新散列和其他地方使用的插入函数。

bool HashTable::insert(const std::string &k){
    int currentPos = findPos(k);
    if(isActive(currentPos)){
        return false;
    }
    array[currentPos] = HashEntry(k, ACTIVE);
    if(++currentSize > array.size() / 2){
        rehash();
    }
    return true;
}

我在这里做错了什么？即使它是由重新散列引起的，当没有进行重新散列时它仍然是 20MB，我相信 20MB 对于 100k 项目来说太多了。这个哈希表应该包含大约 800 万个元素。

Answer 1

360,461 个 HashEntry 占用 20 MB 的空间这一事实不足为奇。您是否尝试查看 sizeof(HashEntry)？

每个 HashEntry 包括两个 std::strings、一个指针和三个 int。正如老笑话所说，要回答“一个字符串有多长？”这个问题并不容易，在这种情况下，因为有各种各样的字符串实现和优化，所以您可能会发现 sizeof(std: :string) 是 4 到 32 字节之间的任何位置。 (在 32 位架构上它只有 4 个字节。)实际上，一个字符串需要三个指针和字符串本身，除非它恰好为空。如果 sizeof(std::string) 与 sizeof(void*) 相同，那么您可能有一个不太新的 GNU 标准库，其中 std::string 是一个指向包含两个指针、一个引用计数和字符串本身的 block 的不透明指针。如果 sizeof(std::string) 是 32 字节，那么您可能有一个最近的 GNU 标准库实现，其中在字符串结构中有一些额外的空间用于短字符串优化。查看 Why does libc++'s implementation of std::string take up 3x memory as libstdc++? 的答案进行一些测量。假设每个字符串 32 个字节，忽略细节；它不会关闭太多。

所以两个字符串(每个 32 个字节)加上一个指针(8 个字节)加上三个 int(另外 12 个字节)和四个填充字节，因为其中一个 int 在两个 8 字节对齐的对象之间，总共是每个 HashEntry 88 个字节。如果您有 360,461 个哈希条目，那将是 31,720,568 字节，大约 30 MB。您“仅”使用 20MB 的事实可能是因为您使用的是旧的 GNU 标准库，它将空字符串优化为单个指针，并且您的大部分字符串都是空字符串，因为一半的插槽从未使用过.

现在，让我们看一下重新哈希。精简到最基本的:

void rehash() {
  std::vector<HashEntry> tmp = array;  /* Copy the entire array */
  array.resize(new_size());            /* Internally does another copy */
  for (auto const& entry : tmp)
    if (entry.used()) array.insert(entry);  /* Yet another copy */
}

在高峰期，我们有两个较小数组的拷贝以及新的大数组。即使新阵列只有 20 MB，峰值内存使用量几乎是它的两倍也就不足为奇了。 (事实上​​ ，这再次出人意料地小，而不是出奇地大。可能实际上不需要更改新 vector 的地址，因为它位于当前分配的内存空间的末尾，可以扩展。)

请注意，我们为所有这些数据做了两份拷贝，array.resize() 可能做了另一份。让我们看看是否可以做得更好:

void rehash() {
  std::vector<HashEntry> tmp(new_size());  /* Make an array of default objects */
  for (auto const& entry: array) 
    if (entry.used()) tmp.insert(entry);   /* Copy into the new array */
  std::swap(tmp, array);                   /* Not a copy, just swap three pointers */
}

这样，我们只做一份。我们不是通过调整大小进行(可能的)内部复制，而是对新元素进行批量构造，这应该是相似的。 (它只是将内存归零。)

此外，在新版本中，我们每个只复制一次实际字符串，而不是每个复制两次，这是复制中最繁琐的部分，因此可能会节省相当多的钱。

适当的字符串管理可以进一步减少开销。 rehash 实际上不需要复制字符串，因为它们没有改变。所以我们可以将字符串保存在别处，比如在字符串 vector 中，并且只需在 HashEntry 中使用 vector 中的索引。由于您不希望保存数十亿个字符串，只有数百万个，因此索引可以是一个四字节的 int。通过还混洗 HashEntry 字段并将枚举减少到一个字节而不是四个字节(在 C++11 中，您可以指定枚举的基础整数类型)，HashEntry 可以减少到 24 个字节，并且不会不需要为尽可能多的字符串描述符留出空间。