网站不足,百度权重站长工具,巩义做网站xd seo,成都个人网站制作#xff08;一#xff09;位图 位图是用来存放某种状态的#xff0c;因为一个bit上只能存0和1所以一般只有两种状态的情况下适合用位图#xff0c;所以非常适合判断数据在或者不在#xff0c;而且位图十分节省空间#xff0c;很适合于海量数据#xff0c;且容易存储一位图 位图是用来存放某种状态的因为一个bit上只能存0和1所以一般只有两种状态的情况下适合用位图所以非常适合判断数据在或者不在而且位图十分节省空间很适合于海量数据且容易存储数据无重复的场景因为位图是天然去重的 那我们来看一下他是如何节省空间的 我们看这个例子如果我们不使用位图一共10个整型数据需要消耗40个字节但是如果使用位图我们就只需要3个字节就可以判断这个数字是否存在
注10亿字节1个g
二)位图的实现及作用
public class bitmap {public byte[] elem;public int usedSize;public bitmap() {elemnew byte[1];}//初始化位图长度public bitmap(int n) {elemnew byte[(n/8)1];}public void setElem(int val){//找到插入第几个byte中 val/8if (val0)throw new IndexOutOfBoundsException();int arrIndexval/8;//找到插入到byte的第几个bit中 val%8int bitIndexval%8;elem[arrIndex] | (1bitIndex); //这里用| 之前为1的就一直为1当前我要插入的一定会修改为1usedSize; //这里其实不一定正确因为如果本身就存在这个元素那么我们不应该}public boolean get(int val){//找到插入第几个byte中 val/8if (val0)throw new IndexOutOfBoundsException();int arrIndexval/8;//找到插入到byte的第几个bit中 val%8int bitIndexval%8;if((elem[arrIndex] 1bitIndex)!0){ //这里是用 把其余所有位都变成0如果当前我要找的存在就不为0return true;}return false;}public void delete(int val){//找到删除第几个byte中 val/8if (val0)throw new IndexOutOfBoundsException();int arrIndexval/8;//找到删除到byte的第几个bit中 val%8int bitIndexval%8;elem[arrIndex] ~(1bitIndex);usedSize--;}
}
我们之后来看一下我们的set delete和get方法中的不同点
我们发现只有对bit位的处理是不同的找位置的代码都是一样的所以我们就来看对bit位的处理
首先是set方法我们是用了 | 只要有1就为1 这样是为了确保在我们添加元素的时候不影响其他bit位上的元素如果我们变成 就会这样
我们发现下标为5的元素被修改为0了这显然是不对的如果是异或那就更不对了 然后我们来看get 我们用了 只有都为1的时候才为1其他都是0也就是说我们想找这个元素且他存在的时候才为1其他都为0如果使用 | 我们就无法判断了
最后一个我们看delete 我们先取反然后再 这样能够保证只有这一位是0其他位全为1如果其他位本身不存在那么10还是0如果存在11为1还是存在而我们要删除的位无论如何都为0这里可能要问为什么不能使用异或异或有一个情况会发生错误如果我们删除的位置本身不存在为0那么就会导致0^1为1反倒存在了所以不可以用^ 我们可以使用我们的位图进行排序 public static void main(String[] args) {int[] array {1,3,2,13,10,3,14,18,3};final bitmap bitSet new bitmap(18);for (int tmp:array) {bitSet.setElem(tmp);}for (int i 0; i bitSet.elem.length; i) {for (int j 0; j 8; j) {if((bitSet.elem[i] (1 j) ) ! 0 ) {System.out.println(i*8j);}}}}
其实位图我们Java也给我们实现过了 但是他的底层是long类型的数组 而我们是byte类型的 那我们来总结一下位图的应用
1.快速查找某个数据适合处理整数是否在集合中
2.排序去重
3.求两个集合的交集并集
三布隆过滤器 我们上面说的位图适合存储整数如果是对象那我们要存到那一个byte位所以我们就出现了布隆过滤器 布隆过滤器是哈希和位图思想的结合
之前我们有一篇博客讲了布隆过滤器解决缓存穿透的问题 我们说布隆过滤器用于一些可以存在误判率的场景下因为布隆过滤器是通过多个哈希函数多次将数据给存放到位图上
像这样 但是因为我们在多次插入后可能会出现这种场景 我们发现不同数据hash后可能会落到同一个格子但是还好这个还有一位不同更极端点的例子 一个数据多次hash都落到了1位置上这样就会判断它存在但是它实际上是不存在的此时就会出现误判 所以布隆过滤器对于结果来说存在不一定存在不存在一定不存在
布隆过滤器的优缺点
优点
1.增加和查询元素的时间复杂度为O(1)
2.布隆过滤器不存元素本身所以适合要保密的场景
3.布隆过滤器由于使用了位图很节省空间
4.数据量很大时布隆过滤器可以表示全集也就是能表示更多的元素
5.适用相同hash函数的布隆过滤器可以进行交并差运算
缺点
1.存在一定误判率
2.不能获取元素本身hash不可逆
3.一般不能删除元素因为多个元素可能hash到一个位置上
4.这样删除会存在计数回绕问题 总结下布隆过滤器适合一些非整数的数据通过hash位图的思想查找的时间复杂度和hash函数个数有关但都是常数也不会太大存储的不是信息本身只能判断数据是否存在但是有误判率
四海量数据面试题
1.给定100亿个整数设计找到值出现一次的整数
解法一哈希切割 我们把这100亿个整数哈希到不同小文件中这样相同的数字是会在一起的然后遍历每个小文件记录只出现一次的整数到另一个文件中这样就能判断那个数字只出现一次 解法二位图 我们把这100亿个整数放到两个位图中 我们适用二进制计数的方式这样只出现一次的整数就是0 1然后我们遍历整个位图就可以得到了。 当然也可以只用一个位图那就是两个bit位存一个数据 这样我们需要/4和%4找位置了
2.给定两个文件分别有100亿个整数但是我们只有1g内存如何找到两个文件交集
解法一哈希切割
我们依然将两个文件分别hash成多个小文件这样相同的数据大概率在同一个文件中然后我们求这两个文件的交集放到另一个文件中 解法二位图
我们将第一个文件的数据放到位图中然后遍历第二个文件如果在位图中存在了那么就是两个文件的交集
3.给两个文件分别有100亿个query我们只有1g内存如何找两个文件交集给出精确算法和近似算法 注意我们这题是query那就说明不是整数那就不适合用位图但是我们可以适用布隆过滤器
解法一哈希切割精确算法
我们依然将两个文件分别hash成多个小文件这样相同的数据大概率在同一个文件中然后我们求这两个文件的交集放到另一个文件中跟上面一样 解法二近似算法
把第一个文件的query映射到布隆过滤器中然后读第二个文件把每个query都放到布隆过滤器查找有误判率所以是近似算法
那我们来总结一下哈希切割是比较通用的方法通过hash函数把相同的数据都放到一个文件中然后进行判断和处理
位图适合整型数据的处理而布隆过滤器是适合允许有一定误报率的处理
