转载自：Bitmap 简介 - 废物大师兄 - 博客园 (cnblogs.com)

BitMap

0. 简介

Bit-map 的基本思想就是用一个 bit 位来标记某个元素对应的 Value，而 Key 即是该元素。由于采用了 Bit 为单位来存储数据，因此在存储空间方面，可以大大节省。（PS：划重点 节省存储空间）

假设有这样一个需求：在 20 亿个随机整数中找出某个数 m 是否存在其中，并假设 32 位操作系统，4G 内存

在 Java 中，int 占 4 字节，1 字节=8 位（1 byte = 8 bit）

如果每个数字用 int 存储，那就是 20 亿个 int，因而占用的空间约为 (2000000000*4/1024/1024/1024)≈7.45G

如果按位存储就不一样了，20 亿个数就是 20 亿位，占用空间约为 (2000000000/8/1024/1024/1024)≈0.2****33G

高下立判，无需多言

那么，问题来了，如何表示一个数呢？

刚才说了，每一位表示一个数，0 表示不存在，1 表示存在，这正符合二进制

这样我们可以很容易表示{1,2,4,6}这几个数：

计算机内存分配的最小单位是字节，也就是 8 位，那如果要表示{12,13,15}怎么办呢？

当然是在另一个 8 位上表示了：

这样的话，好像变成一个二维数组了

1 个 int 占 32 位，那么我们只需要申请一个 int 数组长度为 int tmp[1+N/32] 即可存储，其中 N 表示要存储的这些数中的最大值，于是乎：

tmp[0]：可以表示 0~31

tmp[1]：可以表示 32~63

tmp[2]：可以表示 64~95

。。。

如此一来，给定任意整数 M，那么 M/32 就得到下标，M%32 就知道它在此下标的哪个位置

1. 基本操作

1.1 添加

这里有个问题，我们怎么把一个数放进去呢？例如，想把 5 这个数字放进去，怎么做呢？

首先，5/32=0，5%32=5，也是说它应该在 tmp[0]的第 5 个位置，那我们把 1 向左移动 5 位，然后按位或

换成二进制就是

这就相当于 86 | 32 = 118

86 | (1<<5) = 118

b[0] = b[0] | (1<<5)

也就是说，要想插入一个数，将 1 左移带代表该数字的那一位，然后与原数进行按位或操作

化简一下，就是 86 + (5/8) | (1<<(5%8))

因此，公式可以概括为：p + (i/8)|(1<<(i%8)) 其中，p 表示现在的值，i 表示待插入的数

1.2 清除

以上是添加，那如果要清除该怎么做呢？

还是上面的例子，假设我们要 6 移除，该怎么做呢？

从图上看，只需将该数所在的位置为 0 即可

1 左移 6 位，就到达 6 这个数字所代表的位，然后按位取反，最后与原数按位与，这样就把该位置为 0 了

b[0] = b[0] & (~(1<<6))

b[0] = b[0] & (~(1<<(i%8)))

1.3 查找

前面我们也说了，每一位代表一个数字，1 表示有（或者说存在），0 表示无（或者说不存在）。通过把该为置为 1 或者 0 来达到添加和清除的小伙，那么判断一个数存不存在就是判断该数所在的位是 0 还是 1

假设，我们想知道 3 在不在，那么只需判断 b[0] & (1<<3) 如果这个值是 0，则不存在，如果是 1，就表示存在

代码实现

package com.example.learn.datastructures.bitmap;

import java.util.Collection;
import java.util.Iterator;
import java.util.Set;

/**
 * @author mjz
 * @date 2021/10/14
 */
public class Bitmap implements Set<Integer> {

    int maxSize;
    int currentSize;

    int[] nums;

    /**
     * int的位数
     */
    private static final int BIT_COUNT = 32;

    /**
     * 构造函数
     *
     * @param maxSize 最多多少个数，包括0
     */
    public Bitmap(int maxSize) {
        this.maxSize = maxSize;
        nums = new int[(this.maxSize - 1) / BIT_COUNT + 1];
    }

    public void print() {
        int rowNum = 0;
        for (int num : nums) {
            for (int i = rowNum * BIT_COUNT; i < (rowNum + 1) * BIT_COUNT; i++) {
                System.out.print(i + "\t");
            }
            System.out.println();
            for (int i = 0; i < BIT_COUNT; i++) {
                System.out.print((1 & (num >> i)) + "\t");
            }
            System.out.println();
            System.out.println();
            rowNum++;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Bitmap bitmap = new Bitmap(33);
        bitmap.print();

        bitmap.add(4);
        bitmap.add(32);
        bitmap.print();

        bitmap.remove(4);
        bitmap.print();
    }

    @Override
    public int size() {
        return this.currentSize;
    }

    @Override
    public boolean isEmpty() {
        return currentSize != 0;
    }

    @Override
    public boolean contains(Object o) {
        if (!(o instanceof Integer)) {
            return false;
        }
        int integer = (Integer) o;
        // 找到第几个数字
        int x = integer / BIT_COUNT;
        // 确定第几位
        int y = integer % BIT_COUNT;
        return (nums[x] & (1 << y)) == (1 << y);
    }

    @Override
    public Iterator<Integer> iterator() {
        return null;
    }

    @Override
    public Object[] toArray() {
        return new Object[0];
    }

    @Override
    public <T> T[] toArray(T[] a) {
        return null;
    }

    @Override
    public boolean add(Integer integer) {
        if (integer >= maxSize) {
            throw new IndexOutOfBoundsException("要添加的数：" + integer + "，总大小：" + maxSize);
        }
        if (contains(integer)) {
            return false;
        }
        // 找到第几个数字
        int x = integer / BIT_COUNT;
        // 确定第几位
        int y = integer % BIT_COUNT;

        int i = nums[x];
        nums[x] = i ^ (1 << y);
        currentSize++;
        return true;
    }

    @Override
    public boolean remove(Object o) {
        if (!contains(o)) {
            return false;
        }
        int integer = (Integer) o;
        // 找到第几个数字
        int x = integer / BIT_COUNT;
        // 确定第几位
        int y = integer % BIT_COUNT;

        int i = nums[x];
        nums[x] = i & (~(1 << y));
        currentSize--;
        return true;
    }

    @Override
    public boolean containsAll(Collection<?> c) {
        return false;
    }

    @Override
    public boolean addAll(Collection<? extends Integer> c) {
        return false;
    }

    @Override
    public boolean retainAll(Collection<?> c) {
        return false;
    }

    @Override
    public boolean removeAll(Collection<?> c) {
        return false;
    }

    @Override
    public void clear() {
        for (int i = 0; i < nums.length; i++) {
            nums[i] &= 0;
        }
    }

}

​

运行结果

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0

32	33	34	35	36	37	38	39	40	41	42	43	44	45	46	47	48	49	50	51	52	53	54	55	56	57	58	59	60	61	62	63
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0


0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31
0	0	0	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0

32	33	34	35	36	37	38	39	40	41	42	43	44	45	46	47	48	49	50	51	52	53	54	55	56	57	58	59	60	61	62	63
1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0


0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0

32	33	34	35	36	37	38	39	40	41	42	43	44	45	46	47	48	49	50	51	52	53	54	55	56	57	58	59	60	61	62	63
1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0



Process finished with exit code 0

​

2. 作用

// TODO