- 散列是一种用于以常数平均时间执行插入、删除、和查找的技术，通过关键字key，经由哈希函数，映射到值val的存储地址。
- 装载因子：散列表中元素个数 除以 散列表的大小。是表示 Hsah 表中元素的填满的程度，若加载因子越大，则填满的元素越多,这样的好处是：空间利用率高了,但冲突的机会加大了。反之,加载因子越小,填满的元素越少,好处是冲突的机会减小了，但空间浪费多了。
- 散列冲突：两个不同的key映射到了同一个值的时候。
- 素数：只能被1和自身整除的数（如 2 n − 1 2^{n}-1 2n−1或者 2 n + 1 2^{n}+1 2n+1 ）
分离链接(Separate chaining)
如果链表过长，会导致查找效率低下，此时就可以使用红黑树替代链表。
优点：
- 无需为每个桶预留多个槽位
- 可解决任意多次冲突
- 删除操作简单、统一
缺点：
- 指针需要额外空间
- 节点需要动态申请，存在开销
- 空间未必连续分布，容易造成内存碎片
- （一次项的线性）线性探测(Linear probing)
- （添加了一个二次项）二次探查
- 双重哈希(Double hashing)
- 数组 + [链表 / 红黑树]
一般预留的哈希表大小为一个素数空间（大于所要填充的数量），避免哈希冲突。
可以通过设置装填因子(如0.75)，从而保持着一定的预留空间，当达到装填因子的填充比例时，便动态调整数组的大小（类比与vector的实现），降低哈希冲突概率。
STL无序容器实现原理:
采用的开链法，其中，Pi 表示存储的各个键值对。
可以看到，当使用无序容器存储键值对时，会先申请一整块连续的存储空间，但此空间并不用来直接存储键值对，而是存储各个链表的头指针，各键值对真正的存储位置是各个链表的节点。
注意，STL 标准库通常选用 vector 容器存储各个链表的头指针。
不仅如此，在 C++ STL 标准库中，将图中的各个链表称为桶（bucket），每个桶都有自己的编号（从 0 开始）。当有新键值对存储到无序容器中时，整个存储过程分为如下几步：
- 将该键值对中键的值带入设计好的哈希函数，会得到一个哈希值（一个整数，用 H 表示）；
- 将 H 和无序容器拥有桶的数量 n 做整除取余运算（即 H % n），该结果即表示应将此键值对存储到的桶的编号；
- 建立一个新节点存储此键值对，同时将该节点链接到相应编号的桶上。
动画：什么是散列表？
C++ STL无序容器底层实现原理（深度剖析）
