位图数据结构及其在-Java和-Redis中的应用-深蓝源码网

目录

位图的基本介绍

概念

什么是位图?BitMap,大家直译为位图. 我的理解是:位图是内存中连续的二进制位(bit),可以用作对大量整形做去重和统计.

引入一个小栗子来帮助理解一下:

假如我们要存储三个int数字 (1,3,5),在java中我们用一个int数组来存储,那么占用了12个字节.但是我们申请一个bit数组的话.并且把相应下标的位置为1,也是可以表示相同的含义的,比如

可以看到,对应于1,3,5为下标的bit上的值为1,我们或者计算机也是可以get到1,3,5这个信息的.

优势

那么这么做有什么好处呢?感觉更麻烦了鸭,下面这种存储方式,在申请了bit[8]的场景下才占用了一个字节,占用内存是原来的12分之一,当数据量是海量的时候,比如40亿个int,这时候节省的就是10几个G的内存了.

这就引入了位图的第一个优势,<font color="red">占用内存小</font>.

再想一下,加入我们现在有一个位图,保存了用户今天的签到数据.下标可以是用户的ID.

A:

这代表了用户(1,3,5)今天签到了.

当然还有昨天的位图,

B:

这代表了用户(1,2,3,7)昨天签到了.

我们现在想求:

1. 昨天和今天都签到的用户.
2. 昨天或者今天签到的用户.

在关系型数据库中存储的话,这将是一个比较麻烦的操作,要么要写一些表意不明的SQL语句,要么进行两次查询,然后在内存中双重循环去判断.

而使用位图就很简单了,A & B, A | B 即可.上面的操作明显是一个集合的与或操作,而二进制天然就支持逻辑操作,且众所周知猫是液体.错了,众多周知是计算机进行二进制运算的效率很高.

这就是位图的第二个优点: <font color="red">支持与或运算且效率高</font>.

哇,这么完美,那么哪里可以买到呢?,那么有什么缺点呢?

不足

当然有,位图不能很方便的支持非运算,(当然,关系型数据库支持的也不好).这句话可能有点难理解.继续举个例子:

我们想查询今天没有签到的用户,直接对位图进行取非是不可以的.

对今天签到的位图取非得到的结果如下:

这意味着今天(0,2,4,6,7)用户没有签到吗?不是的,存在没有7(任意数字)号用户的情况,或者他注销了呢.

这是因为位图只能表示布尔信息,即true/false.他在这个位图中,表示的是XX用户今天有签到或者没有签到,但是不能额外的表达,xx用户存在/不存在这个状态了.

但是我们可以曲线救国,首先搞一个全集用户的位图.比如:

全集:

然后用全集的位图和签到的位图做异或操作,相同则为0,不相同则为1.

在业务的逻辑为: 用户存在和是否签到两个bool值,共四种组合.

用户存在,且签到了. 两个集合的对应位都为1,那么结果就为0. 用户存在,但是没签到. 全集对应位为1,签到为0,所以结果是1. 用户不存在,那么必然没可能签到, 两个集合的对应位都是0,结果为0.

所以结果中,为1的只有一种可能:用户存在且没有签到,正好是我们所求的结果.

A ^ 全集:

此外,位图对于稀疏数据的表现不是很好,(当然聪明的大佬们已经基本解决掉了这个问题).原生的位图来讲,如果我们只有两个用户,1号和100000000号用户,那么直接存储int需要8个字节也就是32个bit,而用位图存储需要1亿个bit.当数据量少,且跨度极大也就是稀疏的时候,原生的位图不太适合.

<a href="#xishu">点击这里跳转到稀疏数据的解决方案</a>

总结

那么我们来做一下总结:

位图是用二进制位来存储整形数据的一种数据结构,在很多方面都有应用,尤其是在大数据量的场景下,节省内存及提高运算效率十分实用.

他的优点有:

1. <font color="red">节省内存.</font> -> 因此在大数据量的时候更加显著.
2. <font color="red">与或运算效率高.</font> ->可以快速求交集和并集.

缺点有:

1. <font color="red">不能直接进行非运算.</font> -> 根本原因是位图只能存储一个布尔信息,信息多了就需要借助全量集合等数据辅助.
2. <font color="red">数据稀疏时浪费空间.</font> -> 这个不用很担心,后面会讲到大佬们的解法,基本可以解决掉.
3. <font color="red">只能存储布尔类型.</font> -> 有限制,但是业务中很多数据都可以转换为布尔类型.比如上面的例子中, 业务原意:用户每天的签到记录,以用户为维度. 我们可以转换为: 每天的每个用户是否签到,就变为了布尔类型的数据.

Java中的位图

上面讲了位图的原理,那么我们先来自己手动实现一个!

简陋版本

说明:因为后面还有JDK版本,所以这里只实现了很简陋的版本,方便理解位图的核心原理即可.这个简陋版本完全不可以直接使用,能跑,但是在很多情况下都会直接报错.

虽然简陋,但是必须的还是要有.

构造方法

写了一个仅支持bit数量的构造参数. 因为我们是用int数组来保存实际的数据,所以对传入的值右移5(相当于除以32,因为int是32位的嘛)就是int数组的大小.

set方法

支持将某一个位设置为true/false.

为了实现set-true,其实是有粗暴的符合人类思路的逻辑的,比如当调用set(5,true)的时候,我们将int数字转化为二进制字符串,得到000000000000000000000000000000(应该是32个我没数),然后将其右边第六位置为1,得到000000000000000000000000100000,然后再转回int数字.

这个方法很符合位图的直接定义,也很好理解,但是对于计算机来说,太麻烦了,而且过程中需要一个String,占用太多的内存空间了.

