OR博客
Bitmap简介
OrdinaryRoad
创建于:2021-10-14 21:52:18
0
17
74
0
假设有这样一个需求:在20亿个随机整数中找出某个数m是否存在其中,并假设32位操作系统,4G内存。
转载自:[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}这几个数: ![](https://oss.ordinaryroad.top/api/download/thumbnail/2021-10-14/928d337fed1e4efdb7ef3d48d9f4eac5.png) 计算机内存分配的最小单位是字节,也就是8位,那如果要表示{12,13,15}怎么办呢? 当然是在另一个8位上表示了: ![](https://oss.ordinaryroad.top/api/download/thumbnail/2021-10-14/61c0c163cdad4d1e8c31f237289dc611.png) 这样的话,好像变成一个二维数组了 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位,然后按位或 ![](https://oss.ordinaryroad.top/api/download/thumbnail/2021-10-14/e4539973373f40a2b50b38311f5c1339.png) 换成二进制就是 ![](https://oss.ordinaryroad.top/api/download/thumbnail/2021-10-14/56912cade7ae41a5b07cb64668b4235d.png) 这就相当于 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移除,该怎么做呢? ![](https://oss.ordinaryroad.top/api/download/thumbnail/2021-10-14/02ff8f7f2dac4d70b491cea00de83d18.png) 从图上看,只需将该数所在的位置为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
评论
楼主暂时不想被别人评论哦~