C++map与unordered_map（红黑树VS哈希表）

相同点：键值对关联容器、无重复元素。

内部实现机理不同

• map： 内部实现红黑树
  有序性，红黑树自动排序。
  时间复杂度log(n) 查找、删除、插入

map底层为什么用红黑树实现？
红黑树在查找，插入删除的性能都是O(logn)，且性能稳定
AVL 树是高度平衡的，频繁的插入和删除，会引起频繁的rebalance，导致效率下降；红黑树不是高度平衡的，算是一种折中，插入最多两次旋转，删除最多三次旋转。

红黑树特点：
定义：RB-tree是一个需满足以下规则的二叉搜索树
1.每个结点不是红色就是黑色
2.根结点为黑色
3.每个叶结点（空结点）是黑色的
4.每个红色结点的两个子结点都是黑色的
5.从任一节点到其每个叶子结点的所有路径都包含相同数目的黑色节点。

为什么红黑树是一种好的搜索树？

一棵内部有n个结点的红黑树的高度至多为2∗logn（性质4）。这保证了红黑树任意操作的复杂度都是O(logn)。
基本操作：左旋，右旋，重新着色

目的：红黑树在插入，删除过程中可能会破坏原本的平衡条件导致不满足红黑树的性质，这时候一般情况下要通过左旋、右旋和重新着色这个三个操作来使红黑树重新满足平衡化条件。

• unordered_map:内部实现哈希表
  无序
  查找时间O(1)
  内存占用比较高
  查询性能取决于散列函数、处理冲突的方法、以及填装因子（可以理解为元素在表中的密度）

哈希函数：
直接寻址、随机数、除数留余、

处理冲突的方法：
开放寻址
再散列法
链地址

skip-list跳表

时间复杂度和红黑树相似 log（n）
底层链表实现。每层一个链表曾与层之间有直连通道