hash 的应用

散列表

根据key计算key在表中的位置的数据结构；是key和其所在存储地址的映射关系； 注意：散列表的节点中 kv是存储在一起的

struct node {
    void *key;
    void *val;
    struct node *next;
}

与平衡二叉树相比

通过比较，结构有序，提升搜索效率
key与节点存储位置的映射关系

组成

hash函数
    映射函数Hash(key)=addr,hash 函数可能会把两个或两个以上的不同key映射到同一地址，这种情况称之为冲突（或者hash碰撞）；
数组

选择函数

1. 计算速度快
2. 强随机分布（等概率，均匀地分布在整个地址空间）
3. murmurhash1,murmurhash2,murmurhash3,siphash(redis6.0当中使用，rust等大多数语言选用的hash算法来实现hashmap),cityhash都具备强随机分不行
4. siphash主要解决字符串接近的强随机分布性 role:10001 role:10002

负载因子

数组存储元素的个数/数组长度；用来形容散列表的存储密度；负载因子越小，冲突越小，负载因子越大，冲突越大；需要注意扩容翻倍和缩容所导致的rehash

冲突处理

链表法

引用链表来处理哈希冲突，将冲突元素用链表链接起来，常用处理冲突的方式，但是如果冲突元素较多，该冲突链表过长，这个时候可以将这个链表转化成红黑树，最小堆；
由原来的时间复杂度O（n）转化为红黑树O(log2n),可以采用超过256个节点时候将链表结构转换为红黑树或堆结构。

开放寻址法

将所有元素都存放在哈希表的数组中，不使用额外的数据结构；一般使用线性探查的思路解决

1. 当插入新元素的时候，使用哈希函数在哈希表中定位元素位置
2. 检查数组中该槽位索引是否存在元素，如果为空就插入，否则转为3
3. 在2检测的位置索引加上一定步长后在检查2；加一定的步长可以分为按 i+1，i+2...,i+n i+1^2,1+2^2,...,i+n^2 这两种都会导致同类的hash聚集，也就是近似值它的hash值也近似，形成hash聚集，第一种同类聚集冲突在前，第二种只是将聚集冲突延后；另外可以使用双重哈希解决

在stl 散列表中有 map,set,multimap,multiset 都是红黑树，unordered_map unordered_set unordered_multimap unordered_multiset 都是散列表

布隆过滤器

布隆过滤器通常用于判断某个key一定不存在的场景，同时允许判断存在时有误差的 布隆过滤器是一种概率型数据结构，高效地插入和查询，能确定某个字符串一定不存在和可能存在，另一方面布隆过滤器不存储具体数据，所以占用空间小，查询结果存在误差，但是误差可控，同时不支持删除操作。。

原理

当一个元素加入位图时，通过K个hash函数将这个元素映射到位图的K个点，并把他们位置为1，当检索时，再通过K个hash函数运算检测位图的k个点是否为1，如果有不为1的点，那么认为该key不存在，如果全部为1，则可能存在

为何不支持删除操作？

1. 在位图中每个槽位只有两种状态（0或1）,一个槽位被设置为1状态，但不确定它被设置了多少次，也就是不知道被多少个key哈希映射而来以及是被具体哪个hash函数映射而来。
2. 不存在，只要一个索引位为0，如果都为1，不一定存在