OR博客
Bitmap简介
苗锦洲
创建于:2021-10-14 21:52:18
0
34
293
0
假设有这样一个需求:在20亿个随机整数中找出某个数m是否存在其中,并假设32位操作系统,4G内存。

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

转载自: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

评论
楼主暂时不想被别人评论哦~