昆明网站开发报价,安徽省教育局网站建设方案,湛江人做寄生虫网站,网站如何进行优化位图
引入问题#xff1a;给40亿个不重复的无符号整数#xff0c;没排过序。给一个无符号整数#xff0c;如何快速判断一个数是否在这40亿个数中。
首先要注意 40 亿个数据如果使用 整型#xff08;int) 来存放的话#xff0c;就是要 40 亿个整型#xff0c;一个整型有…位图
引入问题给40亿个不重复的无符号整数没排过序。给一个无符号整数如何快速判断一个数是否在这40亿个数中。
首先要注意 40 亿个数据如果使用 整型int) 来存放的话就是要 40 亿个整型一个整型有4个字节一个字节有8个比特位我们换算一下40亿个字节差不多需要 15 GB 来存储我们可以这样简便的记忆 10亿 个字节约等于 1GB
一般情况下大家的电脑运行内存为 16GB 或者 更大的 32GB但是我们不可能真的把这40亿 的整型数据存储进去我们的电脑运行内存还有其他应用程序也占用着所以我们就要想办法去缩小存储空间这时候就可以考虑位图了
概念
位图就是用每一位来存放某种状态适用于海量数据整数数据无重复的场景。通常是用来判 断某个数据存不存在的。
位图并不是将数据存储进去而是将这个数据的状态存储进去即该数据存在或者不存在位图利用比特位的 0 与 1 来表示数据的状态通过映射关系来进行存储与读取。
举个例子 这是位图的初始状态 位图上面的红色 7 ~ 0 的数字大家可以自行定义顺序可以逆序也可以顺序只是映射关系不同我这里使用的是逆序 我们来插入数据使用映射关系使用除法式子确定下标取模来确定具体的比特位
模拟实现
成员变量这里我使用字节数组 byte[] 来模拟位图源码底层是使用 long[] 然后再加上一个统计目前元素个数的成员变量 useSize.
提供两个构造方法注意带参数的构造方法是为了让用户自行设置大小但是用户设计的是元素的多少而实际我们每次开辟一个字节就可以保存 8 个元素这里要注意换算关系。 public MyBitSet() {this.elem new byte[1];}public MyBitSet(int size) {if(size 0) {throw new IndexOutOfBoundsException(设置的大小无效);}int num size / 8 1;this.elem new byte[num];}在存储数据的时候先通过映射关系来确定下标如果下标越界数据就要扩容然后再存储数据这里该如何存储数据我们可以让 1 左移 val % 8 个位置这样就可以对齐到这个数据的具体的比特位然后我们再考虑使用什么位运算符来进行计算如果比特位本身为1说明再次存储相同的数据还是为 1 从这里就可以看出位图无法存储相同的数据有去重的功能如果比特位原本为 0 那插入数据之后就要变成 1 可以看出 这里要使用的是 或运算| public void set(int val) {int index val / 8;if(index elem.length) {elem Arrays.copyOf(elem, (index 1) * 2);}elem[index] | 1 (val % 8);useSize;}是否存在某个元素 这里要注意的是要使用的是 运算符 public boolean get(int val) {int index val / 8;if(index elem.length) {return false;}if((elem[index] (1 (val % 8))) 0) {return false;}return true;}删除 删除元素的时候要注意是只删除对应的元素如果该元素存在对应的比特位为 1先按位取反 (1 (val % 8)) 然后再与运算这样就可以删除成功了。 public boolean remove(int val) {int index val / 8;if(index elem.length) {return false;}elem[index] (~(1 (val % 8)));useSize--;return true;}获取元素个数 public int size() {return useSize;}最终代码
public class MyBitSet {private byte[] elem;private int useSize;public MyBitSet() {this.elem new byte[1];}public MyBitSet(int size) {if(size 0) {throw new IndexOutOfBoundsException(设置的大小无效);}int num size / 8 1;this.elem new byte[num];}public void set(int val) {int index val / 8;if(index elem.length) {elem Arrays.copyOf(elem, (index 1) * 2);}elem[index] | (1 (val % 8));useSize;}public boolean get(int val) {int index val / 8;if(index elem.length) {return false;}if((elem[index] (1 (val % 8))) 0) {return false;}return true;}public boolean remove(int val) {int index val / 8;if(index elem.length) {return false;}elem[index] (~(1 (val % 8)));useSize--;return true;}public int size() {return useSize;}
}BitSet
在java.util这个包下有一个 BitSet 的类这个就是Java提供给我们的位图的数据结构
方法说明BitSet()无参的构造方法BitSet(int nbits)可以设置位图的大小void set(int bitIndex)插入数据boolean get(int bitIndex)查看数据是否存在int size()位图存放的元素总数
位图的应用
快速查找某个数据是否在一个集合中排序 去重求两个集合的交集、并集等操作系统中磁盘块标记 排序是因为位图存放的数据已经有序我们只需要遍历位图依次打印出数据即为有序。 布隆过滤器
布隆过滤器是由布隆Burton Howard Bloom在1970年提出的 一种紧凑型的、比较巧妙的概率型数据结 构特点是高效地插入和查询可以用来告诉你 “某样东西一定不存在或者可能存在”它是用多个哈希函 数将一个数据映射到位图结构中。此种方式不仅可以提升查询效率也可以节省大量的内存空间。
引用场景 一个像 Yahoo,Hotmail 和 Gmai 那样的公众电子邮件email提供商总是需要过滤来自发送垃 圾邮件的人spamer的垃圾邮件。一个办法就是记录下那些发垃圾邮件的 email 地址。由于那些发送者 不停地在注册新的地址全世界少说也有几十亿个发垃圾邮件的地址将他们都存起来则需要大量的网络服 务器。
如果用哈希表每存储一亿个 email 地址 就需要 1.6GB 的内存用哈希表实现的具体办法是将每一个 email 地址对应成一个八字节的信息指纹,然后将这些信息指纹存入哈希表由于哈希表的存储效率一般只有 50%因此一个 email 地址需要占用十六个字节。一亿个地址大约要 1.6GB 即十六亿字节的内存。因此 存贮几十亿个邮件地址可能需要上百 GB 的内存。除非是超级计算机一般服务器是无法存储的。
小结
用哈希表存储用户记录缺点浪费空间用位图存储用户记录缺点位图一般只能处理整形如果内容编号是字符串就无法处理了。将哈希与位图结合即布隆过滤器
插入
布隆过滤器的思想是将一个元素用多个不同的哈希函数映射到一个位图中因此被映射到的位置的比特位一定为1 具体使用多少个哈希函数是可以通过数学进行计算的。并且哈希函数的设置也是有规定的作为开发人员我们就使用就可以了。 查找
分别计算每个哈希值对应的比特位置存储的是否为零只要有一个为零代表该元素一定不在哈希表中否则可能在哈希表中。 注意布隆过滤器如果说某个元素不存在时该元素一定不存在如果该元素存在时该元素可能存在因 为有些哈希函数存在一定的误判。 举个例子如果一个字符串通过不同的哈希函数映射到的位置分别为 034刚好和 上面的 world 重合但是这个字符串却本身不存在只是正好哈希值和另一个元素重合所以可能会存在误判
删除
传统的布隆过滤器不能直接支持删除工作因为在删除一个元素时可能会影响其他元素。
一种支持删除的方法将布隆过滤器中的每个比特位扩展成一个小的计数器插入元素时给k个计数器(k个哈希函数计算出的哈希地址)加一删除元素时给k个计数器减一通过多占用几倍存储空间的代价来增加删除操作。 缺陷
无法确认元素是否真正在布隆过滤器中【会有误判】存在计数回绕【回绕意思为溢出】
模拟实现
class SimpleHash {public int cap;//当前容量public int seed;//随机值public SimpleHash(int cap,int seed) {this.cap cap;this.seed seed;}//根据seed不同 创建不能的哈希函数int hash(String key) {int h;return (key null) ? 0 : (seed * (cap-1)) ((h key.hashCode()) ^ (h 16));}}public class BloomFilter {//默认大小public static final int DEFAULT_SIZE 1 20;//位图public BitSet bitSet;//记录存了多少个数据public int usedSize;public static final int[] seeds {5,7,11,13,27,33};public SimpleHash[] simpleHashes;public BloomFilter() {bitSet new BitSet(DEFAULT_SIZE);simpleHashes new SimpleHash[seeds.length];for (int i 0; i simpleHashes.length; i) {simpleHashes[i] new SimpleHash(DEFAULT_SIZE,seeds[i]);}}public void set(String val) {for (int i 0; i simpleHashes.length; i) {int hash simpleHashes[i].hash(val);bitSet.set(hash);}usedSize;}public boolean get(String val) {for (int i 0; i simpleHashes.length; i) {int hash simpleHashes[i].hash(val);if(!bitSet.get(hash)) {return false;}}return true;}public int size() {return usedSize;}
}布隆过滤器优点
增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数一般比较小)与数据量大小无关哈希函数相互之间没有关系方便硬件并行运算布隆过滤器不需要存储元素本身在某些对保密要求比较严格的场合有很大优势在能够承受一定的误判时布隆过滤器比其他数据结构有这很大的空间优势数据量很大时布隆过滤器可以表示全集其他数据结构不能使用同一组散列函数的布隆过滤器可以进行交、并、差运算
布隆过滤器缺陷
有误判率即存在假阳性(False Position)即不能准确判断元素是否在集合中(补救方法再建立一个白名单存储可能会误判的数据)不能获取元素本身一般情况下不能从布隆过滤器中删除元素如果采用计数方式删除可能会存在计数回绕问题
布隆过滤器使用场景
google的guava包中有对Bloom Filter的实现网页爬虫对URL的去重避免爬去相同的URL地址。垃圾邮件过滤从数十亿个垃圾邮件列表中判断某邮箱是否是垃圾邮箱。解决数据库缓存击穿黑客攻击服务器时会构建大量不存在于缓存中的key向服务器发起请求在数 据量足够大的时候频繁的数据库查询会导致挂机。秒杀系统查看用户是否重复购买。
海量数据处理
哈希切割
给一个超过 100G 大小的log file,log 存在log中存着IP地址, 设计算法找到出现次数最多的IP地址 与上题条件相同如何找到top K的IP 答使用哈希切割将这个大文件通过哈希切割分成若干个小文件每一个小文件只存储一个IP地址剩下的就简单了。 位图应用
1.给定100亿个整数设计算法找到只出现一次的整数 答解法一使用哈希切割将数字哈希到对应的小文件中 解法二使用两个位图bitSet1 和 bitSet2,当插入数据的时候先检查 bitSet1 的比特位是否为0是则变为1不是则在 bitSet2插入这样的话我们还可以进一步划分当 bitSet1 为0 、bitSet2 也为0 时则该数据重未出现过 当 bitSet1 为0 、bitSet2 也为0 时则该数据出现过一次 当 bitSet1 为0 、bitSet2 也为0 时则该数据出现过两次 当 bitSet1 为0 、bitSet2 也为0 时则该数据出现过三次及以上 解法三使用一个位图这时候我们可以利用解法二将两个比特位表示一个数据的状态 这样的话就不能直接使用Java 提供的位图了我们需要自己手动搓一个位图映射关系也要修改。 举个例子如果插入数据 4 4 / 4 1 说明要插入到 数组的 1 下标4 % 4 * 2 0说明要修改的是 0 号位置与 1 号位置 所以这时候映射关系应该为 index num / 4 i num % 4 * 2 2.给两个文件分别有100亿个整数我们只有1G内存如何找到两个文件交集 答解法一使用哈希切割 解法二使用一个位图遍历第一个文件将数据保存到 bitSet1 ,遍历第二个文件在遍历第二个文件的同时检查数据是否也出现在 bitSet1 或者使用两个位图分别保存两个文件的数据然后将两个位图按位与 拓展 并集两个位图按位或 | 差集差集 的概念是所有属于A且不属于B的元素构成的集合这里指属于位图1但不属于位图2 和 属于位图2但不属于位图1 的元素集合那么将位图1 按位异或 ^ 位图2 3.位图应用变形1个文件有100亿个int1G内存设计算法找到出现次数不超过2次的所有整数 答解法一使用哈希切割 解法二使用两个位图 解法三使用一个位图两个比特位表示一个整数的状态 布隆过滤器应用
1.给两个文件分别有100亿个query我们只有1G内存如何找到两个文件交集分别给出精确算法和 近似算法 精确算法使用哈希切割或者两个位图 近似算法使用布隆过滤器先将第一个文件存储进布隆过滤器中再遍历第二个文件同时查看布隆过滤器。 2.如何扩展BloomFilter使得它支持删除元素的操作 布隆过滤器中的每个比特位扩展成一个小的计数器删除的时候计数器减1
