BitMap 算法

什么是 BigMap 算法

所谓 BitMap 就是用一个 bit 位来标记某个元素对应的 value,而 key 即是这个元素。由于采用bit为单位来存储数据,因此在可以大大的节省存储空间。

算法思想

32位机器上,一个整形,比如 int a; 在内存中占32bit,可以用对应的32个bit位来表示十进制的0-31个数,bitmap算法利用这种思想处理大量数据的排序与查询。

优点:

  • 效率高,不许进行比较和移位
  • 占用内存少,比如N=10000000;只需占用内存为N/8 = 1250000Bytes = 1.2M,如果采用int数组存储,则需要38M多

缺点:

  • 无法对存在重复的数据进行排序和查找

示例:

申请一个int型的内存空间,则有4Byte,32bit。输入 4, 2,  1,  3时:

输入4:

输入2:

输入1:

输入3:

思想比较简单,关键是十进制和二进制bit位需要一个 map 映射表,把10进制映射到bit位上。

map映射表

假设需要排序或者查找的总数N=10000000,那么我们需要申请的内存空间为 int a[N/32 + 1].其中a[0]在内存中占32位,依此类推:

bitmap表为:

a[0] ------> 0 - 31

a[1] ------> 32 - 63

a[2] ------> 64 - 95

a[3] ------> 96 - 127

......

下面介绍用位移将十进制数转换为对应的bit位

位移转换

(1) 求十进制数 0-N 对应的在数组 a 中的下标

index_loc = N / 32即可,index_loc即为n对应的数组下标。例如n = 76, 则loc = 76 / 32 = 2,因此76在a[2]中。

(2)求十进制数0-N对应的bit位

bit_loc = N % 32即可,例如 n = 76, bit_loc = 76 % 32 = 12

(3)利用移位0-31使得对应的32bit位为1

代码示例(c语言)

#include <stdio.h>
#include <stdlib.h>

#define SHIFT 5
#define MASK 0x1F

/**
 * 设置所在的bit位为1
 *
 * T = O(1)
 *
 */
void set(int n, int *arr)
{
    int index_loc, bit_loc;

    index_loc = n >> SHIFT; // 等价于n / 32
    bit_loc = n & MASK;    // 等价于n % 32 。 h%2^n = h & (2^n -1)

    arr[index_loc] |= 1 << bit_loc;
}

/**
 * 初始化arr[index_loc]所有bit位为0
 *
 * T = O(1)
 *
 */
void clr(int n, int *arr)
{
    int index_loc;
    index_loc = n >> SHIFT;
    arr[index_loc] &= 0;
}

/**
 * 测试n所在的bit位是否为1
 *
 * T = O(1)
 *
 */
int test(int n, int *arr)
{
    int i, flag;
    i = 1 << (n & MASK);
    flag = arr[n >> SHIFT] & i;
    return flag;
}

int main(void)
{
    int i, num, space, *arr;
    while (scanf("%d", &num) != EOF) {
        // 确定大小&&动态申请数组
        space = num / 32 + 1;
        arr = (int *)malloc(sizeof(int) * space);

        // 初始化bit位为0
        for (i = 0; i <= num; i ++)
            clr(i, arr);

        // 设置num的比特位为1
        set(num, arr);
        
        // 测试
        if (test(num, arr)) {
            printf("成功!\n");
        } else {
            printf("失败!\n");
        }
    }
    return 0;
}

MARK 补充 Java 实现

参考:http://www.cnblogs.com/dyllove98/archive/2013/07/26/3217741.html

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏精讲JAVA

Java异常面试问题

异常是在程序执行期间可能发生的错误事件,并且会中断它的正常流程。异常可能来自不同类型的情况,例如用户输入的错误数据,硬件故障,网络连接故障等。

1283
来自专栏林欣哲

Java异常 知识点速查

971
来自专栏PHP在线

shell脚本编程入门

什么是Shell脚本 示例 看个例子吧: #!/bin/sh cd ~ mkdir shell_tut cd shell_tut for ((i=0; i<1...

3386
来自专栏爱撒谎的男孩

Struts2之获取请求参数

3496
来自专栏java一日一条

Java编程常见问题汇总1

每天在写Java程序,其实里面有一些细节大家可能没怎么注意,这不,有人总结了一个我们编程中常见的问题。虽然一般没有什么大问题,但是最好别这样做。另外这里提到的很...

892
来自专栏前端侠2.0

co yield避免嵌套详细代码示例。

1481
来自专栏chenssy

干货分享|Java异常经典14问,你都能答对吗?

异常是在程序执行期间可能发生的错误事件,并且会中断它的正常流程。异常可能来自不同类型的情况,例如用户输入的错误数据,硬件故障,网络连接故障等。

1072
来自专栏积累沉淀

Linux之grep和egrep命令总结

grep / egrep 语法: grep  [-cinvABC]  'word'  filename -c :打印符合要求的行数 -i :忽略大小写 ...

19010
来自专栏java一日一条

Java反射在JVM的实现

反射使程序代码能够接入装载到JVM中的类的内部信息,允许在编写与执行时,而不是源代码中选定的类协作的代码,是以开发效率换运行效率的一种手段。这使反射成为构建灵活...

2153
来自专栏desperate633

Java动态代理与静态代理静态代理动态代理

我们先看一个简单的例子,当我们需要程序中加入方法执行的日志信息的时候,很显然我们最容易想到的实现方法,就是在方法前后插入日志记录信息。

1572

扫码关注云+社区

领取腾讯云代金券