title: hashtable needs lots of memory
body: <p>I've declared and defined the following HashTable class. Note that I needed  a hashtable of hashtables so my HashEntry struct contains a HashTable pointer. The public part is not a big deal it has the traditional hash table functions so I removed them for simplicity.</p>
  
  <pre><code>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 &amp;k = std::string(),
                  Status s = EMPTY,
                  const std::string &amp;u = std::string(),
                  const int &amp;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&lt;HashEntry&gt; array;
      int currentSize;
  public:
      HashTable(int size = 1181, int csz = 0): array(size), currentSize(csz){}
  };
  </code></pre>
  
  <p>I am using quadratic probing and I double the size of the vector in my rehash function when I hit <code>array.size()/2</code>. The following list is used when a larger table size is needed.</p>
  
  <pre><code>int a[16] = {49663, 99907, 181031, 360461,...}
  </code></pre>
  
  <p>My problem is that this class consumes so much memory. I've just profiled it with massif and found out that it needs 33MB(33 million bytes!) of memory for 125000 insertion. To be clear, actually</p>
  
  <pre><code>1 insertion -&gt; 47352 Bytes
  
  8 insertion -&gt; 48376 Bytes
  
  512 insertion -&gt; 76.27KB
  
  1000 insertion 2MB (array size increased to 49663 here)
  
  27000 insertion-&gt; 8MB (array size increased to 99907 here)
  
  64000 insertion -&gt; 16MB (array size increased to 181031 here)
  
  125000 insertion-&gt; 33MB (array size increased to 360461 here)
  </code></pre>
  
  <p>These may be unnecessary but I just wanted to show you how memory usage changes with the input. As you can see, when rehashing is done, memory usage doubles. For example, our initial array size was 1181. And we have just seen that 125000 elements -> 33MB.</p>
  
  <p>To debug the problem, I changed the initial size to 360461. Now 127000 insertion does not need rehashing. And I see that 20MB of memory is used with this initial value. That is still huge, but I think it suggests there is a problem with rehashing. The following is my rehash function.</p>
  
  <pre><code>void HashTable::rehash(){
      std::vector&lt;HashEntry&gt; oldArray = array;
  
      array.resize(nextprime(array.size()));
      for(int j = 0; j &lt; array.size(); j++){
          array[j].current_status = EMPTY;
      }
      for(int i = 0; i &lt; 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 &gt;= a[i]){i++;}
      return a[i];
  }
  </code></pre>
  
  <p>This is the insert function used in rehashing and everywhere else.</p>
  
  <pre><code>bool HashTable::insert(const std::string &amp;k){
      int currentPos = findPos(k);
      if(isActive(currentPos)){
          return false;
      }
      array[currentPos] = HashEntry(k, ACTIVE);
      if(++currentSize &gt; array.size() / 2){
          rehash();
      }
      return true;
  }
  </code></pre>
  
  <p>What am I doing wrong here? Even if it's caused by rehashing, when no rehashing is done it is still 20MB and I believe 20MB is way too much for 100k items. This hashtable is supposed to contain like 8 million elements.</p>