什么网站可以自己做字,word发布wordpress,wordpress定制网页,网络管理工具布隆过滤器使用场景 之前在《数学之美》里面看到过布隆过滤器的介绍。那么什么场景下面需要使用布隆过滤器呢#xff1f; 看下下面几个问题
字处理软件中#xff0c;需要检查一个英语单词是否拼写正确在 FBI#xff0c;一个嫌疑人的名字是否已经在嫌疑名单上在网络爬虫里 看下下面几个问题
字处理软件中需要检查一个英语单词是否拼写正确在 FBI一个嫌疑人的名字是否已经在嫌疑名单上在网络爬虫里一个网址是否被访问过yahoo, gmail等邮箱垃圾邮件过滤功能以上这些场景有个共同的问题如何查看一个东西是否在有大量数据的池子里面。 通常的做法有如下几种思路
数组链表树、平衡二叉树、TrieMap (红黑树)哈希表
哈希函数 哈希函数的概念是将任意大小的数据转换成特定大小的数据的函数转换后的数据称为哈希值或哈希编码。下面是一幅示意图 可以明显的看到原始数据经过哈希函数的映射后称为了一个个的哈希编码数据得到压缩。哈希函数是实现哈希表和布隆过滤器的基础。
布隆过滤器介绍
巴顿.布隆于一九七零年提出一个很长的二进制向量 位数组一系列随机函数 (哈希)空间效率和查询效率高不会漏判但是有一定的误判率哈希表是精确匹配
布隆过滤器原理
布隆过滤器Bloom Filter的核心实现是一个超大的位数组和几个哈希函数。假设位数组的长度为m哈希函数的个数为k 以上图为例具体的操作流程假设集合里面有3个元素{x, y, z}哈希函数的个数为3。首先将位数组进行初始化将里面每个位都设置位0。对于集合里面的每一个元素将元素依次通过3个哈希函数进行映射每次映射都会产生一个哈希值这个值对应位数组上面的一个点然后将位数组对应的位置标记为1。查询W元素是否存在集合中的时候同样的方法将W通过哈希映射到位数组上的3个点。如果3个点的其中有一个点不为1则可以判断该元素一定不存在集合中。反之如果3个点都为1则该元素可能存在集合中。注意此处不能判断该元素是否一定存在集合中可能存在一定的误判率。可以从图中可以看到假设某个元素通过映射对应下标为456这3个点。虽然这3个点都为1但是很明显这3个点是不同元素经过哈希得到的位置因此这种情况说明元素虽然不在集合中也可能对应的都是1这是误判率存在的原因。
添加元素
将要添加的元素给k个哈希函数得到对应于位数组上的k个位置将这k个位置设为1
查询元素
将要查询的元素给k个哈希函数得到对应于位数组上的k个位置如果k个位置有一个为0则肯定不在集合中如果k个位置全部为1则可能在集合中简易实现
简易实现
import java.util.BitSet;/*** Created by haicheng.lhc on 18/05/2017.** author haicheng.lhc* date 2017/05/18*/
public class SimpleBloomFilter {private static final int DEFAULT_SIZE 2 24;private static final int[] seeds new int[] {7, 11, 13, 31, 37, 61,};private BitSet bits new BitSet(DEFAULT_SIZE);private SimpleHash[] func new SimpleHash[seeds.length];public static void main(String[] args) {String value stone2083yahoo.cn ;SimpleBloomFilter filter new SimpleBloomFilter();System.out.println(filter.contains(value));filter.add(value);System.out.println(filter.contains(value));}public SimpleBloomFilter() {for (int i 0; i seeds.length; i) {func[i] new SimpleHash(DEFAULT_SIZE, seeds[i]);}}public void add(String value) {for (SimpleHash f : func) {bits.set(f.hash(value), true);}}public boolean contains(String value) {if (value null) {return false;}boolean ret true;for (SimpleHash f : func) {ret ret bits.get(f.hash(value));}return ret;}public static class SimpleHash {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;}}
}
