文档章节

Java-基础-BitMap深度分析

nickles
 nickles
发布于 2017/05/07 23:04
字数 1287
阅读 207
收藏 2

 一、问题引入

        BitMap从字面的意思,很多人认为是位图,其实准确的来说,翻译成基于位的映射,怎么理解呢?

举一个例子,有一个无序有界int数组{1,2,5,7},初步估计占用内存4*4=16字节,这倒是没什么奇怪的,但是假如有10亿个这样的数呢,10亿*4/(1024*1024*1024)=3.72G左右。如果这样的一个大的数据做查找和排序,那估计内存也崩溃了,有人说,这些数据可以不用一次性加载,那就是要存盘了,存盘必然消耗IO。我们提倡的是高性能,这个方案直接不考虑。

 

二、问题分析

     如果用BitMap思想来解决的话,就好很多,那么BitMap是怎么解决的啊,如下:

一个byte是占8个bit,如果每一个bit的值就是有或者没有,也就是二进制的0或者1,如果用bit的位置代表数组值有还是没有,那么0代表该数值没有出现过,1代表该数组值出现过。不也能描述数据了吗?具体如下图:

 

是不是很神奇,那么现在假如10亿的数据所需的空间就是3.72G/32了吧,一个占用32bit的数据现在只占用了1bit,节省了不少的空间,排序就更不用说了,一切显得那么顺利。这样的数据之间没有关联性,要是读取的,你可以用多线程的方式去读取。时间复杂度方面也是O(Max/n),其中Max为byte[]数组的大小,n为线程大小。

 

三、应用与代码

    如果BitMap仅仅是这个特点,我觉得还不是它的优雅的地方,接下来继续欣赏它的魅力所在。下面的计算思想其实就是针对bit的逻辑运算得到,类似这种逻辑运算的应用场景可以用于权限计算之中。

 

  再看代码之前,我们先搞清楚一个问题,一个数怎么快速定位它的索引号,也就是说搞清楚byte[index]的index是多少,position是哪一位。举个例子吧,例如add(14)。14已经超出byte[0]的映射范围,在byte[1]范围之类。那么怎么快速定位它的索引呢。如果找到它的索引号,又怎么定位它的位置呢。Index(N)代表N的索引号,Position(N)代表N的所在的位置号。

  Index(N) = N/8 = N >> 3;

 Position(N) = N%8 = N & 0x07;

 

  (1)  add(int num)

   你要向bitmap里add数据该怎么办呢,不用担心,很简单,也很神奇。

   上面已经分析了,add的目的是为了将所在的位置从0变成1.其他位置不变.

  

 实例代码:

    public void add(int num){
        // num/8得到byte[]的index
        int arrayIndex = num >> 3; 
        
        // num%8得到在byte[index]的位置
        int position = num & 0x07; 
        
        //将1左移position后,那个位置自然就是1,然后和以前的数据做|,这样,那个位置就替换成1了。
        bits[arrayIndex] |= 1 << position; 
    }

(2) clear(int num)

     对1进行左移,然后取反,最后与byte[index]作与操作。

  

实例代码:

    public void clear(int num){
        // num/8得到byte[]的index
        int arrayIndex = num >> 3; 
        
        // num%8得到在byte[index]的位置
        int position = num & 0x07; 
        
        //将1左移position后,那个位置自然就是1,然后对取反,再与当前值做&,即可清除当前的位置了.
        bits[arrayIndex] &= ~(1 << position); 

    }

(4) contain(int num) 

 

示例代码:

    public boolean contain(int num){
        // num/8得到byte[]的index
        int arrayIndex = num >> 3; 
        
        // num%8得到在byte[index]的位置
        int position = num & 0x07; 
        
        //将1左移position后,那个位置自然就是1,然后和以前的数据做&,判断是否为0即可
        return (bits[arrayIndex] & (1 << position)) !=0; 
    }

全部代码如下:

package com.chs.alg.bitmap;

public class BitMap {
    //保存数据的
    private byte[] bits;
    
    //能够存储多少数据
    private int capacity;
    
    
    public BitMap(int capacity){
        this.capacity = capacity;
        
        //1bit能存储8个数据,那么capacity数据需要多少个bit呢,capacity/8+1,右移3位相当于除以8
        bits = new byte[(capacity >>3 )+1];
    }
    
    public void add(int num){
        // num/8得到byte[]的index
        int arrayIndex = num >> 3; 
        
        // num%8得到在byte[index]的位置
        int position = num & 0x07; 
        
        //将1左移position后,那个位置自然就是1,然后和以前的数据做|,这样,那个位置就替换成1了。
        bits[arrayIndex] |= 1 << position; 
    }
    
