【算法与数据结构专场】BitMap算法基本操作代码实现

上篇我们讲了BitMap是如何对数据进行存储的,没看过的可以看一下【算法与数据结构专场】BitMap算法介绍

这篇我们来讲一下BitMap这个数据结构的代码实现。

回顾下数据的存储原理

一个二进制位对应一个非负数n,如果n存在,则对应的二进制位的值为1,否则为0。

这个时候,我们的第一个问题:

我们在使用byte,int,short,long等这些数据类型在存储数据的时候,他们最小的都要占用一个字节的内存,也就是8个bit,也就是说,最小的操作单位是8个bit。根本就没有可以一个一个bit位操作的数据类型啊。

在Java的bitMaP实现中,它采用的是用一个long数据来进行存储的。一个long占用8个字节,即64bit,所以一个long可以存储64个数。例如 arr 是一个long 类型的数组,则 arr[0]可以存 0 ~ 63,arr[1]可以存64 ~127,以此类推。

不过,我们就采用byte数组的来存吧。一个byte占用一个字节,即8bit,可以存8个数字。

当然,你要采用long数组来存也可以。在实现上可以说是一样的。

例如我们要存储(1,3,5,7,8,10)时,他们的内存如下所示。

下面我们就来讲讲如何对一个一个位进行操作的。

如何向bitmap中添加一个数值

我们先来说说如何在bitmap中如何添加一个数值的问题,例如我们我们要添加n=14。

这个其实很简单,我们先找到n在arr数组中的下标index,显然index = 1。然后再找到n在arr[index]中的位置position,显然这里position = 6。

这里还是可以很容易找出index和position的公式的。即

index = n / 8 = n >> 3。

position = n % 8 = n & 0x07。

接下来我们把1向右移动position个二进制位,然后把所得的结果和arr[index]做“或(or)”操作就可以了。如下图

这里有个需要注意的地方,在画图的时候,为了方便,我们是把左边的位当作低位,右边的位当作高位来算了。不过在实际的存储中,左边的才是存高位,而右边的存的是低位。所以在我们的代码实现中,我们所说的右移对应代码的左移。

代码实现

//添加数据的操作

public void add(int n){
    //用>>的操作是,运算会比较快
    int index = n >> 3;
    int position = n & 0x07;
    //把1右移和做or操作两步一起
    //即 << 对应上图的右移,实际上<<是左移符。
    arr[index] |= 1 << position;
}

知道了add操作,其他的操作差不多类似。

当然,我们实现的add操作只是简单的实现一下,假如你要严谨地实现的话,还是需要很多异常的判断的。例如判断这个数是否是非负数,判断arr数组是否下标越界,进行容量的扩充等等。有兴趣的可以严谨去实现一下。

删除操作

我们只需要把对应的二进制的1变成0就可以了。

我们可以把1右移(代码中对应左移)后的结果取反,然后与arr[index]做“与”操作就可以了。代码如下:

public void delete(int n){
    int index = n >> 3;
    int position = n & 0x07;
    arr[index] &= ~(1 << position);
}

判断是否存在操作

我们把1右移之后,把结果和arr[index]做“与”操作,如何结果不为0,则证明存在,否则就不存在。

public boolean contain(int n){
    int index = n >> 3;
    int position = n & 0x07;
    return (arr[index] & (1 << position)) != 0;
}

三个最基本的操作代码基本实现了。

希望大家能够去实践一下。

全部代码:

public class BitMap {
    private byte[] arr;
    //容量,即最多能够存多少个数据
    private int capacity;

    public BitMap(int capacity) {
        this.capacity = capacity;
        //一个byte可以存8个数据,capacity实际上指的是多少个bit
        arr = new byte[(capacity / 8 + 1)];
    }

    //添加数据的操作

    public void add(int n){
        //用>>的操作是,运算会比较快
        int index = n >> 3;
        int position = n & 0x07;
        //把1右移和做or操作两步一起
        //即 << 对应上图的右移,实际上<<是左移符。
        arr[index] |= 1 << position;
    }

    public void delete(int n){
        int index = n >> 3;
        int position = n & 0x07;
        arr[index] &= ~(1 << position);
    }

    public boolean contain(int n){
        int index = n >> 3;
        int position = n & 0x07;
        return (arr[index] & (1 << position)) != 0;
    }
}

问题

大家看了以上的代码,有没发现一些问题呢?

例如我们只在bitmap存储1个数,并且存的数值是2000000000,我们就会在第2000000000个二进制把0改为1。也就是说arr数组的大小至少为2000000000/8+1。可是这时候前面的二进制位并没有存数据,那不是超级超级浪费资源?

所以说,像我们上面的那种写法可以说是暴力写法,没有经过任何优化,实际上,在Java自带的bitMap中是有很多优化的,并不会像我们上面实现的代码一样那么浪费空间资源。有兴趣的可以研究下。

至于如何优化,我会在之后的文章讲,尽情期待。觉得有帮助的话可以转发分享给更多的小伙伴哦

- End -

本文分享自微信公众号 - 苦逼的码农(di201805)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-09-23

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

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券