共计 858 个字符，预计需要花费 3 分钟才能阅读完成。
map 与 unordered_map 都是 c ++ stl 中的关联容器，两者的应用也都大致相同。不过在底层的实现上，map 应用的是红黑树，unordered_map 应用的则是 hash 表。
红黑树
红黑树是一种绝对均衡的二叉搜寻树，并且其附加定义如下：
- 节点有且只有两种色彩，红色和彩色
- 根节点和叶子节点必须是彩色，其中，叶子节点是虚构存在的空节点 NULL
- 红色节点的两个子节点必须是彩色
- 任意节点到叶子节点的门路上，必须蕴含雷同数目的彩色节点
能够参考一下以下 blog：
Red-Black Trees
绝对于 AVL 均衡树，红黑树对于平衡性的要求没有那么高，因为其对于 色彩 的定义，任意节点左右子树的高度差在一倍之内（最长门路为节点红黑相间，最短门路为节点全黑），因而频繁插入和删除节点时，触发均衡调整的次数更少，均衡调整的过程也更易收敛。
而 c ++ stl 中的 map 应用红黑树作为底层实现，对于 map 中的键值，它只有可能比拟大小：如数值、字符串或其它可能反对大小比拟的类就能够。
hash 表
hash 表，其实就是通过肯定的算法：hash 函数将原始数据转为一段固定长度的数值（表这个词其实没有具体意义，hash 的存储形式有很多，如再链表法，如凋谢地址法的数据结构，表只是对于它们的一种抽象称说）。
具体可见：什么是 hash
这里次要答复一下我本人长期的一个误区：
即之前我始终认为 hash 只实用于 key-value 这样的数据，并且认为 hash 表中只存储 value，那么依据 key 的 hash 值寻找数据时，存在 hash 抵触的话，就没法晓得以后 hash 值对应的 value 数据到底哪个是对应于 key 的。
其实，hash 也能够对于不是 key-value 这样的数据进行存储，比方就是一系列大量的数值或字符串，咱们能够应用 hash 算法，而不是简略的数组顺序存储，为的是放慢查找速度；并且对于 key-value 这样的数据，其实 hash 表中所存储的不是只有 value，而是 key-value 这个键值对都存储了，这样在有 hash 抵触的状况下就能依据 key 值找到真正对应的 value。
