首先我们是讨论标准库。需要第三方库支持其实已经说明定义一个实用可靠的 hash 是非平凡的工作，即使代码量不长但组合两个 hash 值应该用什么算法就值得想想。讲道理，pod类型的hash本来就应该是自动的，但实际做不到，对吧？
【 在 here080 的大作中提到: 】
: C++数据类型定义hash很容易啊
: 如果用ABSL库就更方便了：
: https://abseil.io/docs/cpp/guides/hash
: ...................
--
FROM 120.36.50.*

有时候就是想顺序遍历呀  
  
【 在 allegro () 的大作中提到: 】
: 时间复杂度unordered_map吊打。
: 空间复杂度差不多，stl实现里面unordered_map的一个node的额外消耗只有map的node的一半。
: 如果不需要一颗排好序的树，基本没有什么理由使用map了吧？
--
FROM 138.19.103.*

惭愧啊，我竟然从来没用过这个。
跟map比，除了按照插入顺序保存，还有啥优点吗？

不过你这一说倒是提醒我了，我现在有些类似场景都是map存数据，vector存key来记录顺序，可以去改改代码

【 在 allegro 的大作中提到: 】
:
: 时间复杂度unordered_map吊打。
: 空间复杂度差不多，stl实现里面unordered_map的一个node的额外消耗只有map的node的一半。
: 如果不需要一颗排好序的树，基本没有什么理由使用map了吧？

#发自zSMTH@一代鸡皇水果iPhone 250 MAX
--

※ 来源:水木社区 [82.19.154.*(英国)]

#修改自zSMTH@一代鸡皇水果iPhone 250 MAX
※ 修改:·one4all4one 于 Jun 17 17:12:06 2020 修改本文·[FROM: 82.19.154.*]
※ 来源:·水木社区 http://www.newsmth.net·[FROM: 82.19.154.*]

修改:one4all4one FROM 82.19.154.*
FROM 82.19.154.*

更少
【 在 meizhi 的大作中提到: 】
: 纯外行，unordered_map内存占用更多吧
: 发自「今日水木 on Redmi Note 7」
--
FROM 73.63.211.*

我的理解是：

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.*