散列表需要大量內存

Question

我已經聲明並定義了下面的HashTable類。請注意，我需要散列表的哈希表，所以我的HashEntry結構包含一個HashTable指針。公共部分並不是什麼大事，它具有傳統的哈希表函數，所以爲了簡單起見我將它們刪除了。

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。當需要更大的表格大小時，使用以下列表。

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

我的問題是，這個類消耗這麼多的內存。我剛剛使用地塊進行了剖析，發現它需要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

由於您使用的是開放尋址，所以一半的散列槽必須爲空。由於HashEntry非常大，因此在每個空槽中存儲完整的HashEntry非常浪費。

，可以儲存您HashEntry結構別處，把HashEntry *在你的哈希表，或者切換到一個更加密集的客座率鏈接。任何一個都可以減少這種浪費。

另外，如果你要移動HashEntry對象周圍，交換，而不是複製，或者使用移動語義，所以你不必複製這麼多的字符串。請務必清除您不再使用的任何條目中的字符串。

而且，即使你說你需要哈希表的哈希表，你真的不解釋爲什麼。如果小散列表不具有內存效率，那麼使用具有有效表示的複合鍵的一個散列表通常更有效。

Answer 2

事實上，360461 HashEntry的需要20 MB是不足爲奇的。你有沒有試過看sizeof(HashEntry)？

每個HashEntry包括兩個標準::字符串，指針和3分int的。正如老笑話所說的那樣，要回答「字符串有多長？」這個問題並不容易，在這種情況下，因爲有大量的字符串實現和優化，所以您可能會發現sizeof(std::string)在4到32之間的任何位置字節。 （在32位體系結構中只有4個字節）。實際上，一個字符串需要三個指針和字符串本身，除非它恰好爲空。如果sizeof（std :: string）與sizeof（void *）相同，那麼你可能有一個不太近的GNU標準庫，其中std::string是一個不透明指針，指向包含兩個指針的塊，一個引用計數和字符串本身。如果sizeof（std :: string）是32個字節，那麼你可能有一個最近的GNU標準庫實現，其中字符串結構中有一些額外的空間用於短字符串優化。有關測量，請參閱Why does libc++'s implementation of std::string take up 3x memory as libstdc++?的答案。我們只需說每個字符串32個字節，並忽略細節;它不會太多。因此，兩個字符串（每個32字節）加上一個指針（8字節）加上三個字節（另一個12字節）和四個字節的填充，因爲其中一個字符串位於兩個8字節對齊的對象之間，這就是一個總數每個HashEntry有88個字節。如果您有360,461個散列條目，那麼這將是31,720,568字節，大約30 MB。事實上，你「僅」使用20MB，可能是因爲你使用的是舊的GNU標準庫，它將空字符串優化爲單個指針，並且大部分字符串都是空字符串，因爲一半的槽沒有被使用過。

現在，讓我們來看看rehash。減少到它的要領：

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，峯值內存使用率幾乎是其兩倍也就不足爲奇了。 （實際上，這又小得驚人地小，不出所料，可能實際上並不需要改變新矢量的地址，因爲它是在當前分配的存儲空間的末尾，這可能只是擴展。）

請注意，我們做了所有這些數據的兩個副本，並且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實際上並不需要複製字符串，因爲它們沒有改變。因此，我們可以將字符串保存在其他地方，比如說在一個字符串矢量中，並且只需在HashEntry中使用索引到矢量中。由於您不希望擁有數十億字符串，只有數百萬字符，索引可能是四字節的整數。也可以通過對HashEntry字段進行混洗，並將枚舉減少爲一個字節而不是四個字節（在C++ 11中，您可以指定枚舉的基本整數類型），HashEntry可以減少到24個字節， t是需要留出空間的字符串描述符。

Answer 3

我已經改變了我的結構，就像你所有的建議一樣，但有一件事沒人注意到。

當重新調整/調整大小時，我的rehash函數調用insert。在這個插入函數中，我增加了currentSize，它保存了散列表有多少個元素。所以每次需要調整大小時，currentSize應該保持不變。我刪除了該行，並編寫了適當的代碼進行重新調整，現在我認爲我沒事。

我現在使用了兩個不同的結構，程序爲800萬個元素消耗1.6GB內存，這是多字節字符串和整數所期望的結果。這個數字之前是7-8GB。