网站建设与管理培训活动总结,wordpress 管理中心,建设银行上海黄浦支行网站,沈阳建网站BitMap的存储原理
bitMap他会标识出某个整数是否存在#xff0c;存在即为1#xff0c;不存在对应位即为0bitMap是存储int类型的#xff0c;int 4byte#xff0c; 1byte 8bit#xff0c;因此bitMap数组中的每个下标可以标识出32个数字是否存在bitMap相当于一个个小格子存在即为1不存在对应位即为0bitMap是存储int类型的int 4byte 1byte 8bit因此bitMap数组中的每个下标可以标识出32个数字是否存在bitMap相当于一个个小格子底层是一个int类型数组数组的每个下标可以存储32个数字如果bitMap的长度设置为100则可以标识出100 * 32 3200 个数字是否存在假设现在有数字【0 10 24 50】那么0会保存到下标为0的那个位10会保存下标为10的位置24会保存下标是24的位置50会保存下标是50的位置即假设bitMap中第 30个位置对应值 1 则表示30这个数字是存在的bitMap不能存储【负数,float,double】等非正整数的数字。bitMap以32位的倍数出现即我们要存50这个数字则bitMap总共size就是64因为50大于32但小于64所以需要两个空间存储即size 64bitSet是java中的类型他的底层是Long存储的所以它是以64位为一个整体bitSet中每个数组位可以标识64个数字同理也不能出现【负数,fload, double】类型注意bitMap可以标识字符串和对象但是必须要先进行hash取模然后再存由于是hash取模所以存储字符串 或 对象会出现hash碰撞导致不准确的情况出现
BitMap 与 BitSet的使用场景
用户签到登录签到的用户根据自增id在对应位上打上1的标识统计uv即有多少人访问了网站把访问网站的用户id打到对应标识位上置1 最后统计bitMap中为1的个数即可领取优惠券每人只能领取1次领取的人把id打到对应bitMap位置上置1领取前根据该用户id查询bitMap是否为1如果为1则直接拒绝因为已经领取了去重比如爬虫爬取url下一个网页可能存在上一个网页的链接防止重复爬取url造成死循环可以使用布隆过滤器把爬过的网页进行hash后存到布隆过滤器每次爬到url的时候就去布隆过滤器看下是否存在 如果存在则忽略掉直接爬下一个即可
java中BitSet的使用方式及常用API
package bitmap;import java.util.BitSet;/*** 要求 有1千万个随机数分布在1 到 1亿之间需要找出1 到 1亿不存在的数据即随机剩下的9千万数据** 使用java的bitSet集合** bitSet是Long类型每一个组是64bit* bitMap是int类型每一个组32bit** 注意bitSet不能存负数只能存0以上的并且在Long类型范围内的正整数*/
public class BitSetTest {public static void main(String[] args) {// 这个初始化128会在里面生成一个128个桶的Long类型的数组所以一共有128 * 64 个bit位也就是一共能标记出128 * 64个整数是否存在// 不指定默认64BitSet bitSet new BitSet(128);bitSet.set(0);bitSet.set(66);// 输出bitSet大小应该是128因为66大于64所以需要第二个Long位每个Long位是642个就是128System.out.println(bitSet大小: bitSet.size());// 这个是bit位的长度是最大的那个数字1即67System.out.println(bitSet长度: bitSet.length());// 查询出有多少个为1的位显然我们只存了0和66只有俩所以结果就是2System.out.println(bitSet中存在多少数字 bitSet.cardinality());// 读取bit位 0的下标 返回true说明存数据了即该位的值 1因为bitSet.set(0)// 把0存到了第0位这是必然的0一定是存到下标位0的位置这是规则不需要认为指定System.out.println(0是否存在: bitSet.get(0));// 读取bit位 1的下标返回false 说明该位没有存数据即没有存数字1所以该位的值 0 表示1这个数字不存在System.out.println(1是否存在: bitSet.get(1));System.out.println(66是否存在: bitSet.get(66));}
}
输出
布隆过滤器
布隆过滤器可以支持多种类型而bitSet 和 bitMap只能支持正整数布隆过滤器本身不支持删除元素因为可能出现好几个值由于hash碰撞都存到了同一个格子如果删除可能会影响到其他元素。当然可以把布隆过滤器改造成带有计数的效果即如果某个格子计数是1即只有一个元素占有这个位置这个时候就可以删除布隆过滤器保存某个值的时候可以通过多次hash比如把java进行3次不同的hash算法取模会得到3个不同的hash值那么这3个值都会保存到布隆过滤器对应的位中即java这个值会被存到3个位置这3个位置都标记这java的hash布隆过滤器说没有那一定就不存在但是布隆过滤器说存在那未必真的存在因为可能发生hash碰撞导致你要查的元素hash的值和别的元素hash值相同了这个时候布隆过滤器会误判成存在
布隆过滤器是如何降低误判
保存元素时会对该元素去多个hash值把这些hash值全部存到布隆过滤器中(比如要存java 进行3次hash后值分别是【2,10,26】, 那么java这个值就会被同时存储到【2, 10, 26】的位置)当要查询一个元素是否存在时会以同样的hash算法计算出3个值然后用这3个值去布隆过滤器的对应3个位置去找如果这3个位置有一个位置是0则直接判该值不存在(假如之前只存了java 现在要查询web这个字符串是否存在 那么会以同样的hash算法对web进行3次hash取模假如取到的是【2, 15, 26】, 会发现15这个位置是0此时直接回判定web不存在尽管2, 26都有但15没有就说明web不存在)当布隆过滤器中的bit格子被逐渐被占满时候此时即使hash取3个值依然会有大概率误判因为可能hash出来的3个值都和其他元素发生hash碰撞了(比如要查询cloud, 取模是【10, 15, 26】, 而布隆过滤器并没有cloud 而10, 15, 26却都是1因为与java, “web发生hash碰撞了所以会误判cloud也存在而实际却并不存在cloud”)
布隆过滤器(BloomFilter)和位图(bitMap)的区别
BitMap的每个位只会存储1个元素的标识而bloomFilter可以标识多个元素因为1个元素会hash出多个值并存到多个位BitMap只能存int类型而bloomFilter可以存储多种类型原理是通过hash取模的方式所以String存在hash碰撞BitMap的每个元素会消耗1个bit来存储而BloomFilter通常来说会小于1bit因为每个位可能会存储多个元素那么平摊下来每个元素就小于1bit当然如果元素很少那1个元素会占用3个bit那就更多了。
