哈希知识点总结：哈希、哈希表、位图、布隆过滤器

哈希

哈希也叫散列，它表示的是“一种映射，关键字和存储位置建立一个关联关系”。

哈希表

关键字和存储位置建立一个关联关系

哈希常用方法

1、直接定址法

关键字和存储位置是一 一对应的关系，可能该数就是地址，也可能是通过某种运算得到该地址

使用场景：关键字范围集中（否则容易空间浪费），数据量较小

2、存留余数法

通常计算方法为：

存储位置 = 该数 % 哈希表.size()

【注】

负数也可以用该种方法确定位置，因为%上的数是size()，而size()的结果是size_t，也就是无符号数，这意味着运算时会发生隐式类型转换，也就是说不用担心得出的位置的下标为负数的情况

在这里，就要扩展一下哈希冲突了

哈希冲突

哈希冲突也叫哈希碰撞，表示的是：不同的值映射到同一位置

上面介绍的“存留余数法”获取存储位置的方法是通过模上一个数，但是我们应该很容易想到，不同的数很可能模到同一位置，如哈希表长度为5，当要存储5这个数据时，将会映射到0这个位置，但是后面如果要存储10这个数据时，我们通过计算，会发现存储位置仍然是0，但这个位置已经有数据了，这就引发了哈希冲突

哈希冲突的解决办法

1、闭散列：开放定址法

顾名思义，“开放定址法”也就是将“地址开放”，也就是说，数据可以占用其他位置，只要该位置还处于开放状态，也就是该位置未存储数据。开放定址法的定址有两种探测方法：

（1）线性探测法

通常是 存储位置 = hahi + i （i >= 1），也就是 存储位置 = 上一次哈希映射的位置 + i （i >= 1），直到找到可以存储的位置

（2）二次探测法

通常是 存储位置 = hahi + i ^ 2

2、开散列

哈希桶 / 拉链法

所谓的拉链，就是用一个链条拉起来，和普通的哈希数组不同，拉链法的哈希数组是一个指针数组，每个元素存的是一个节点的指针

哈希的运用

位图

首先我用一个题目来引入

给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在 这40亿个数中

解决方案： （1）二分查找 缺点：要有序 ----> 排序花时间且数据都要存在数组中 -----> 占内存大 --------> 40亿个数据 = 4,0000,000,000 * 4 byte = 14.9G，但是在普通电脑中，用14.9G的内存存数据是比较困难的，而且是要在连续的空间下，这难上加难 （2）位图 因为该题只需要我们判断一个数是否存在，而是否存在我们可以用0和1两种状态来表示，我们很容易能想到二进制，而计算机中，每个比特位就是一个二进制，而一个字节有32个比特位，因此我们可以用一个字节来表示32个数哪些存在，哪些不存在，显然，这种方法所需空间大小远远小于上面那种方法的大小。

接下来我们就要看位图到底怎么使用

假如我们要用一个字节表示下面这个数组哪些数字存在，哪些数字不存在，我们可以这样子做

❁ x在第几个区？（该图是8个比特位一个区） 区号 = x / 8 ❁ x在该区的第几个位？ 位数 = x % 8

我们得到了x在哪个区的哪个位后，我们只需要通过位运算就可以得出该数是否存在，存在则该比特位为1，否则为0

接下来将讲解的是位图中最重要的两个操作：set，reset

set操作

该操作是将某数据设置为“存在”，也就是将其对应的比特位设置为1

假如我们需要将j位处理成1，那我们需要注意的是：我们不应该影响其他位

将某位设置，很明显，我们需要进行移位操作，假如我们要将 j 位设置为1，我们只需要：

bits[i] |= (1 << j)

i表示的是x所在的区号，而bits是整个位图

reset操作

该操作是将某数据设置为“不存在”，也就是将其对应的比特位设置为0

假如我们需要将j位处理成0，那我们仍然需要注意的是：我们不应该影响其他位

将某位设置为0，我们只需要：

bits[i] &= (~(1 << j))

【注】

原位 &= (~(1 << j))后，将会被置为0

总结

其实位图就是数组，只是数组的每个元素是一个比特位，这样子一个整型可以表示32个数，大大节省了空间

位图的运用

1、给定100亿个整数，涉及算法找到只出现一次的整数

解答： 仍然和最原始的题目一样，它仍然是判断在不在的问题，只是多加了一个条件：只出现一次 我们可以将不同次数分个类： ❂ 出现 0 次 ❂ 出现 1 次 ❂ 出现两次及以上 位图建立在二进制的基础上，因此我们再用二进制数表示这三种情况： ❂ 出现 0 次 —————— 00 ❂ 出现 1 次 —————— 01 ❂ 出现两次及以上 ————— 10 两个位置的数都是0和1，因此我们可以用位图来表示 由于有两位，所以我们用两个位图来表示即可，再根据次数的变化，分别更新两个位图对应位的数字就好

2、给两个文件，分别由100亿个整数，我们只有1G内存，如何找到两个文件的交集

解答： 该题和上题一样，需要用到两个位图，把两个处理100亿个数据的问题分离出来，就是该文章第一个提的关于位图的问题，也就是我们只需要把两个文件中的数据都对应到自己所属的位图中去就可以了，最后遍历位图，如果两个位图的同一个位置都位1，则表明该数属于两个文件的交集

布隆过滤器

引入

现在我们来思考一个问题：

我们学过哪些可以用来搜索数据的算法或者数据结构，它们有哪些缺点？

答： 1、暴力查找 缺点：数量大了，效率就低 2、排序 + 二分查找 缺点：排序有代价，时间复杂度、空间复杂度，学过位图我们也可以直到，面对数量特别大的情况下，虽然二分查找很快，但是在空间上有问题的话，再快的算法没有空间也进行不起来 3、搜索树（如AVL树、红黑树） 4、哈希 以上讲的所有方法，在数据量特别大的时候将无法进行

我们怎么优化呢？