title: Memory efficient datastructure for hashmap (c++)
body: <p>The scenario is a kind of simple.</p>
  
  <p>I get a value, in range between <code>0 and 2^x (x~27)</code>. Now i would like to use this value also as key for a hashmap. In the hashmap I then just store an index (source of the value). x may be also greater then 27, so I have to use a memory efficient data structure.<br>
  I first tried an unordered_multimap, but there is a big overhead, disqualifying it. Then i tried an unordered_map of vectors. But by increasing number of vectors in the map, the overhead is also too big. So I thought of just using a 2d Array with reallocating for dynamic size.<br>
  But as I learned here on stackoverflow calling 2^27 times "malloc()" creates also an overhead, so i tried this:</p>
  
  <pre><code>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&lt;length;i++)
      hashmap[i] = values + 3 * i;
  
  //Destroys the whole datastructure
  hashmap[0] = (uint64_t *) realloc(hashmap[0],sizeof*hashmap[0]*4);
  </code></pre>
  
  <p>I allocate <code>3 * siezof * values</code> to keep track of actual length and maximal length of the bucket. <br>
  But as the comment says the reallocating destroys the whole arrray, maybe because there is no bookkeeping (via malloc) on the pointer  that it just stores 3 elements?
  Is there a way to do a realloc on this structure? Or do u even know a better structure for my intend?</p>
  
  <p>Edit cause of dau_sama's Answer:</p>
  
  <p>While using the following Code, I'm excpierencing performance problems (runtime and memory):</p>
  
  <pre><code>std::unordered_map &lt;uint64_t, std::vector&lt;uint64_t&gt;&gt; m;
  uint64_t length = 1UL&lt;&lt;22;
  for(int i = 0 ; i&lt;length;i++)
  {
      m.emplace(i,vector&lt;uint64_t&gt;());
      m.at(i).push_back(i);
  }
  </code></pre>
  
  <p>I reduced the length to 2^22 cause i aborted the 2^27 implementation at a runtime of 7 Minutes and a memory usage of ~8GB. <br>
  This snippet has a runtime of 60 seconds and a memory usage of ~1.7GB. Compared to the above array implementation that's alot, array took ~4GB of memory and a runtime of 1.7 seconds (at 2^27 elements). Maybe I'm doing something wrong?</p>