专栏首页Spark学习技巧海量数据处理之bitmap

海量数据处理之bitmap

一、概述

本文将讲述Bit-Map算法的相关原理,Bit-Map算法的一些利用场景,例如BitMap解决海量数据寻找重复、判断个别元素是否在海量数据当中等问题.最后说说BitMap的特点已经在各个场景的使用性。

二、Bit-Map算法

先看看这样的一个场景:给一台普通PC,2G内存,要求处理一个包含40亿个不重复并且没有排过序的无符号的int整数,给出一个整数,问如果快速地判断这个整数是否在文件40亿个数据当中?

问题思考:

40亿个int占(40亿*4)/1024/1024/1024 大概为14.9G左右,很明显内存只有2G,放不下,因此不可能将这40亿数据放到内存中计算。要快速的解决这个问题最好的方案就是将数据搁内存了,所以现在的问题就在如何在2G内存空间以内存储着40亿整数。一个int整数在java中是占4个字节的即要32bit位,如果能够用一个bit位来标识一个int整数那么存储空间将大大减少,算一下40亿个int需要的内存空间为40亿/8/1024/1024大概为476.83 mb,这样的话我们完全可以将这40亿个int数放到内存中进行处理。

具体思路:

1个int占4字节即4*8=32位,那么我们只需要申请一个int数组长度为 int tmp[1+N/32]即可存储完这些数据,其中N代表要进行查找的总数,tmp中的每个元素在内存在占32位可以对应表示十进制数0~31,所以可得到BitMap表:

tmp[0]:可表示0~31

tmp[1]:可表示32~63

tmp[2]可表示64~95

.......

那么接下来就看看十进制数如何转换为对应的bit位:

假设这40亿int数据为:6,3,8,32,36,......,那么具体的BitMap表示为:

如何判断int数字在tmp数组的哪个下标,这个其实可以通过直接除以32取整数部分,例如:整数8除以32取整等于0,那么8就在tmp[0]上。另外,我们如何知道了8在tmp[0]中的32个位中的哪个位,这种情况直接mod上32就ok,又如整数8,在tmp[0]中的第8 mod上32等于8,那么整数8就在tmp[0]中的第八个bit位(从右边数起)。

java里面有个实现就是bitset,一个老早就有的工具,具体使用,可以参考如下源码:

import java.util.BitSet;

public class BitSetTest {

    public static void main(String[] args) {
        int [] array = new int [] {1,2,3,22,0,3,63};
        BitSet bitSet  = new BitSet(1);
        System.out.println(bitSet.size());   //64
        bitSet  = new BitSet(65);
        System.out.println(bitSet.size());   //128
        bitSet  = new BitSet(23);
        System.out.println(bitSet.size());   //64

        //将数组内容组bitmap
        for(int i=0;i<array.length;i++)
        {
            bitSet.set(array[i], true);
        }

        System.out.println(bitSet.get(22));
        System.out.println(bitSet.get(60));

        System.out.println("下面开始遍历BitSet:");
        for ( int i = 0; i < bitSet.size(); i++ ){
            System.out.println(bitSet.get(i));
        }
    }

}

当然,这个是使用现成,自己写的话也是很简单,下面有一个简单的实现:

/**
 * 实现BitMap
 *注:这个bitMap的index是从1开始的
 */
public class BitMap {
    private long length;
    private static int[] bitsMap;

    //构造函数中传入数据中的最大值
    public BitMap(long length) {
        this.length = length;
        // 根据长度算出,所需数组大小
        bitsMap = new int[(int) (length >> 5) + ((length & 31) > 0 ? 1 : 0)];
    }

    public int getBit(long index) {
        int intData = bitsMap[(int) ((index - 1) >> 5)];
        int offset = (int) ((index - 1) & 31);
        return intData >> offset & 0x01;
    }


    public void setBit(long index) {
        // 求出该index - 1所在bitMap的下标
        int belowIndex = (int) ((index - 1) >> 5);
        // 求出该值的偏移量(求余)
        int offset = (int) ((index - 1) & 31);
        int inData = bitsMap[belowIndex];
        bitsMap[belowIndex] = inData | (0x01 << offset);
    }
    public static void main(String[] args) {
        BitMap bitMap = new BitMap(32);
        bitMap.setBit(32);
        System.out.println(bitMap.getBit(1));
        System.out.println(bitMap.getBit(32));
    }
}

本文分享自微信公众号 - Spark学习技巧(bigdatatip)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-11-16

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 你注意ArrayList扩容原理了吗

    本文主要是从java 1.6-1.8说一下ArrayList的初始容量大小及扩容的思路,主要是底层是ArrayList在扩容的时候会整个复制导致性能底下,所以在...

    Spark学习技巧
  • 大数据面试题分析

    转自:https://blog.csdn.net/csuwubing/article/details/79259749

    Spark学习技巧
  • Java 性能优化的 45 个细节

    在JAVA程序中,性能问题的大部分原因并不在于JAVA语言,而是程序本身。养成良好的编码习惯非常重要,能够显著地提升程序性能。

    Spark学习技巧
  • 1466: [蓝桥杯2019初赛]等差数列

    数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一部分的数列,只记得其中N 个整数。现在给出这N 个整数,小明想知道包含这N 个整数的最短的等差数...

    可爱见见
  • 洛谷P4424 [HNOI/AHOI2018]寻宝游戏(思维题)

    那么我们把每一列上的数和他之前的操作符分别拿出来看成一些序列,显然这个序列要满足最后一个\(\mid 1\)要在\(\& 0\)之后

    attack
  • Hackerrank GCD Product(莫比乌斯反演)

    attack
  • BZOJ3262: 陌上花开(cdq分治)

    第一行为N,K (1 <= N <= 100,000, 1 <= K <= 200,000 ), 分别表示花的数量和最大属性值。

    attack
  • 2018 团队设计天梯赛题解---华山论剑组

    2018 年度的团队设计天梯赛前几天结束了。但是成绩真的是惨不忍睹。。。毕竟是团队的比赛,如果团队平均水平不高的话,单凭一个人,分再高也很难拉起来(当然,一个人...

    指点
  • LeetCode 3. Longest Substring Without Repeating Characters题目分析

    样例 例如,在"abcabcbb"中,其无重复字符的最长子字符串是"abc",其长度为 3。

    desperate633
  • ZR国庆Round2解题报告

    然后刚T3暴力,刚完还有2h左右。。然后,,这时候我zz的选择去打T2的暴力,然而T2暴力真的不是一般的难写。。

    attack

扫码关注云+社区

领取腾讯云代金券