大量数据去重bitMap位图解决方案

数据去重bitMap位图解决方案

一个32g的内存操作系统，在20亿个整数，找出某个数x是否存在其中

代码语言：javascript复制

 - 方式一:假设是java int占4个字节，1个字节=8位(1byte=8bit)一个int 32*20亿 个bit 约等于7g

 - 方式二：不存储具体数据，而存储是否存在，如果存在则打上标签，采用bit存储20亿个数就是20亿位，空间就是0.2g。

什么是Bitmap Bit-map就是用一个bit位来标记某个元素对应的Value（若元素存在bit位置为1，不存在则置为0）。可创建一个整型数组（如byte数组，int数组，long数组）来表示

Bitmap原理在Java中，数据类型int占4字节，4字节=32位（1 byte = 8 bit）数据类型byte占1字节，1字节=8位

用byte数组来表示集合 {1,2,4,6}，byte数组一个元素占一个字节，一个字节占8位
计算机内存分配的最小单位是字节，也就是8位，那如果要表示集合{1,2,4,6,12,13,15},需要在byte数组，增加一个元素，即增加8位的数据来表示

需求案例方式二解答

每个int类型可标识32个整数，存储20亿个元素需要20亿个比特位，20亿/8/1024/1024 约上200多MB，省32倍空间

代码语言：javascript复制

需要申请的数组大小
array[0]:可表示0~31
array[1]:可表示32~63
array[2]可表示64~95
…
总的数组长度为20亿/32  1

如何确定位置（给定任意整数M，那么M/32就得到下标，M2就知道它在此下标的哪个位置）

代码语言：javascript复制

比如元素存储 80，确定所在数组的bit位置
1、数组index索引  80/32 = 2.5，即第3个数组的位置 arr[2]
2、比特位index索引 802 = 16，索引下标为16的比特位，把比特位设置为1，即arr[2][16]

注意

位图适合对【数值类型】的海量数据进行查询统计、排序、去重和对两个集合做交集、并集运算
bitmap在数据连续的时候，非常节省空间，但是在数据稀疏的时候，会有极大的浪费

缺点

数据碰撞：
- 字符串映射到 bitmap会有碰撞问题，即可能映射到同个位置，即hash碰撞
稀疏数据
- 不连续的数据容易浪费空间，比如存入1和88两个数，需要构建长度89的数组
- 表示索引从1到88，所以需要构建一个长度为89的数组，存放1到88的元素，但实际只存储2个数字
- 如果用户的ID的数据类型是int32的话，那么最大值是2^32，需要用512MB的字节的位图来表示
  - 2^32bit=4294967296 比特(bit)=512 兆字节(MB)
  - 如果只往bitmap存储一个最大值，那边需要申请512 兆字节(MB)，大大浪费空间

业务应用：日活/月活UV统计、签到统计、用户点赞，用户签到，访问计数，在线用户数等

编码实现1亿个数据找不存在的随机数

题目需求
有1千万个随机数，随机数的范围在1到1亿之间，将1到1亿之间没有在随机数中的数求出来
前提条件：使用java现有数据结构或自定义数据结构，要求高效和省空间

位图在java里面的实现BitSet类

是一个实现按需增长的位向量，位Set的每一个位置都有一个boolean值，默认初始值都是false

底层实现是使用long数组作为内部存储结构的，所以BitSet的大小为long类型大小(64位)的整数倍

如果指定了bitset的初始化大小，会规整到一个大于或者等于这个数字的64的整倍数（内存对齐）

比如64位，bitset的大小是1个long，而65位时，bitset大小是2个long，即128位

主要API

代码语言：javascript复制

void and(BitSet set) 对此目标位 set 和参数位 set 执行逻辑与操作。

void or(BitSet set) 对此目标位集执行逻辑或操作

void clear() 将此 BitSet 中的所有位设置为 false

void clear(int bitIndex)：将指定索引处的位设置为 false

void set(int index) 将指定索引处的位设置为 true

boolean get(int index) 返回指定索引处的位值

int size()：返回此 BitSet 中的位数（按逻辑大小）【表示位值时实际使用空间的位数，值是64的整数倍】

