Bit-map java 原

一、简介

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏编程

Python入门白皮书#P01 Lists

文档: 我们以Google Python Exercises作为练习素材。 参考对应的文档 https://developers.google.com/edu/...

20560
来自专栏刘望舒

Java虚拟机(二)对象的创建与OOP-Klass模型

前言 在前一篇文章中我们学习了Java虚拟机的结构原理与运行时数据区域,那么我们大概知道了Java虚拟机的内存的概况,那么内存中的数据是如何创建和访问的呢?这篇...

267100
来自专栏极客编程

solidity智能合约

Solidity里的智能合约是面向对象语言里的类。它们持久存放在状态变量和函数中,(在里面)可以通过solidity修改这些变量。在不同的智能合约(实例)中调用...

16130
来自专栏java达人

多线程设计模式解读5—Immutable Object(不可变对象)模式

前面讲了Producer-Consumer模式,它有许多变种,我们以后会讲。我们将接着了解另外一种分支的设计模式,前面所讲的所有的模式,都是要用到锁的,而锁是会...

9030
来自专栏程序员的知识天地

最值得你收藏的30个Python常用小技巧!

[0, 1, 16, 81, 256, 625, 1296, 2401, 4096, 6561, 10000, 121, 144, 169, 196, 225,...

13920
来自专栏木木玲

JVM中 对象的内存布局 以及 实例分析

22080
来自专栏偏前端工程师的驿站

意译:《JVM Internals》

译者语                                  为加深对JVM的了解和日后查阅时更方便,于是对原文进行翻译。内容是建立在我对JVM的认...

25270
来自专栏本立2道生

实例分析C程序运行时的内存结构

这段代码包含两个函数,因此可以测试函数调用,此外还包含了静态变量、局部变量、返回值等

18310
来自专栏GreenLeaves

C# checked和unchecked详解

1、对基元类型执行的许多算术运算都可能造成溢出,有如下代码: Byte b=100; b=(Byte)(b+200); 简单的解读上面的代码: 第一步,将所有的...

21580
来自专栏佳爷的后花媛

java基础知识

Vector、Stack、HashTable、ConcurrentHashMap、Properties

31650

扫码关注云+社区

领取腾讯云代金券