首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Bit-map java 原

Bit-map java 原

作者头像
wuweixiang
发布2018-08-14 11:42:39
5020
发布2018-08-14 11:42:39
举报
文章被收录于专栏:吴伟祥吴伟祥

一、简介

Bit-map就是用一个bit位来标记某个元素对应的Value, 而Key即是该元素。由于采用了Bit为单位来存储数据,因此在存储空间方面,可以大大节省。

可以把16GB的存储空间缩小为16GB/32 = 512M,就可以大大减少读取文件的工作。直接读一次文件存入内存,然后遍历输出就完成了排序。

优点:

1.运算效率高,不许进行比较和移位;

2.占用内存少,比如N=10000000;只需占用内存为N/8=1250000Byte=1.25M。 

10000000个bit占用的空间:

1byte = 8bit

1kb = 1024byte

1mb = 1024kb

占用的空间为:10000000/8/1024/1024mb。

大概为1mb多一些。

缺点:

       所有的数据不能重复。即不可对重复的数据进行排序和查找。  

二、具体思路

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

即:

1.求十进制0-N对应在数组a中的下标: n/32 

2.求0-N对应0-31中的数:N%32=M

3.利用移位0-31使得对应32bit位为1: 1<<M,并置1;

三、Bit-Map的应用

1)可进行数据的快速查找,判重,删除,一般来说数据范围是int的10倍以下。

 2)去重数据而达到压缩数据

四、在Java中的实现

 @Test
    public void size() {
        int [] array = new int [] {3,64,65,3};
        BitSet bitSet  = new BitSet();//默认 8byte = 64bit
        System.out.println(bitSet.size());
        //将数组内容组bitmap
        for(int i=0;i<array.length;i++)
        {
            bitSet.set(array[i], true);
        }
        System.out.println(bitSet.size());
        System.out.println(bitSet.get(3));
        System.out.println(bitSet.get(64));
        System.out.println(bitSet.get(66));
    }


Console:
64
128
true
true
false
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2017/08/11 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 一、简介
  • 二、具体思路
  • 三、Bit-Map的应用
  • 四、在Java中的实现
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档