int length() 返回此 BitSet 的"逻辑大小",BitSet 中最高设置位的索引加 1

int cardinality() 返回此 BitSet 中设置为 true 的位数

API测试

代码语言：javascript复制

 public static void testBitSet(){
        BitSet bitSet = new BitSet();
        bitSet.set(0);
        bitSet.set(66);
        
        System.out.println(bitSet.size());   // 128
        System.out.println(bitSet.length());  // 67
        System.out.println(bitSet.cardinality()); // 2
        System.out.println("====="); 
        System.out.println(bitSet.get(0));  // true
        System.out.println(bitSet.get(1));  // false
}

解答思路

海量数据 里面查找是否存在，排序，交集，并集等，这类题目基本就是使用位图解决

这类题目一般有两个面试形式

方式一口述问答形式
- 给定X亿个不重复的 int的整数，再给一个数，如何快速判断这个数是否在那X亿个数当中
- 解法：遍历X亿个数字，映射到BitMap中，对于给出的数，直接判断指定的位上存在不存在即可

方式二上机编码形式

代码语言：javascript复制

public class BitSetTest { public static void main(String[] args) { // BitSet bitSet = new BitSet(); // bitSet.set(0); // bitSet.set(66); // System.out.println(bitSet.size()); // System.out.println(bitSet.length()); // System.out.println(bitSet.cardinality()); // System.out.println(bitSet.get(0)); // System.out.println(bitSet.get(1)); testBitSetMap(); }

代码语言：javascript复制

public static void  testBitSetMap(){
    //范围
    int range=100000000;
    //个数
    int total=10000000;
    //普通
    ArrayList<Object> list = new ArrayList<>();
    //声明一个位图
    BitSet bitSet = new BitSet(range);
    //产生随机数
    for (int i = 0; i < total; i  ) {
        int random = (int) (Math.random() * range);
        bitSet.set(random);
        list.add(random);
    }
    System.out.println("产生的随机数:" list);
    System.out.println("bitSet是一的个数:" bitSet.cardinality());
    System.out.println("bitSet的大小:" bitSet.size());
    System.out.println("bitSet最高位加1 length:" bitSet.length());
    //遍历bitst,没有出现的打印出来
    for (int i = 0; i <range; i  ) {
        if(!bitSet.get(i)) {
            System.out.print(i "");
        }
    }
}

} ```

限定优惠劵业务解决方案-Redis7的BitMap应用

简介：限定优惠劵业务解决方案-Redis的BitMap应用

需求背景

互联网项目里多数离不开优惠劵，门槛优惠劵比较多
现在有一个B2C电商平台，总用户量10亿，日活用户5千万
每天都会发放几十到上百种不同类型的优惠劵，每类活动优惠劵领劵率到达20% （即1千万用户）
现在发一个门槛优惠劵，一个用户只能领取一张，禁止重复领取，（user_id是64位的Long类型）
针对”禁止重复领劵“，这个需求说下你的设计和思路

题目条件

用户量大，优惠劵类型多，领劵率高，日活高也说明存在高并发

老王

特别容易，新建一个coupon表，进行分库分表处理
领过的用户把user_id插入数据库表中，下次如果再次领取的查询是否重复领取
分析
- 分库分表可以解决海量数据查询和存储问题
- 但存在高并发场景，频繁插入查询数据库不行，严重影响性能

老帆

存在高并发场景，频繁插入查询数据库不行，那可以结合Redis，进行判断

代码语言：javascript复制

docker部署redis7

#部署
docker run -itd --name xdclass-redis1 -p 6379:6379 -v /mydata/redis/data:/data redis:7.0.8 --requirepass 123456

#进入容器内部
docker exec -it 容器id /bin/bash

#客户端连接
./redis-cli

#授权
auth 123456

使用Redis的Set集合存储领取过的用户user_id，每个优惠劵创建一个set集合
领过的用户把user_id加入set集合中，下次如果再次领取的查询是否重复领取
分析
- Redis存储可以，解决了高并发场景避免了频繁查询数据库
- 但使用Redis的Set数据结构存储，存在内存空间问题
- 假如一个优惠劵有1千万用户领取，每个用户id占用空间64位
- 需要存储空间大小 64bit * 1千万 = 6.4亿bit = 76MB，空间占据比较多

冰冰

存在高并发场景，频繁插入查询数据库不行，那可以结合Redis，进行判断

但数据结构应该采用bitmap数据结构，每个用户id占用空间只占用1位

领过的用户把user_id加入bitmap中，下次如果再次领取的查询是否重复领取

Redis的bitmap

代码语言：javascript复制

Redis中提供的BitMap命令：setbit,getbit,bitcount

领劵：setbit coupon-id  user-uid 1
  例子：setbit coupon-id:876 8888 1

已经领券判断：getbit  coupon-id  user-uid
  例子：getbit coupon-id:876 8888
  如果未领取状态是0，如果已领就是1
  
统计该优惠券有多少个用户领取
  bitcount  coupon-id:876
 返回值为该key值中1的个数

分析

假如一个优惠劵有1千万用户领取，每个用户id占用空间1位
需要存储空间大小 1bit * 1亿 = 1亿bit = 11.9MB，对比前面方案，省了7倍空间
- 为啥是1亿，因为用户总量有1亿个，用户id顺序递增，最大到1亿的值，如果id值更大则需要更多空间

注意

但假如该网站每天的独立访问用户很少，例如只有10万，那这时候使用Bitmaps就不太合适，因为基本上大部分位都是0
Set存储使用的空间：64位 * 100000 = 800KB
BitMap存储使用的空间：1bit * 1亿 = 1亿bit = 11.9MB

进阶版哈希表BloomFilter

简介：进阶版哈希表BloomFilter

背景需求
- 海量数据去重需求解决方案
  - 如果用户的ID的数值类型是32位的话，如果有最大值是2^32，需要用512MB空间的【位图来表示】
    - 2^32bit=4294967296 比特(bit)=512 MB
  - 如果用户的ID的数值类型是64位的话，如果有最大值是2^64，需要用2048PB的位图来表示，硬件支撑不了
    - 2^64bit=2^61 Byte= 2048 PB
  - 所以Bitmap位图出现的问题
    - 好处：空间复杂度不随原始集合内元素的个数增加而增加
    - 坏处：空间复杂度随集合内【最大元素】增大而线性增大
什么是布隆过滤器
- 1970年由布隆提出的一种空间效率很高的概率型数据结构，它可以用于检索一个元素是否在一个集合中
- 由只存0或1的位数组和多个hash算法, 进行判断数据【一定不存在或者可能存在的算法】
- 如果这些bit数组 有任何一个0，则被判定的元素一定不在; 如果都是1则被检元素很可能在
- 对比bitmap位图，布隆过滤器适合更多类型元素，通过hash值转换
- 原理
  - 将元素添加到一个bitmap数组中，每个散列函数将元素映射到bitmap数组中的一个位置
  - 如果该位置已经被占用，则将该位置置为1，否则置为0
  - 当要查询一个元素是否存在时，只需要计算该元素的散列值，并检查bitmap数组中对应的位置是否已经被置为1
  - 如果都是1，则该元素可能存在，否则肯定不存在。
  - 优点
    - 占用空间小，查询速度快，空间效率和查询时间都远远超过一般的算法
  - 缺点
    - 有一定的误识别率，有一定的误识别率，即某个元素可能存在，但实际上并不存在。
    - 删除困难，因为无法确定某个位置是由哪个元素映射而来的
- 记住结论：不存在的一定不存在，存在的不一定存在
注意点
- 布隆过滤器存在误判率，数组越小，所占的空间越小，误判率越高；如果要降低误判率，则数组越长，但所占空间越大
- 最大限度的避免误差, 选取的位数组应尽量大, hash函数的个数尽量多, 但空间占用的浪费和性能的下降
- 业务选择的时候，需要误判率与bit数组长度和hash函数数量的平衡
- 布隆过滤器不能直接删除元素，因为所属的bit可能多个元素有使用
- 如果要删除则需要重新生成布隆过滤器，或者把布隆过滤器改造成带引用计数的方式

爬虫URL去重实战-SpringBoot3.0 Guava布隆过滤器

前置环境准备

本地 JDK17安装（SpringBoot3.0要求JDK17）

项目开发

快速创建 https://start.spring.io/

依赖包引入

代码语言：javascript复制

<dependencies>
    <dependency>
      <groupId>org.springframework.boot</groupId>
      <artifactId>spring-boot-starter-web</artifactId>
    </dependency>

    <dependency>
      <groupId>org.springframework.boot</groupId>
      <artifactId>spring-boot-starter-test</artifactId>
      <scope>test</scope>
    </dependency>


    <dependency>
      <groupId>org.apache.commons</groupId>
      <artifactId>commons-lang3</artifactId>
      <version>3.12.0</version>
    </dependency>

    <dependency>
      <groupId>com.google.guava</groupId>
      <artifactId>guava</artifactId>
      <version>31.1-jre</version>
    </dependency>

  </dependencies>

数据准备 (随机生成500万URL)

代码语言：javascript复制

    @Test
    public void testGeneUrl() {
        try{
            File file = new File("/Users/xdclass/Desktop/dat.txt");
            if (!file.exists()) {
                file.createNewFile(); // 创建新文件,有同名的文件的话直接覆盖
            }
            FileOutputStream fos = new FileOutputStream(file, true);
            OutputStreamWriter osw = new OutputStreamWriter(fos);
            BufferedWriter bw = new BufferedWriter(osw);
            StringBuilder builder = new StringBuilder();
            for (int i = 0; i < 5000000; i  ) {
                String name = RandomStringUtils.randomAlphabetic(5);
                String fileName = "https://www."   name   ".com"   i   "n";
                builder.append(fileName);
            }
            bw.write(String.valueOf(builder));
            bw.newLine();
            bw.flush();
            bw.close();
            osw.close();
            fos.close();
        } catch (FileNotFoundException e1) {
            e1.printStackTrace();
        } catch (IOException e2) {
            e2.printStackTrace();
        }
    }

Guava包布隆过滤器介绍

代码语言：javascript复制

//参数一： 指定布隆过滤器中存的是什么类型的数据，有 IntegerFunnel，LongFunnel，StringCharsetFunnel
//参数二： 预期需要存储的数据量
//参数三： 误判率，默认是 0.03
BloomFilter.create(Funnels.stringFunnel(Charset.forName("UTF-8")), 5000000, 0.01);

核心代码编写

代码语言：javascript复制

  @Bean
  public Set set() throws IOException {
    Set<String> set = new LinkedHashSet<>();
    FileInputStream inputStream = new FileInputStream(new File("/Users/xdclass/Desktop/dat.txt"));
    InputStreamReader streamReader = new InputStreamReader(inputStream);
    BufferedReader reader = new BufferedReader(streamReader);
    String line = null;
    while (true) {
      line = reader.readLine();
      if (line != null) {
        set.add(line);
      } else {
        break;
      }
    }
    inputStream.close();
    return set;
  }


  @Bean
  public BloomFilter bloomFilter() throws IOException {
    BloomFilter bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charset.forName("UTF-8")), 5000000, 0.01);
    FileInputStream inputStream = new FileInputStream(new File("/Users/xdclass/Desktop/dat.txt"));
    InputStreamReader streamReader = new InputStreamReader(inputStream);
    BufferedReader reader = new BufferedReader(streamReader);
    String line = null;
    while (true) {
      line = reader.readLine();
      if (line != null) {
        bloomFilter.put(line);
      } else {
        break;
      }
    }
    inputStream.close();
    return bloomFilter;
  }
  
  
@RestController
@RequestMapping("/api")
public class FilterController {
    @Autowired
    private BloomFilter<String> bloomFilter;

    @Autowired
    private Set set;

    @GetMapping("/bloom")
    public String list() throws IOException {

        //判断是否包含这个内容
        if (bloomFilter.mightContain("https://www.dhVrX.com5")) {
            return "命中了";
        } else {
            return "没命中";
        }
    }

    @GetMapping("/set")
    public String set() {
        if (set.contains("httssps://www.shncb.com999663")) {
            return "命中了";
        } else {
            return "没命中";
        }
    }

}

案例测试（调整JVM参数分配内存：-Xms100m -Xmx100m）
- 使用Set集合
- 使用布隆过滤器

存储 bitmap 解决方案数据数组

0 人点赞