BitMap算法

栏目: 编程工具 · 发布时间: 5年前

内容简介:在某公众号中看到一个比较有意思的题目,记录一下顺便学习下bitmap算法。这道题的解题方法是采用bitmap:1个字节占8位,可以表示8个整数是否出现的情况(出现则对应的位置1,否则为0),那么表示40亿个整数的情况需要40亿/8=5亿,约62.5M的空间.空间复杂度是O(n)+O(1);一个int类型的数字占四个字节,一个字节占8位。即一个int数字占32位,如果用每一位表示一个数字的话,一个int类型的整数就可以表示32个整数。bitmap算法就是利用这种思想处理大量的数据的排序和查询。

在某公众号中看到一个比较有意思的题目,记录一下顺便学习下bitmap算法。

给40亿个不重复的unsigned int的整数,没排过序的,然后再给一个数,如何快速判断这个数是否在那40亿个数当中?

这道题的解题方法是采用bitmap:1个字节占8位,可以表示8个整数是否出现的情况(出现则对应的位置1,否则为0),那么表示40亿个整数的情况需要40亿/8=5亿,约62.5M的空间.空间复杂度是O(n)+O(1);

BitMap

算法思想

一个int类型的数字占四个字节,一个字节占8位。即一个int数字占32位,如果用每一位表示一个数字的话,一个int类型的整数就可以表示32个整数。bitmap算法就是利用这种思想处理大量的数据的 排序 和查询。

下面用一组样例来演示一下bitmap的使用:

对数列{1,7,2,5,4}进行排序

我们用一个整数的二进制形式来“存储这几个整数”

BitMap算法

遍历数列,将数列中的数字的对应位置为1

BitMap算法

按顺序输出该二进制中值为1的下标,即为排序后的数列。

bitmap的思想比较简单,最主要的是十进制数字与二进制位之间的映射。

map映射表

假设需要排序或者查找的数据中的最大值不超过MAX = 100000000(一亿),我们需要申请的内存空间大小为int[1+MAX/32]。

对应的map映射表为:
a[0] ---------> 0-31
a[1] ---------> 32-63 
a[2] ---------> 64-95 
a[3] ---------> 96-127

将一个整数n映射到map映射表中,首先要确定n在map映射表中的index。我们用int类型的数组a作为map映射表,n/32就可以求出n在a数组中的index。然后再通过n%32求出n所在的位就可以了。

通过上面的分析,可得出一下式子:

a[n>>5] |= 1<<(n & 0x1F)

n>>5 相当于 n/32(求得n在a数组中的index)

n & 0x1F 相当于 n%32 (求得n在a[index]的第几位)

|= 相当于将所在位置为1

代码实现:

public class BitMap {

    private static final int MAX = 10000000;

    private int[] a = new int[MAX/32 + 1];


    // 将第i位置为0
    public void clean(int i) {        
    	a[i>>5] &= ~(1<<(i & 0x1F)); 
    }
    
    // 将所在的bit位为1
    public void add(int n){
        //row = n / 32 求十进制数在数组a中的下标
        int index = n>>5;
        //相当于 n % 32 求十进制数在数组a[i]中的下标
        a[index] |= 1<<(n & 0x1F);
    }

    // 判断所在的bit为是否为1
    public int exits(int n){
        int index = n >> 5;
        return (a[index] & ( 1 << (n & 0x1F)));
    }

    public static void main(String[] args){
        int num[] = {1,5,30,32,64,56,159,120,21,17,35,45};
        BitMap bitMap = new BitMap();
        for(int i=0;i<num.length;i++){
            bitMap.add(num[i]);
        }

        int temp = 121;
        if(bitMap.exits(temp) != 0){
            System.out.println("temp: " + temp + " has already exists");
        } else {
        	System.err.println("temp: " + temp + " has not exists");
        }
    }
}

以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Growth Hack 這樣做

Growth Hack 這樣做

Xdite / PCuSER電腦人文化 / 2016-5-7 / 300.00台幣

◎具體教你在預算有限的情況之下,把成長做出來的可行與必要方法! ◎帶動台灣成長駭客話題的專業講師,親授讓產品突破80分的成長秘笈 @這本書要給誰看? 1. 創業者、個人品牌經營者,想要提高自己服務轉換率的人。 2. 空有產品,但是賣不出去,花了錢投廣告卻效果低落的人。 @這本書有什麼不一樣? 1.全球最重要的趨勢,台灣最知名的 Growth Hack 講師 Xd......一起来看看 《Growth Hack 這樣做》 这本书的介绍吧!

URL 编码/解码
URL 编码/解码

URL 编码/解码

SHA 加密
SHA 加密

SHA 加密工具

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换