一、问题引入
先来思考这样一个问题：假如给你20亿个数字，范围大小是 1- 20亿，需要你把这些数字存储起来，然后再随机给定一个数字，判断其是否存在这20亿个数字中， 你怎么解决。
首先如果不考虑其个数多少的话，我们首先想到的可能就是使用一个set集合，用来存储数字集合，然后直接判断数字是否存在，因为其底层使用了hash的数据结构，判断给定数字是否存在也是O(1) 的时间复杂度。但是当这个数字来到10亿，乃至更大的时候，如果还是用set集合，可能会极大得浪费我们的存储空间，并且可能会引发OOM（我们可以大概估算一下，java中，一个int类型的数字是4个字节，取值范围：-2147483648~+2147483647。那么这20亿个数据如果我们用int类型表示，那么占用内存就是 4 * 20亿 = 80亿字节，约等于8个G）。这个时候，我们需要怎么解决这个问题呢？
我们主要解决的是占用内存过大的这个问题，那我们想，有没有比字节更小的单位呢，没错了，就是bit 位。 我们知道，计算机中，最原始都是使用二进制表示，int类型有32bit位，如果我们用每个bit位表示一个数字，那么一个int类型就能够存储32个数字，而且题干中刚好只要求我们能够判断目标数字是否存在，那我们只需要对应的bit位上存储 1 或者 0，用来表示存在或者不存在。这么算下来，原本 约8个G的存储 / 32,也就是200多M，就可以解决这个问题。
二、思路归纳
为了方便计算，我们暂且将 数字缩小化便于理解。
比如给定的数字集合，最大是130。现在我们向集合中添加128，129这两个数字，具体应该怎么添加呢？
1、首先要确定这个集合怎么表示，我们可以使用int类型的数组（当然你也可以使用Long类型的，这里只是举例），因为int类型占用4个字节，32位，所以一个int可以表示32个数字，也就是int[0] 可以表示0-31，int[1]表示32-63，依次类推。
2、有了数组，那么我们就要确定给定的数字位于数组的下标位置。我们可以用 （130 / 32 ）+1 = 5 来表示下标位置。为什么数组长度需要+1呢，因为4个长度的int数组只能表示0-127，所以多出来的几个数字，只能数组长度再加一。
3、有了下标，还需要找到数组下标中的bit位置。128 % 32 = 0 来表示在第几个bit位。
向int数组中添加128，
向int数组中添加129，
有了如上添加数字将对应bit位置置为1的逻辑，接下来给定一个数字，判断这个数字是否存在于集合内，就只要判断该数字对应的big位上 的值是否等于1 即可。
比如给定100，首先找到数组下标 index = 100 / 32 = 3, num = 100 % 32 = 4, 即只要判断bigmap[2]的第四个bit位上是否等于1，等于1，说明存在，不等于1，则不存在。
三：布隆过滤器
所谓位图，就是使用位这个最小的存储单元来储存，针对于Integer4个字节，根据位的高低来存储不同大小的数字。正常来说，20亿个正整型数字，数组来存，需要20亿的长度，但是如果用位来存，一个Integer占32位，也就是数组中的一个Integer可以表示32个数字，那么就整整缩小了32倍的数组长度。
问题一：
我们想，现在只是针对数字，如果我们把范围扩大到其他类型，如果是字符串呢，那么我们就需要先对目标进行哈希运算，然后再计算其数组下标。
问题二:
同时我们的哈希表（数组）长度总是有限的，如果产生哈希冲突，那么最后判断哈希表中的值，就会不准确。那么怎么解决呢？通过设置多个哈希函数，同时将多个位上的值置为1。当判断一个key所对应的值存不存在时，通过多个哈希函数得到的数组下标所对应的值都为1时，才能确定这个key是存在的，否则不存在。这样当然也可能会存在误判，不过我们可以根据业务场景的容忍度，通过设置哈希表的大小和哈希函数的个数来调整误判的概率。redis中的布隆过滤器也就是这么做的。
java的位图实现：
/**
* @author zhangxiaohu
* @descript int整数位图
* @date 2022-10-12
*/
public class BitMap {
private int[] bitMap;
/**
* java中int 占用4个字节，共32位
* 如果最大数值是 128，那么bigMap 数组的长度就是 4（占用128位），如果用普通的方式存储，最大值是128，那么我们的 数组长度就是128,相比之下，内存空间减少了32倍
* @param range
*/
public BitMap(int range) {
/**
* range >> 5 = range / 32
* 这里为什么要 + 1呢，这是因为，比如最大值是128，数组长度是4，最多只能存储到 0 - 127，所以存储128数组长度要再+1
* 数组长度+1之后，所以range = 128，但是我们可以表示的最大值应该是 128 + 31 = 159
*/
bitMap = new int[(range >> 5) + 1];
}
public void set(Integer number) {
/**
* number >> 5 = number / 32
* 假如number = 128
* index = 4 表示在数据的最后一个位置，也就是bitMap[3]
* num = 0 表示在bitMap[3]上的第0位（bitMap[3] 上有32位），也就是： 00000000 00000000 00000000 00000001
*/
int index = number >> 5;
int num = number % 32;
/**
* 1 << num = 1 * 2的num次幂,保证相应位置上的值无论为0还是1，都变成1
* 这里为什么要用 | 运算呢 , | 或运算：有一个为1，值就为1
* 是因为多次给每个bitMap位置上的32个元素赋值为1时，这32个值不相互影响
* 比如，第一次number=128，bitMap[3] = 00000000 00000000 00000000 00000001
* 第二次number = 130, bitMap[3] 不应该 = 00000000 00000000 00000000 00000100，而是应该 = 00000000 00000000 00000000 00000101
* 所以需要每次赋值时进行或运算
*/
bitMap[index] = bitMap[index] | 1 << num;
}
public boolean exist(Integer number) {
int index = number / 32;
int num = number % 32;
/**
* & 与运算：全部为1，才为1
* 与运算后的结果为 0或者2的num次幂,只要 != 0,就说明这个元素存在
*/
return true == ((bitMap[index] & 1 << num ) != 0) ;
}
}
