刘强东发飙,上网干什么好,三星智力快车题库
BloomFilter主要包括两种操作：
add()：添加元素到其中
contains()：判断一个元素是否在其中,（没有就是没有，说了有但实际上有可能没有）
关于contains()函数：
①，如果结果返回false：则元素一定不再其中
②，如果返回true，则不一定就在其中，这就是误差
BloomFilter实现（m(byte数组的大小)+k（hash次数）+n(需要存储的数据量)）byte映射,多个hash函数
既然涉及到byte存储，那么必然需要一种映射关系了，也就是需要知道一个元素用哪些byte来表示，这也就是hash函数所干的事情。直观地想，一个元素一个byte基本上不可能，一般情况下这样的hash函数可以说不存在，所以这里假设用k位来表示，一般采用k次hash来确定这些byte。实际上，BloomFilter中一般包含m(byte数组的大小),k（hash次数）和n(需要存储的数据量)。 在元素加入实现add()操作时，连续k次hash，将得到的对应k位全置为1。当查询元素是否在集合中时，也是连续k次hash，如果这k次得到的位不是全为1，那么返回false；否则返回 true。传统的算法优化都是以时间换空间或者以空间换时间，BloomFilter则是以正确率换空间。
原文链接：https://bjyjtdj.iteye.com/blog/1455029
-------------------------------------------------------------------------------------------------------------------------------
BloomFilter简单的java例子实现;
package com.me;
import java.util.BitSet;
//BloomFilter主要有两种操作：add()，contains()
public class BloomFilter {
private int defaultSize = 2 << 20;
private int basic = defaultSize - 1;
private BitSet bitSet;
public BloomFilter() {
bitSet = new BitSet(defaultSize);
}
// 将元素加入其中，
public void add(String url) {
if (url == null) {
return;
}
int key1 = hashA(url);
int key2 = hashB(url);
int key3 = hashC(url);
bitSet.set(key1);
bitSet.set(key2);
bitSet.set(key3);
}
// 判断一个元素是不是在其中
public boolean contains(String url) {
if (url == null) {
return true;
}
int key1 = hashA(url);
int key2 = hashB(url);
int key3 = hashC(url);
if (bitSet.get(key1) && bitSet.get(key2) && bitSet.get(key3)) {
return true;
}
return false;
}
private int check(int speed) {
return basic & speed;
}
public boolean ifNotContainsSet(String url) {
if (url == null) {
return true;
}
int key1 = hashA(url);
int key2 = hashB(url);
int key3 = hashC(url);
if (bitSet.get(key1) && bitSet.get(key2) && bitSet.get(key3)) {
return true;
}
bitSet.set(key1);
bitSet.set(key2);
bitSet.set(key3);
return false;
}
private int hashA(String url) {
int speed = 0;
for (int i = 0; i < url.length(); i++) {
speed = 13 * speed + url.charAt(i);
}
return check(speed);
}
private int hashB(String url) {
int speed = 0;
for (int i = 0; i < url.length(); i++) {
speed = 23 * speed + url.charAt(i);
}
return check(speed);
}
private int hashC(String url) {
int speed = 0;
for (int i = 0; i < url.length(); i++) {
speed = 34 * speed + url.charAt(i);
}
return check(speed);
}
public static void main(String[] args) {
String bd = "https://www.baidu.com";
BloomFilter bloomFilter = new BloomFilter();
//not contains
String tb = "https://www.taobao.com";
System.out.println(bloomFilter.contains(tb));
//if not contains then add
System.out.println(bloomFilter.contains(bd));
bloomFilter.add(bd);
System.out.println(bloomFilter.contains(bd));
//if not contains then set (ifNotSet)
String gg = "https://www.google.com";
System.out.println(bloomFilter.ifNotContainsSet(gg));
System.out.println(bloomFilter.contains(gg));
}
}
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
Net Core Web Api项目与在NginX下发布的方法
asp.net core3.1 引用的元包dll版本兼容性问题解决方案
IdentityServer4实现.Net Core API接口权限认证(快速入门)
ASP.NET Core MVC通过IViewLocationExpander扩展视图搜索路径的实现
我要评论
网友评论