BitMap(位图)
BitMap定义
位图（BitMap），即位（Bit）的集合，是一个离散的数组结构，用一个bit位来标记某个元素对应的Value，而Key即是该元素;最基本的情况，使用一个bit表示一个关键字的状态（可标示两种状态0-不存在，1-存在），也可以使用2bit（表示4种状态），3bit（表示8种状态）需要根据业务场景实现。
BitMap 数据结构
数据结构：byte[]，一个byte 8 bit,使用bit为单位来存储数据，可以在空间和时间双重维度提高效率。
注：也可以是 int[],long[],数据结构,分别表示32bit,64bit
一个int 4个字节 32 bit，使用 BitMap(byte[]) 一个bit 表示一个int 空间缩小32倍。
如：在Java里面一个int类型占4个字节，要对于20亿个int数据进行处理，20亿*4/1024/1024/1024≈7.5G左右，需要将尽8G的内存;BitMap(byte[])处理需要20亿/8/1024/1024/1024≈0.232G,内存不到0.5G,查询某个数据时间复杂度是o(n),校验数据时间复杂度o(1)
数组:[7,9,11,1,3,5]，存储如下图
注:byte[] 下标 n/8 == n >>> 3 即向右位移3位；byte[]值域 1<< n%8 = ( n & 0x07) 即取模向左位移
BitMap 应用场景
1.多个超大文件取交集(数字文件)
2.从海量电话号码中，统计不同号码的个数
3.统计日活，访问量，如 redis.setbit('YYYY-MM-DD',Id,1);
4.BitMap处理大量数字型数据的排序、查询、去重
5.BitMap扩展——Bloom Filter(布隆过滤器)过滤数据(id)
BitMap 优缺点
优点：
1.运算效率高，不需要进行比较和移位；
2.占用内存少，比如: 20亿/8/1024/1024/1024≈0.232G
3.高效排序，去重，校验o(1)，查询o(n)
4.可删除(存储数值型数据)
缺点：
1.所有的数据不能重复。即不可对重复的数据进行排序和查找。
2.只有当数据比较密集时才有优势
3.数据碰撞。比如将字符串hash映射到 BitMap 的时候会有碰撞的问题，那就可以考虑用 Bloom Filter 来解决，Bloom Filter 使用多个 Hash 函数来减少冲突的概率。
4.数据稀疏。比如要存入(9,55555555,99999999)这三个数据，需要建立一个 99999999/8+1 长度的 BitMap ，但是实际上只存了3个数据，这时候就会很大的空间浪费（少量数据不建议使用）；可以通过引入 Roaring BitMap 来解决。
BitMap 手动实现源码逻辑
本次底层是数据结构使用byte[],实现，也可以使用 int[],long[]数据结果，注意初始化数组大小，防止内存不够
| /** * java运算符 与（&）、非（~）、或（|）、异或（^） * BitMap 数据存储约 160 亿 * 存储方式为离散数组方式,建议大量连续数据使用 * @author ysf * */ public class BitMap { private static final int MAXSIZE = Integer.MAX_VALUE-Short.MAX_VALUE; private byte[] bits; private long count=0; public BitMap() { bits = new byte[Integer.MAX_VALUE/2]; } public BitMap(long maxNum) { long maxSize = (maxNum>>>3)+1; if(maxSize > Long.valueOf(MAXSIZE)){ bits = new byte[MAXSIZE]; }else{ bits = new byte[(int)maxSize]; } } public BitMap(int count) { bits = new byte[count]; } /** * 添加数据元素,每一bit标识一个数据（0-不存在，1-存在） * @param i */ public void add(long i){ // 取模 int r = (int)(i>>3); // 取余 int c = (int)(i & 0x07); // | 或运算 只要一个为1，即为1 if(contains(i)){ return; } bits[r] |= (1 << c); count++; } /** * 验证数据是否存在 * @param i * @return */ public boolean contains(long i){ // 取模 int r = (int) (i>>3); // 取余 int c = (int)(i & 0x07); // & 与运算 两个都为1，即为1 if (((bits[r] >>> c) & 1) == 1) { return true; } return false; } /** * 移除数据 * @param i */ public void remove(long i){ // 取模 int r = (int) (i>>3); // 取余 int c = (int)(i & 0x07); if(!contains(i)){ return; } bits[r] &= ~(1 << c); count--; } /** * 获取数据记录总数 bit * @return */ public long getCount(){ return count; } /** * 获取下标元素数据，因为离散型数组存储,需要遍历全部数据 * @param subscript * @return long */ public long getNum(long subscript){ long size = (long)bits.length<<3; long sub = 0; for(long i= 0;i < size;i++){ if(contains(i)){ if(sub == subscript){ return i; } sub++; } } return 0; } } |
BitMap Bloom Filter扩展
注：布隆过滤器是以BitMap基本原理实现的扩展
布隆过滤器是一个含有 m 个元素的位数组（元素为0或1），每一位初始为0;并含有 k 个独立的哈希函数 h1, h2,..., hk 。
需要将集合中的元素加入到布隆过滤器中，依次计算h1(x), h2(x),...,hk(x)，其计算结果填充对应数组的位置，并将其全部置1。一个位置可以被多次置1，但只有一次有效。
当查询某个元素是否在集合中时，计算这 k 个哈希函数，只有当其计算结果全部为1时，则认为可能存在；只要有1个计算结果为0时，则必不存在。
注:布隆过滤器存在假阳性的可能，即当所有哈希值都为1时，该元素也可能不在集合内，但该算法认为在里面。假阳性出现的概率被哈希函数的数量、位数组大小、以及集合元素等因素决定
BitMap Bloom Filter 优缺点与BitMap大致一样
- 优点：
- 空间效率高，所占空间小。
- 查询时间短。
- 自带去重
- 缺点：
- 元素添加到集合中后，不能被删除。
- 有一定的误判率
布谷鸟过滤器与布隆过滤器比较
- 支持动态删除项；
- 更好的查找性能；
- 对于需要低假阳性率的应用程序(ϵ<3%)有更好的空间利用率
BitMap Bloom Filter 使用场景
- 大量数据中判断某个数据是否存在
- 解决缓存穿透
- 爬虫url/ 邮箱等系统的过滤
注：Bloom Filtet 实现请参考google,hutool
<dependency>
<groupId>com.google</groupId>
<artifactId>guava</artifactId>
<version>28.0-jre</version>
</dependency>
<dependency>
<groupId>cn.hutool</groupId>
<artifactId>hutool-all</artifactId>
<version>4.1.12</version>
</dependency>