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 限流;