转载自：[Bitmap简介 - 废物大师兄 - 博客园 (cnblogs.com)](https://www.cnblogs.com/cjsblog/p/11613708.html) # 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.45**G 如果按位存储就不一样了，20亿个数就是20亿位，占用空间约为 (2000000000/8/1024/1024/1024)≈**0.2****33**G 高下立判，无需多言 那么，问题来了，如何表示一个数呢？ 刚才说了，每一位表示一个数，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，就表示存在 ### 代码实现 ```java 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; } } } ``` ### 运行结果 ```bash 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