哈希表的构造方法-哈希冲突-布隆过滤器_布隆过滤器哈希冲突

哈希-散列表

散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f,使得每个关键字key对应一个存储位置f(key)

查找时，根据这个确定的对应关系找到给定值key的映射f(key)，若查找集合中存在这个记录，则必定在f(key)的位置上

散列表的查找步骤

1. 存储时：通过散列函数计算记录的散列地址，并按此散列地址存储该记录
2. 查找时：通过同样的散列函数计算记录的散列地址，按地址访问该记录

C++当中的unordered_map以及常见用法

unordered_map
//存在于下面的头文件中，在定义的时候要引用该头文件
#include <unordered_map>
1
2
3

常见的使用函数

    //获取大小
    cout<<mp.size();
    //删除其键值
    mp.erase(3);
    //逆置散列表
    mp.reserve(n);
    //在容器中查找以key键的键值对的个数
    mp.count(3);
	//第一个值为键值--第2个保存的为其对应的值--插入的时候不能够出现键值相同，如果键值相同则无法插入
    mp.insert({20,30});
	//插入一组键值比insert效率高
	mp.emplace(15,10);
1
2
3
4
5
6
7
8
9
10
11
12

构造哈希函数的6中方法

1·直接定址法

优缺点

2·数字分析法

适用情况

3·平方取中法

4·折叠法

5·除留余数法

6·随机数法

哈希冲突

解决哈希冲突的几种方法

1·开放定址法

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-6WkLfHMA-1651850024140)(C:/Users/kexib/AppData/Roaming/Typora/typora-user-images/image-20220506223102162.png)]

2·再散列函数法

3·链地址法

4·公共溢出区法

一致性哈希

为了解决这种服务器出现问题，数据大量移动的这种问题，提出了一致性哈希

哈希偏斜

图中是在服务器部署均衡的情况下，当服务器部署不均衡的时候，大量的数据集中到一个服务器上的时候，我们称其为哈希偏斜

布隆过滤器

海量的数据去重

设计

一组非常长的二进制矢量+一组哈希函数

在初始状态时，对于长度为 m 的位数组，它的所有位都被置为0，如下图所示：

当有变量被加入集合时，通过 K 个映射函数将这个变量映射成位图中的 K 个点，把它们置为 1（假定有两个变量都通过 3 个映射函数）

查询某个变量的时候我们只要看看这些点是不是都是 1 就可以大概率知道集合中有没有它了

• 如果这些点有任何一个 0，则被查询变量一定不在；
• 如果都是 1，则被查询变量很可能存在

为什么说是可能存在，而不是一定存在呢？那是因为映射函数本身就是散列函数，散列函数是会有碰撞的。

特点

1. 如果确定一个值不在，则肯定100%不在
2. 如果确定一个值在，则这个值不一定在

优缺点

优点

1. 占用空间小
2. 插入效率非常高
3. 安全，不论过滤器不储存原始数据，只储存特征值

缺点

1. 会发生误判
2. 删除不了数据

使用场景

1. 游客黑名单
2. 邮件黑名单
3. 判断用户是否度过某视频或文章
   优缺点