BitMap


面试题海量数据处理经常出现BitMap,所以记一下笔记

1. BitMap

BitMap也称为位图,其原理和布隆过滤器类似,其基本原理都是使用位数组及其下标来表示某些元素是否存在,其在处理大量数据的排序、查询、去重,以及在用户群做交集和并集运算的时候也有极大的便利

假如我们要将 {5,6,1,10} 进行排序,利用位图思想的话:(这里并不是真实原理,是个假设)

  • 遍历找出或预计最大元素值
  • 然后创建最大元素值大小的位数组(比如上例就创建大小为10的位数组)
  • 最后遍历数据,每遇到一个元素则在对应的位数组置1

其时间复杂度为O(N),比一般的排序算法都快

且空间利用率高,在普通情况下10亿个整数占用空间3.8G,而位图占用120MB左右

2. 实际操作

我们使用 byte[] arr = new byte[max]数组来模拟位数组:

  • 一个 byte占用8bit,那么可以表示 0~7 的数
  • byte[10] 占用80bit,那么可以表示 0~79的数
  • 根据上两条,那么 8这个数是在 byte[1] 里面存放的

那么我们可以总结出:若最大数为N,那么需要创建数组大小为 byte[ N / 8+ 1]

找出某数 n对应的整型数组下标:n / 8 == n >> 3

在具体整型下标中,找出的位下标:n % 8 == n & 0x07

综合起来的Java实现就是

public class BitMap {

    private byte[] data;

    private int capacity;

    public BitMap(int cacapacity){  // 还可以做个扩容机制?
        this.capacity = cacapacity;
        data = new byte[ (cacapacity >> 3) + 1];
    }

    public void add(int num){
        int arrayIndex = num >> 3;  // /8
        int position = num & 0x07;  // %8
        // 左移表示将1向左移动几位,加上小端存储,即可占用对应位了
        data[arrayIndex] |= 1 << position;
    }

    public boolean contain(int num){
        int arrayIndex = num >> 3;
        int position = num & 0x07;
        return ( data[arrayIndex] & (1 << position) ) != 0;
    }

    public void clear(int num){
        int arrayIndex = num >> 3;
        int position = num & 0x07;
        data[arrayIndex] &= ~(1 << position);
    }

    public static void main(String[] args) {
        BitMap bitmap = new BitMap(100);
        bitmap.add(10);

        System.out.println("是否存在10:"+ bitmap.contain(10));

        bitmap.clear(10);
        System.out.println("是否存在10:" + bitmap.contain(10));
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Tomcat的设置

    因为logging默认使用utf-8,而我们的windows的日志输出控制台使用系统的GB2312,所以去conf中修改logging的配置编码为GB2312即...

    晚上没宵夜
  • SpringSecurity

    Spring Security是一个功能强大且高度可定制的身份认证和访问控制框架,它是用于保护基于Spring的应用程序的实际标准。Spring Securit...

    晚上没宵夜
  • 反码补码和位运算

    三者是计算机存储数据的不同形式,计算机用补码存储数据。而且计算机利用这三者可以用加法实现减法

    晚上没宵夜
  • 07.HTML实例

    Java帮帮
  • 非CS科班算法岗(规控方向)面经

    先说一下背景,top2本博控制专业,一年前没有任何数据结构和算法系统知识,一年内系统的选了数据结构和算法课,同时先后经历了春招实习和秋招校招的洗礼,也完成了自己...

    AI算法与图像处理
  • wsl设置默认账户为root(ubuntu18.04)

    Happyjava
  • Python 中argparse模块的使用

    如果脚本很简单或临时使用,没有多个复杂的参数选项,可以直接利用sys.argv将脚本后的参数依次读取(读进来的默认是字符串格式)。

    用户1332428
  • Python 中argparse模块的使用

    如果脚本很简单或临时使用,没有多个复杂的参数选项,可以直接利用sys.argv将脚本后的参数依次读取(读进来的默认是字符串格式)。

    致Great
  • uni-app 组件

    view scroll-view swiper text rich-text progress

    达达前端
  • 【CodeForces 699D】Fix a Tree

    dfs找出联通块个数cnt,当形成环时,令指向已访问过节点的节点变成指向-1,即做一个标记。把它作为该联通图的根。

    饶文津

扫码关注云+社区

领取腾讯云代金券