找公司做网站需要买服务器,泰安网网站建设,抚顺网站建设技术员招聘,wordpress中文包Bloom Filter是由Bloom在1970年提出的一种多哈希函数映射的快速查找算法。通常应用在一些需要快速判断某个元素是否属于集合#xff0c;但是并不严格要求100%正确的场合。Bloom Filter是一种空间效率很高的随机数据结构#xff0c;它利用位数组很简洁地表示一个集合#xff…Bloom Filter是由Bloom在1970年提出的一种多哈希函数映射的快速查找算法。通常应用在一些需要快速判断某个元素是否属于集合但是并不严格要求100%正确的场合。Bloom Filter是一种空间效率很高的随机数据结构它利用位数组很简洁地表示一个集合并能判断一个元素是否属于这个集合。Bloom Filter的这种高效是有一定代价的在判断一个元素是否属于某个集合时有可能会把不属于这个集合的元素误认为属于这个集合(false positive)。因此Bloom Filter不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下Bloom Filter通过极少的错误换取了存储空间的极大节省。比如10亿个int类型的数如果用int数组存储的话那么需要大约4G内存浪费内存。如果用bitmap解决就比较方便。java语言中没有bitmap结构我们采用byte模拟。一个byte占8个bit如果每一个bit的值是1或0代表有或没有。下图所示构建特定长度的byte数组(new byte[capacity/8 1])其中capacity为整数数组长度(如1000个数字就是1000/8)计算数字num在byte[]中的位置索引(num/8和num 3一样)也就是说num在byte[k]中的索引计算索引k计算数字num在byte中的位置就是在byte的第几位每个byte有8位(num % 8)采用二进程与计算找到该数字存储位置后将bit中的0变成1即表示该数已存在bitmap中如图判断指定数字num是否存在数组中完整代码