计算机更喜欢使用或运算来解决. 假设现有数字为3,即000000000000000000000000001000,这时候我们调用了set(10,true),怎么办呢,首先使用左移,将第11位置为1,然后与原来的值进行或操作.像下面这样子:

原来值 :     000000000000000000000000001000
1右移10位:   000000000000000000010000000000

或操作的结果: 000000000000000000010000001000   ----> 可以直接表示 3 和 10 两个位上都为1了.

设置某一个位为false,和上面的流程不太一样.除去粗暴的办法之外,还可以 对1右移x位的非取与.很拗口,下面是示例:

我们将3上的设为0.

原来值 :              000000000000000000010000001000    ----> 10和3上为1,
1右移3位:             000000000000000000000000001000
1右移3位取非后:        111111111111111111111111110111

原来的值与取非后取与:   000000000000000000010000000000   ----> 只有10上为1了.

get方法

获取某个位上的值.

当然也可以用粗暴的转换二进制字符串解决,但是使用与操作更加快速且计算机友好.

对set方法中的例子来说,设置了3和10之后,如果获取10上的值,可以:

当前值:        000000000000000000010000001000
1右移10位:     000000000000000000010000000000

与操作的结果:   000000000000000000010000000000    ---> 只要这个数字不等于0,即说明10上为1,等于0则为0.

实际的代码加注释如下:

/**
 * Created by pfliu on 2019/07/02.
 */
public class BitMapTest {
    // 实际使用int数组存储
    private int[] data;

    /**
     * 构造方法,传入预期的最大index.
     */
    public BitMapTest(int size) {
        this.data = new int[size >> 5];
    }

    /**
     * get 方法, 传入要获取的index, 返回bool值代表该位上为1/0
     */
    public boolean get(int bitIdx) {
        return (data[bitIdxToWorkIdx(bitIdx)] & (1 << bitIdx)) != 0;
    }

    /**
     * 将对应位置的值设置为传入的bool值
     */
    public void set(int idx, boolean v) {
        if (v) {
            set(idx);
        } else {
            clear(idx);
        }
    }

    // 将index的值设置为1
    private void set(int idx) {
        data[bitIdxToWorkIdx(idx)] |= 1 << idx;
    }

    // 将index上的值设置为0
    private void clear(int bitIdx) {
        data[bitIdxToWorkIdx(bitIdx)] &= ~(1L << bitIdx);
    }

    // 根据bit的index获取它存储的实际int在数组中的index
    private int bitIdxToWorkIdx(int bitIdx) {
        return bitIdx >> 5;
    }

    public static void main(String[] args) {

        BitMapTest t = new BitMapTest(100);
        t.set(10, true);

        System.out.println(t.get(9));
        System.out.println(t.get(10));

    }
}

JDK版本(BitSet源码阅读)

JDK中对位图是有实现的,实现类为BitSet,其中大致思想和上面实现的简陋版本类似,只是其内部数据是使用long数组来存储,此外加了许多的容错处理.下面看一下源码.还是按照方法分类来看.

常量及变量

    // long数组,64位的long是2的6次方
    private final static int ADDRESS_BITS_PER_WORD = 6;
    // 每一个word的bit数量
    private final static int BITS_PER_WORD = 1 << ADDRESS_BITS_PER_WORD;

    // 存储数据的long数组
    private long[] words;
    // 上面的数组中使用到了的word的个数
    private transient int wordsInUse = 0;
    // 数组的大小是否由用户指定的(注释里写明了:如果是true,我们假设用户知道他自己在干什么)
    private transient boolean sizeIsSticky = false;

构造方法及工厂方法

BitSet提供了两个公开的构造方法以及四个公开的工厂方法,分别支持从long[],LongBuffer,bytes [], ByteBuffer中获取BitSet实例.

各个方法及其内部调用的方法如下:

    // ---------构造方法-------

    // 无参的构造方法,初始化数组为长度为64个bit(即一个long)以及设置sizeIsSticky为false.
    public BitSet() {
        initWords(BITS_PER_WORD);
        sizeIsSticky = false;
    }

    // 根据用户传入的bit数量进行初始化,且设置sizeIsSticky为true.
    public BitSet(int nbits) {
        // nbits can't be negative; size 0 is OK
        if (nbits < 0)
            throw new NegativeArraySizeException("nbits < 0: " + nbits);

        initWords(nbits);
        sizeIsSticky = true;
    }
    // ---------构造方法的调用链 -------

    // 初始化数组
    private void initWords(int nbits) {
        words = new long[wordIndex(nbits-1) + 1];
    }

    // 根据bit数量获取long数组的大小,右移6位即可.
    private static int wordIndex(int bitIndex) {
        return bitIndex >> ADDRESS_BITS_PER_WORD;
    }

    // ---------工厂方法,返回BitSet实例 -------

    // 传入long数组
    public static BitSet valueOf(long[] longs) {
        int n;
        for (n = longs.length; n > 0 && longs[n - 1] == 0; n--)
            ;
        return new BitSet(Arrays.copyOf(longs, n));
    }

    // 传入LongBuffer
    public static BitSet valueOf(LongBuffer lb) {
        lb = lb.slice();
        int n;
        for (n = lb.remaining(); n > 0 && lb.get(n - 1) == 0; n--)
            ;
        long[] words = new long[n];
        lb.get(words);
        return new BitSet(words);
    }

    // 传入字节数组
    public static BitSet valueOf(byte[] bytes) {
        return BitSet.valueOf(ByteBuffer.wrap(bytes));
    }

    // 传入ByteBuffer
    public static BitSet valueOf(ByteBuffer bb) {
        bb = bb.slice().o										

						 技术沙龙 教程文章 热点综合