我的理解是：
unordered_map插入冲突时，或者调用unordered_map::reserve()时，都会rehash重新计算桶个数。
个数计算默认使用下一个素数：
__buckets = _M_rehash_policy._M_next_bkt(__buckets);
标准lib内部有一个64bit以内的素数表，这个表大概有300个元素。
也就是说rehash最多300次。
如果使用unordered_map的时候知道至多会插入n个元素，也可以：
unordered_map::reserve(n)
这样便不会产生rehash，因为rehash很贵。
当你的unordered_map构造完成后，如果装了n个元素，最少用的内存大概就是：
next_prime(n) * sizeof(void *) + n * (sizeof(void *) + sizeof(std::pair<key, value>)
一般来讲，n和next_prime(n)的差距不会很大，估计成：next_prime(n) = n + k：
n * (2 * sizeof(void *) + sizeof(std::pair<key, value>)) + k * sizeof(void *)
第一部分就是实际消耗给内部节点的，extra cost是两个pointer的价格。
第二部分就是没有用到的空bucket，比起第一部分不大，这个可以用素数表算出来。
我有一个1亿（还是1千万，忘了）个元素的unordered_map，k/n大概是小于5%。整体第二部分可以忽略不计了。
如果你测出来内存使用量远大于这个数字，那就是内存碎片导致的。
你可以考虑自己实现一个allocator，精确控制所有element都在一个大memory chunk上。
========================
对于std::map，一个node不仅包含std::pair<key, value>，还需要3个pointer和一个marker。
三个pointer是left, right, parent。因为是红黑树，还有一个color_marker，对齐后extra cost是32个字节。
如果std::map有n个元素，最小使用内存为：
n * (4 * sizeof(void *) + sizeof(std::pair<key, value>))
可以看出内存实际上比unordered_map要多。
当然这是不考虑memory slicing，有memory allocator的时候可以达到这个内存使用量。
【 在 meizhi 的大作中提到: 】
: 我不懂啊，之前有个工程大量用了map和unordered_map，发现unordered_map内存吃了很多，map速度又差点意思，再后来换用trie树了。按说unordered_map会多开一些空间啊，毕竟添加元素的时候哈希值不是连续的
: 发自「今日水木 on Redmi Note 7」
--
修改:allegro FROM 209.249.20.*
FROM 209.249.20.*