布隆过滤器 (Bloom Filter) 的 Java 实现方法
这里有新鲜出炉的 Java 函数式编程, 程序狗速度看过来!
Java 程序设计语言
java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言, 是由 Sun Microsystems 公司于 1995 年 5 月推出的 Java 程序设计语言和 Java 平台 (即 JavaEE(j2ee), JavaME(j2me), JavaSE(j2se)) 的总称
下面小编就为大家带来一篇布隆过滤器 (Bloom Filter) 的 Java 实现方法小编觉得挺不错的, 现在就分享给大家, 也给大家做个参考一起跟随小编过来看看吧
布隆过滤器原理很简单: 就是把一个字符串哈希成一个整数 key, 然后选取一个很长的比特序列, 开始都是 0, 在 key 把此位置的 0 变为 1; 下次进来一个字符串, 哈希之后的值 key, 如果在此比特位上的值也是 1, 那么就说明这个字符串存在了
如果按照上面的做法, 那就和哈希算法没有什么区别了, 哈希算法还有重复的呢
布隆过滤器是将一个字符串哈希成多个 key, 我还是按照书上的说吧
先建立一个 16 亿二进制常量, 然后将这 16 亿个二进制位全部置 0 对于每个字符串, 用 8 个不同的随机产生器 (F1,F2,.....,F8) 产生 8 个信息指纹(f1,f2,....,f8). 再用一个随机数产生器 G 把这八个信息指纹映射到 1 到 16 亿中的 8 个自然数 g1,g2,...,g8 现在把这 8 个位置的二进制位全部变为 1 这样一个布隆过滤器就建好了
那么如何检测一个字符串是否已经存在了呢?
现在用 8 个随机数产生器 (F1,F2,...,F8) 对这个字符串产生 8 个信息指纹 s1,s2,...,s8, 然后将这 8 个信息指纹对应到布隆过滤器的 8 个二进制位, 分别是 T1,T2,...,T8. 如果字符串存在, 那么显然 T1,T2,...,T8 对应的二进制位都应该是 1 就是这样来判断字符串是否已经存在的
其实布隆过滤器就是对哈希算法的一个扩展, 既然本质是哈希, 那么就肯定会有不足, 也就是说, 肯定会有误判, 一个字符串明明没有出现过而布隆过滤器判断出现了, 虽然可能性很小, 但是确实存在
那么如何减少这种概率呢, 首先可以想到的是如果将 8 个信息指纹扩展到 16 个错误的概率肯定会降低, 但是也要考虑到, 这样的话, 那么一个布隆过滤器所能存储的字符串数量也降低了 1 倍; 另外就是选取很好的哈希函数, 对字符串的哈希方法有很多种, 其中不乏很好的哈希函数
布隆过滤器主要运用在过滤恶意网址用的, 将所有的恶意网址建立在一个布隆过滤器上, 然后对用户的访问的网址进行检测, 如果在恶意网址中那么就通知用户这样的话, 我们还可以对一些常出现判断错误的网址设定一个白名单, 然后对出现判断存在的网址再和白名单中的网址进行匹配, 如果在白名单中, 那么就放行当然这个白名单不能太大, 也不会太大, 布隆过滤器错误的概率是很小的有兴趣的读者可以去查阅, 布隆过滤器的错误率
下面给出 Java 版的布隆过滤器源码:
- import java.util.BitSet;
- /**
- *
- * @author xkey
- */
- public class BloomFilter {
- private static final int DEFAULT_SIZE = 2 << 24;// 布隆过滤器的比特长度
- private static final int[] seeds = {3,5,7, 11, 13, 31, 37, 61};// 这里要选取质数, 能很好的降低错误率
- private static BitSet bits = new BitSet(DEFAULT_SIZE);
- private static SimpleHash[] func = new SimpleHash[seeds.length];
- public static void addValue(String value)
- {
- for(SimpleHash f : func)// 将字符串 value 哈希为 8 个或多个整数, 然后在这些整数的 bit 上变为 1
- bits.set(f.hash(value),true);
- }
- public static void add(String value)
- {
- if(value != null) addValue(value);
- }
- public static boolean contains(String value)
- {
- if(value == null) return false;
- boolean ret = true;
- for(SimpleHash f : func)// 这里其实没必要全部跑完, 只要一次 ret==false 那么就不包含这个字符串
- ret = ret && bits.get(f.hash(value));
- return ret;
- }
- public static void main(String[] args) {
- String value = "www.phperz.com";
- for (int i = 0; i < seeds.length; i++) {
- func[i] = new SimpleHash(DEFAULT_SIZE, seeds[i]);
- }
- add(value);
- System.out.println(contains(value));
- }
- }
- class SimpleHash {// 这玩意相当于 C++ 中的结构体
- private int cap;
- private int seed;
- public SimpleHash(int cap, int seed) {
- this.cap = cap;
- this.seed = seed;
- }
- public int hash(String value) {// 字符串哈希, 选取好的哈希函数很重要
- int result = 0;
- int len = value.length();
- for (int i = 0; i < len; i++) {
- result = seed * result + value.charAt(i);
- }
- return (cap - 1) & result;
- }
- }
总结: 布隆过滤器是对哈希算法的一种创新, 而且需要消耗的空间也很小, 错误率很低总之这种创新的思路很值得学习, 是一种对 bit 这种数据类型的运用
以上这篇布隆过滤器 (Bloom Filter) 的 Java 实现方法就是小编分享给大家的全部内容了, 希望能给大家一个参考, 也希望大家多多支持 PHPERZ
来源: http://www.phperz.com/article/18/0207/359216.html