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。