BitMap算法

BitMap算法

BitMap算法安详严整

 最初的文章链接:
** 

  所谓的BitMap正是用一个bit位来标识某些成分所对应的value,而key就是该因素,由于BitMap使用了bit位来存款和储蓄数据,由此得以大大节约存款和储蓄空间。

中央思维:

  那此作者用贰个粗略的例证来详细介绍BitMap算法的原理。假若大家要对0-7内的5个因素(4,7,2,5,3卡塔尔(قطر‎实行排序(这里假使成分未有再度卡塔尔(قطر‎。大家可以动用BitMap算法达到排序指标。要代表8个数,大家供给8个byte。

  1.首先大家开辟多个字节(8byteState of Qatar的空中,将那么些空间的有着的byte位都安装为0

  2.然后方便人民群众这5个要素,第四个成分是4,因为下面从0开头,由此我们把第七个字节的值设置为1

  3.然后再管理剩下的多少个要素,最后8个字节的气象如下图

  澳门新萄京 1

  4.现行大家遍历二次bytes区域,把值为1的byte的职位输出(2,3,4,5,7卡塔尔,那样便高达了排序的目标

  从地点的例证大家得以看到,BitMap算法的考虑照旧比较轻松的,关键的标题是哪些鲜明10进制的数到2进制的映射图

MAP映射:

  假使须求排序或则查找的数的总和N=100000000,BitMap中1bit象征一个数字,1个int
= 4Bytes = 4*8bit = 32 bit,那么N个数要求N/32
int空间。所以大家需求提请内部存款和储蓄器空间的大小为int a[1 +
N/32],其中:a[0]在内部存储器中占32为能够对应十进制数0-31,依次类推:

  a[0]—————————–> 0-31

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

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

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

  ………………………………………………

  那么十进制数如何更动为对应的bit位,上边介绍用位移将十进制数转变为相应的bit位:

  1.求十进制数在对应数组a中的下标

  十进制数0-31,对应在数组a[0]中,32-63对应在数组a[1]中,64-95对应在数组a[2]中………,使用数学归结深入分析得出结论:对于七个十进制数n,其在数组a中的下标为:a[n/32]

  2.求出十进制数在对应数a[i]中的下标

  比如十进制数1在a[0]的下标为1,十进制数31在a[0]中下标为31,十进制数32在a[1]中下标为0。
在十进制0-31就对应0-31,而32-63则对应也是0-31,即给定二个数n能够通过模32求得在对应数组a[i]中的下标。

  3.位移

  对于二个十进制数n,对应在数组a[n/32][n%32]澳门新萄京,中,但数组a终归不是八个二维数组,我们经过活动操作达成置1

  a[n/32] |= 1 << n % 32 
  移位操作: 
  a[n>>5] |= 1 << (n & 0x1F)

  n & 0x1F 保留n的后伍人 也便是 n % 32 求十进制数在数组a[i]中的下标

代码完毕:

 1 public class BitMap { 2  3  private static final int N = 10000000; 4  5  private int[] a = new int[N/32 + 1]; 6  7  /** 8   * 设置所在的bit位为1 9   * @param n10  */11  public void addValue(int n){12   //row = n / 32 求十进制数在数组a中的下标13   int row = n >> 5;14   //相当于 n % 32 求十进制数在数组a[i]中的下标15   a[row] |= 1 << (n & 0x1F);16  }17 18  // 判断所在的bit为是否为119  public boolean exits(int n){20   int row = n >> 5;21   return (a[row] & ( 1 << (n & 0x1F))) != 1;22  }23 24  public void display(int row){25   System.out.println("BitMap位图展示");26   for(int i=0;i<row;i++){27    List<Integer> list = new ArrayList<Integer>();28    int temp = a[i];29    for(int j=0;j<32;j++){30     list.add(temp & 1);31     temp >>= 1;32    }33    System.out.println("a["+i+"]" + list);34   }35  }36 37  public static void main(String[] args){38   int num[] = {1,5,30,32,64,56,159,120,21,17,35,45};39   BitMap map = new BitMap();40   for(int i=0;i<num.length;i++){41    map.addValue(num[i]);42   }43 44   int temp = 120;45   if(map.exits(temp)){46    System.out.println("temp:" + temp + "has already exists");47   }48   map.display(5);49  }50 }

使用范围:
  能够采纳在飞速寻找、去重、排序、压缩数量等。

代码示例(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 实现

 

参考:

移步转变

(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

算法观念

三11人机器上,贰个整形,比方 int a;
在内部存款和储蓄器中占32bit,能够用相应的叁十一个bit位来代表十进制的0-34个数,bitmap算法利用这种思虑管理大批量数额的排序与查询。

优点:

  • 频率高,不允许实行比较和平运动动
  • 并吞内存少,比方N=10000000;只需占用内部存款和储蓄器为N/8 = 1250000Bytes =
    1.2M,假使选用int数组存款和储蓄,则供给38M多

缺点:

  • 不能够对存在重新的数量开展排序和寻觅

示例:

申请三个int型的内部存款和储蓄器空间,则有4Byte,32bit。输入 4, 2,  1,  3时:

输入4:

澳门新萄京 2

输入2:

澳门新萄京 3

输入1:

澳门新萄京 4

输入3:

澳门新萄京 5

研讨比较简单,关键是十进制和二进制bit位供给叁个 map
映射表,把10进制映射到bit位上。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图