hash 函数
映射函数 Hash(key)=addr ；hash 函数可能会把两个或两个以上的不同 key 映射到同一地址，这种情况称之为冲突（或者 hash 碰撞）
hash的优势
- 计算速度快
- 强随机分布（等概率、均匀地分布在整个地址空间）
- murmurhash1，murmurhash2，murmurhash3，siphash（ redis6.0 当中使用，rust 等大多数语言选用的 hash 算法来实现 hashmap ），cityhash 都具备强随机分布性
- siphash 主要解决字符串接近的强随机分布性
负载因子
- 数组存储元素的个数 / 数组1长度；用来形容散列表的存储密度；负载因子越小，冲突概率越小，负载因子越大，冲突概率越大。
冲突处理
链表法
引用链表来处理哈希冲突；也就是将冲突元素用链表链接起来。
开放寻址法
将所有的元素都存放在哈希表的数组中，不使用额外的数据结构；一般使用线性探查的思路解决。
STL unordered_* 散列表实现
在 STL 中 unordered_map 、 unordered_set 、unordered_multimap 、 unordered_multiset 四兄弟底层实现都是散列表。
布隆过滤器
布隆过滤器是一种概率型数据结构，它的特点是高效地插入和查询，能确定某个字符串一定不存在或者可能存在。
原理
当一个元素加入位图时，通过 k 个 hash 函数将这个元素映射到位图的 k 个点，并把它们置为 1；当检索时，再通过 k 个 hash 函数运算检测位图的 k 点是否都为 1；如果有不为 1 的点，那么认为该 key 不存在；如果全部为 1，则可能存在。
应用场景
布隆过滤器通常用于判断某个 key 一定不存在的场景，同时允许判断存在时有误差的情况；
常见处理场景：① 缓存穿透的解决；② 热 key 限流；