    public boolean contain(int num){
        // num/8得到byte[]的index
        int arrayIndex = num >> 3; 
        
        // num%8得到在byte[index]的位置
        int position = num & 0x07; 
        
        //将1左移position后,那个位置自然就是1,然后和以前的数据做&,判断是否为0即可
        return (bits[arrayIndex] & (1 << position)) !=0; 
    }
    
    public void clear(int num){
        // num/8得到byte[]的index
        int arrayIndex = num >> 3; 
        
        // num%8得到在byte[index]的位置
        int position = num & 0x07; 
        
        //将1左移position后,那个位置自然就是1,然后对取反,再与当前值做&,即可清除当前的位置了.
        bits[arrayIndex] &= ~(1 << position); 

    }
    
    public static void main(String[] args) {
        BitMap bitmap = new BitMap(100);
        bitmap.add(7);
        System.out.println("插入7成功");
        
        boolean isexsit = bitmap.contain(7);
        System.out.println("7是否存在:"+isexsit);
        
        bitmap.clear(7);
        isexsit = bitmap.contain(7);
        System.out.println("7是否存在:"+isexsit);
    }
}

 

 

 

 

本文转载自:http://www.cnblogs.com/wuhuangdi/p/4126752.html#3074215

nickles
粉丝 5
博文 39
码字总数 32378
作品 0
深圳
程序员
私信 提问
Android Bitmap变迁与原理解析(4.x-8.x)

App开发不可避免的要和图片打交道,由于其占用内存非常大,管理不当很容易导致内存不足,最后OOM,图片的背后其实是Bitmap,它是Android中最能吃内存的对象之一,也是很多OOM的元凶,不过,在...

看书的小蜗牛
2018/05/22
0
0
bitmap and drawable

Android中Bitmap和Drawable Android 一、相关概念 1、Drawable就是一个可画的对象,其可能是一张位图(BitmapDrawable),也可能是一个图形(ShapeDrawable),还有可能是一个图层(LayerDr...

元来元去
2012/01/13
0
0
Android中Bitmap和Drawable

Android中Bitmap和Drawable Android 一、相关概念 1、Drawable就是一个可画的对象,其可能是一张位图(BitmapDrawable),也可能是一个图形(ShapeDrawable),还有可能是一个图层(LayerDr...

笨笨熊的徒弟
2012/11/11
0
0
bitmap设置图片尺寸缩小,避免内存溢出/OutOfMemoryError的优化方法

我们都知道Android的Dalvik VM为一个应用提供了大约16MB的内存,一般我们处理超过8MB的图片将会出现OutOfMemoryError异常(内存溢出异常),报如下错误: 20155392-byte external allocatio...

DD2086
2011/12/01
0
0
有效解决Android加载大图片时内存溢出的问题

首先解析一下基本的知识: 位图模式,bitmap颜色位数是1位 灰度模式,bitmap颜色位数是8位,和256色一样 RGB模式,bitmap颜色位数是24位 在RGB模式下,一个像素对应的是红、绿、蓝三个字节 ...

蜗牛TT
2012/10/24
0
3

没有更多内容

加载失败,请刷新页面

加载更多

texlive安装

Installing to: D:/bin/texlive/texlive/2019Installing [001/307, time/total: ??:??/??:??]: adobemapping [2130k]Installing [002/307, time/total: 00:03/08:57]: ae [84k]Installing......

MtrS
今天
2
0
运维规范

命名规范 发布流程 监控告警 故障定位 状态 日志 监控

以谁为师
今天
2
0
约瑟夫环(报数游戏)java实现

开端 公司组织考试,一拿到考题,就是算法里说的约瑟夫环,仔细想想 以前老师将的都忘了,还是自己琢磨把~ package basic.gzy;import java.util.Iterator;import java.util.LinkedList;...

无极之岚
今天
3
0
Kernel字符设备驱动框架

Linux设备分为三大类:字符设备,块设备和网络设备,这三种设备基于不同的设备框架。相较于块设备和网络设备,字符设备在kernel中是最简单的,也是唯一没有基于设备基础框架(device结构)的...

yepanl
今天
3
0
Jenkins 中文本地化的重大进展

本文首发于:Jenkins 中文社区 我从2017年开始,参与 Jenkins 社区贡献。作为一名新成员,翻译可能是帮助社区项目最简单的方法。 本地化的优化通常是较小的改动,你无需了解项目完整的上下文...

Jenkins中文社区
昨天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部