细品数据结构之BitMap

背景

有10G的数据,查找其中是否有包含某个数据。但是内存只有2G。如何在10G数据中查看这条数据是否存在。也许有同学立马会想到bloom filter，是的布隆过滤器是由位图思想演化来的一个更高级的数据结构。这篇文章主要还是讲一下位图的的原理和思想。

BitMap（位图）

简介

• 用一个bit来表示某个值，也就是通过存储位置来代表这个数据。
• 位图没有存储具体的值，而只是存储了这个值在应用中的数据指纹(可以指数组下标，也可以指的是hash后的值所映射的数组下标)。位图是不可以重复的，且是有序的(具体还是根据存储的方式来看，有序存储是有序的，hash计算时无序的)

数据类型

1. 底层是通过数组进行存储的，数组中的每个bit都代表一个数据值，0代表没有，1代表有
2. 比如有，1357这个数据，按我们普通存储，一个int类型有4bit，所以共需要花费内存28bit 但是使用位图来进行存储的话，只需要7bit，采用的存储方式是顺序存储，数组的第一个从0开始，1就放在数组的第一个槽内，将其置为1，所以其存储后的结构如下：

在这里插入图片描述

存储方式

1. 顺序存储

• 就如上面所列举的例子，直接根据数组修下标作为数据的指纹，进行排序。
• 但是这样会有问题，就是如果存储的数据不是从0开始的而是从1000或者10000开始的呢？ 或者说这些数据之间的间隔很大呢？这都是问题。

2. hash计算进行存储

• 在java中通过hashCode()，MD5等方式的计算进行散列到对应的数组下标。但是散列后会出现特别大的值，随意说得再给对应的值进行取余数计算。列如： 给定一个空的数组，1024长度，存储的数据进行hash后的值是1234567除1024取余数是647，所以最后会落在647这个位置。相同的数据肯定会落在同一个位置，这也就是位图不会重复的原因，在这种情况下是无序的。

应用

1. 计算每天的活跃用户

• 请求到的用户进行hash计算且除以预算好的值进行进行取余运算，统计bit位是1的数据量也就是用户的日活量

2. 用户的回访统计，将两天的bitMap进行and运算

• 将两天的日活量的数据进行取and运算，然后是1的也就是回访的用户量、

已有的轮子

1. JDK中的BitSet 对象 https://docs.oracle.com/javase/8/docs/api/java/util/BitSet.html
2. redis的bitmap用法（https://blog.csdn.net/u011957758/article/details/74783347）

总结

• BitMap是一个不能存储真实数据值，即只能说明这个数据存在不存在
• BitMap存储数据的方式是根据存储位置来区分这个数据，通过该存储位置是否被占用来表示这个数据有没有。
• 每个存储位置为1Bit，这就是其精髓所在，占用空间少
• bloom fliter 也是这个思想，将某个数据进行多次散列，通过固定长度数组，进行存储更多的值。一个数据对应多个槽。具体详解请看：https://editor.csdn.net/md/?articleId=108135235