位图数据结构及其在-Java和-Redis中的应用

呼延十 · 掘金 · · 2019-07-03 06:46

正文

请到「今天看啥」查看全文

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

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实例.