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

哈希

哈希表

哈希常用方法

1、直接定址法

2、存留余数法

哈希冲突

哈希冲突的解决办法

1、闭散列：开放定址法

（1）线性探测法

（2）二次探测法

2、开散列

哈希桶 / 拉链法

哈希的运用

位图

set操作

reset操作

总结

位图的运用

布隆过滤器

引入

思想讲解

【拓展阅读】

经典问题

1、给两个文件，分别有100亿个字符串，我们只有1G内存，如何找到两个文件的交集？分别给出精确算法和近似算法

近似算法：布隆过滤器

精确算法：哈希切分

2、给一个超过100G的logfile，log文件中存折IP地址，设计算法找到出现次数最多的地址，与上题条件相同，如何找到topK的IP？

哈希

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

哈希表

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

哈希常用方法

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、哈希

以上讲的所有方法，在数据量特别大的时候将无法进行

我们怎么优化呢？🤔🤔🤔

学完了位图，我们可以知道：

整型的数据，判断在不在 ——————> 可以用位图😯🤨😲

现在就提出一个问题，那其他类型的数据呢？

答：这里就要引入布隆过滤器的概念了

思想讲解

整型用位图很好处理，那我们是不是可以将其他的数据结构转化为整型来处理呢？

我将用字符串来举例，如果我们将字符串的ASCII的和作为一个key，我们就可以映射到特定的位置了，假如：

其实这种记录方法是可能会出错的，这里就需要大家思考一个问题：判断在的情况是准确的呢？还是不在的情况是准确的呢？🤨😣🧐

解答：

判断不在的情况是准确的

因为判断结果并一定准确，因此：布隆过滤器用在可以接收误判的情况下

我来举一个能接受误判的例子

我们注册用户时，通常会要求“用户名不能重复”，但是一个软件的用户成千上万，如果每次都去服务器上找某个昵称是否存在，那将非常低效，这个时候，就会在用户层和服务器层之间加一个布隆过滤器

✦ 对于不在的情况，就不需要再去服务器查找了，直接就可以返回 ——————> 判断不存在时是准确的

✦ 对于在的情况，就需要再去服务器查找了，确认后再返回 ——————> 判断存在时是准确的，但是，如果不去服务器查找，也是可以的，因为这种误判存在的情况，并不影响运行结果（它并不会导致昵称重复而出错）-------> 这种情况是接受误判的

因为布隆过滤器是会误判的，因此很多读者会提出下列问题：