简单建站的网站,电子商务网站的功能,国外做设备网站,东莞网站设目录
位图的概念#xff1a;
位图的前置知识#xff1a;位运算
位图的实现#xff1a;
位图的基本参数和构造方法#xff1a;
位图的插入#xff1a;
位图的查找#xff1a;
位图的删除#xff1a;
布隆过滤器概念#xff1a;
布隆过滤器的实现#xff1a;
…目录
位图的概念
位图的前置知识位运算
位图的实现
位图的基本参数和构造方法
位图的插入
位图的查找
位图的删除
布隆过滤器概念
布隆过滤器的实现
布隆过滤器的基本参数
布隆过滤器的插入
布隆过滤器的查找
布隆过滤器的删除
布隆过滤器优点
布隆过滤器缺陷
布隆过滤器使用场景 前言
由于布隆过滤器是由位图实现的且这一数据结构相对其他的内容比较少故这里就把位图和布隆过滤器一起写下。
有需要本文章源码的友友可以前往位图源码 / 布隆过滤器源码
位图的概念
所谓位图就是用每一位来存放某种状态适用于海量数据整数数据无重复的场景。通常是用来判断某个数据存不存在的。❤️❤️❤️
面试题
给40亿个不重复的无符号整数没排过序。给一个无符号整数如何快速判断一个数是否在这40亿个数中。【腾讯】
方法1遍历时间复杂度O(N)
主要是内存存储不下这么大的数据故直接遍历不行。
方法2排序(O(NlogN))利用二分查找: logN
同样的内存存储不下。
方法3位图解决
可以解决数据是否在给定的整形数据中结果是在或者不在刚好是两种状态那么可以使用一个二进制比 特位来代表数据是否存在的信息如果二进制比特位为1代表存在为0代表不存在。这样就能极大的利用空间。例如10亿个字节大概是0.9G可看做是1G10亿个比特位大概是119兆看做128兆 。
位图的前置知识位运算
下面位图的实现会经常涉及到位运算故这里讲解一下下面会用到的位运算如果友友对着部分已经有所了解的话可以跳过❤️❤️❤️。大致可以分为下面三种情况。
1确定二进制表示中第x位是0还是1 这种情况我们可以将1左移k位最后将 n (1 k)即可根据结果是零还是非零不能1因为每个二进制位的权重不一样这个非常重要确定二进制表示中第x位是0还是1。
公式为 n (1 k)
2将二进制表示的第x位修改成1
不用想了这张图和上面的一样为了整齐换了个色。 图是一样的但是运算方法是不一样的这里是 n | (1 k) 。
公式为 n | (1 k)
3将二进制表示的第x位修改成0 公式为n (~(1 x))
上面三个公式可以说是位运算最基本的公式了建议大家一定要理解后记住有一些面试题就是考这个的希望友友一定要熟悉。
位图的实现
位图的基本参数和构造方法
在源码中是利用long类型的数组来实现的。
为了方便叙述我们采用byte类型数组进行叙述其实都一样的无非就是除数不一样而已。
没有给定大小的话默认给出1个字节也就是8个比特位有传入参数的话要给n / 8 1这样可能会导致多给一个字节的情况例如n 16理论只要给两个byte但是这里多给了一个没有关系的。
public byte[] elem;//利用byte数组来做private int usedSize;//表示当前位图有多少个数据/*** 默认构造方法给出1个字节。*/public MyBitSet(){elem new byte[1];}/*** 根据需要创建大小可能会多创建一个字节但是没有关系。* param n*/public MyBitSet(int n){elem new byte[n / 8 1];}位图的插入
养成好习惯如果传入一些明显不符合实际情况的值要抛一个异常。
异常的名字就根据实际情况来写异常要单独写一个类。
public class negativeException extends RuntimeException{public negativeException(){super();}public negativeException(String message){super(message);}
}
set位图的插入传入负数给出异常我们这里只写无符号整数的情况如果要实现负数的话那就要给对应的数加上值给他映射成正数的情况 。因为我们是byte数组8个字节所以除以8如果是long的话就要除以64除找到在数组中的对应下标模是找到具体的bit位。
插入元素一定一定要考虑扩容位图具有去重的作用故如果val已经存入的话直接return即可。
至于如何将对应bit位设置成1在上面位运算已经讲的很明白了这里就不再赘述。
public void set(int val){if(val 0){throw new negativeException(传入负数异常);}int arrayIndex val / 8;//计算在byte数组对应下标int bitIndex val % 8;//计算在byte数的具体哪个bit位。//插入就有可能会越界//要考虑arrayIndex越界的情况。if(arrayIndex 1 elem.length){//越界需要扩容elem Arrays.copyOf(elem,arrayIndex 1);}if((elem[arrayIndex] (1 bitIndex)) ! 0){//这个数已经存在return;}else{//这个数不存在//把这个数对应关系存入位图this.elem[arrayIndex] | (1 bitIndex);usedSize;}}
位图的查找
判断val数是否在位图中这个简单唯一注意点就是越界直接return false不用扩容。其他代码里面都有注释了。
/*** 判断val数是否在位图中* param val* return*/public boolean get(int val){if(val 0){throw new negativeException(传入负数异常);}int arrayIndex val / 8;//计算在byte数组对应下标int bitIndex val % 8;//计算在byte数的具体哪个bit位。//防止越界if(arrayIndex 1 elem.length){return false;}if((elem[arrayIndex] (1 bitIndex)) 0){//不存在return false;}else{//存在return true;}} 位图的删除
运用位图的前置知识位运算3将二进制表示的第x位修改成0来实现位图的删除具体代码如下所示
/*** 将位图中val对应关系删除* param val*/public void reSet(int val){if(val 0){throw new negativeException(负数异常);}int arrayIndex val / 8;//计算在byte数组对应下标int bitIndex val % 8;//计算在byte数的具体哪个bit位。if(arrayIndex 1 elem.length){//超过存储大小必定不存在不存在直接返回return;}else{//先判断存不存在if((elem[arrayIndex] (1 bitIndex)) ! 0){//存在elem[arrayIndex] (~(1 bitIndex));usedSize--;}}}
到这我们位图就已经学完了 下面我们将开始介绍布隆过滤器是基于位图实现的。
效果如下 布隆过滤器提出
日常生活中包括在设计计算机软件时我们经常要判断一个元素是否在一个集合中。比如在字处理软件中需要检查一个英语单词是否拼写正确也就是要判断它是否在已知的字典中在 FBI一个嫌疑人的名字是否已经在嫌疑名单上在网络爬虫里一个网址是否被访问过等等。最直接的方法就是将集合中全部的元素存在计算机中遇到一个新元素时将它和集合中的元素直接比较即可。
一般来讲计算机中的集合是用哈希表hash table来存储的。它的好处是快速准确缺点是费存储空间。当集合比较小时这个问题不显著但是当集合巨大时哈希表存储效率低的问题就显现出来了。
比如说一个像 Yahoo,Hotmail 和 Gmai 那样的公众电子邮件email提供商总是需要过滤来自发送垃圾邮件的人spamer的垃圾邮件。一个办法就是记录下那些发垃圾邮件的 email 地址。由于那些发送者不停地在注册新的地址全世界少说也有几十亿个发垃圾邮件的地址将他们都存起来则需要大量的网络服务器。
布隆过滤器概念
布隆过滤器是由布隆Burton Howard Bloom在1970年提出的一种紧凑型的、比较巧妙的概率型数据结构特点是高效地插入和查询可以用来告诉你 “某样东西一定不存在或者可能存在”它是用多个哈希函数将一个数据映射到位图结构中。此种方式不仅可以提升查询效率也可以节省大量的内存空间。 实现布隆过滤器需要多个哈希函数为了方便描述我们下面布隆过滤器的代码实现采用下面的哈希函数
利用随机种子和容量来创建不同的哈希函数可以不一样只要能区分开来就行。
class SimpleHash{private int cap;//容量private int seed;//随机种子public SimpleHash(int cap,int seed){this.cap cap;this.seed seed;}/*** 把val字符串变成一个哈希值* param val* return*/public int hash(String val){int result 0;for(int i 0;i val.length();i){result result * seed val.charAt(i);}return result (cap - 1);}
}
布隆过滤器的实现
布隆过滤器的基本参数 我们定义一个容量大小为2^24次方大小的位图将多个函数设置为数组SimpleHash[]方便调用,在调用MyBloomFilter类似通过传进构造方法的参数实现对哈希函数的初始化。
private static final int DEFAULT_SIZE 1 24;
private static final int[] seeds new int[]{5,7,11,13,31,37,61};//随机数
private BitSet bitSet;//位图
private SimpleHash[] hashFun;
public MyBloomFilter(){//创建位图bitSet new BitSet(DEFAULT_SIZE);hashFun new SimpleHash[seeds.length];//初始化哈希方法for(int i 0;i seeds.length;i){hashFun[i] new SimpleHash(DEFAULT_SIZE,seeds[i]);}
}
布隆过滤器的插入
在位图的插入时是利用多个哈希函数将得到的哈希值对应到位图位置置为1可能会存在两个不同元素哈希值相同的情况所以我们说布隆过滤器是比较巧妙的概率型数据结构它只能表明某样东西一定不存在或者可能存在。 通过多个哈希函数将对应哈希值映射到位图中。
/*** 将字符串value添加到布隆过滤器* param value*/public void set(String value){if(value null){return;}for(SimpleHash fun:hashFun){bitSet.set(fun.hash(value));}} 布隆过滤器的查找
布隆过滤器的思想是将一个元素用多个哈希函数映射到一个位图中因此被映射到的位置的比特位一定为1。 所以可以按照以下方式进行查找分别计算每个哈希值对应的比特位置存储的是否为零只要有一个为零 代表该元素一定不在哈希表中否则可能在哈希表中。
注意布隆过滤器如果说某个元素不存在时该元素一定不存在如果该元素存在时该元素可能存在因为有些哈希函数存在一定的误判。
利用位图进行查找。
/*** 判断value元素在不在布隆过滤器中可能有误判* param value* return*/public boolean contains(String value){for(SimpleHash fun:hashFun){int index fun.hash(value);if(bitSet.get(index) false){return false;}}//会有误判return true;}
效果如下 布隆过滤器的删除
布隆过滤器不能直接支持删除工作因为在删除一个元素时可能会影响其他元素。
一种支持删除的方法将布隆过滤器中的每个比特位扩展成一个小的计数器插入元素时给k个计数器(k个哈希函数计算出的哈希地址)加一删除元素时给k个计数器减一通过多占用几倍存储空间的代价来增加删除操作。
布隆过滤器优点
1增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数一般比较小)与数据量大小无关。
2哈希函数相互之间没有关系方便硬件并行运算。
3布隆过滤器不需要存储元素本身在某些对保密要求比较严格的场合有很大优势。
4在能够承受一定的误判时布隆过滤器比其他数据结构有这很大的空间优势。
5数据量很大时布隆过滤器可以表示全集其他数据结构不能。
6使用同一组散列函数的布隆过滤器可以进行交、并、差运算。
布隆过滤器缺陷
1有误判率即存在假阳性(False Position)即不能准确判断元素是否在集合中(补救方法再建立一个白名单存储可能会误判的数据)。
2不能获取元素本身。
3一般情况下不能从布隆过滤器中删除元素。
4如果采用计数方式删除可能会存在计数回绕问题。
布隆过滤器使用场景
1google的guava包中有对Bloom Filter的实现。
2 网页爬虫对URL的去重避免爬去相同的URL地址。
3垃圾邮件过滤从数十亿个垃圾邮件列表中判断某邮箱是否是垃圾邮箱。
4解决数据库缓存击穿黑客攻击服务器时会构建大量不存在于缓存中的key向服务器发起请求在数 据量足够大的时候频繁的数据库查询会导致挂机。
5秒杀系统查看用户是否重复购买。
总结布隆过滤器和位图主要是使用在大量数据的情况布隆过滤器和位图相比布隆过滤器支持存储除了整形之外的数据类型而位图只能存储整形。
结语
其实写博客不仅仅是为了教大家同时这也有利于我巩固知识点和做一个学习的总结由于作者水平有限对文章有任何问题还请指出非常感谢。如果大家有所收获的话还请不要吝啬你们的点赞收藏和关注这可以激励我写出更加优秀的文章。
