「java布隆过滤器代码」布隆过滤器 python
今天给各位分享java布隆过滤器代码的知识，其中也会对布隆过滤器 python进行解释，如果能碰巧解决你现在面临的问题，别忘了关注本站，现在开始吧！
本文目录一览：
细嚼慢咽布隆过滤器(Bloom Filter)
在上篇【链接】中，我们借助 Java 的 BitSet 源码尝试着理解了下 BitMap 算法，但是有一个很致命的劣势没有解决，那就是很尴尬的 数据碰撞问题 。
啥意思呢，再次解释一下下，BitMap 中我们只是很简单地初始化了一个 Long 数组，然后使用一个个小小的 bit 位来表示一个数据的存在与否，但是其中必然会面对 哈希碰撞 问题。
我们画张简图来回顾下 BitMap 算法。
如上图所示，hash function 均为 f1，数据 A 和 D 指向的位是 1 ，所以肯定是存在的，而 B 和 C 指向的都是同一个位，所以哈希碰撞就是这样很容易地产生了。
即：位上无元素则表示该数据肯定不存在，位上有元素则只能表示该数据 可能存在 。
有弊端总有解决之道，此处正好引入本文主要介绍的一种算法： 布隆过滤器 ，英文名为 Bloom Filter ，下文简称 BF 算法。
同样，我们还是先画一张简图来直观地认识下 BF 算法。
由上图我们可以看出，此时的 A、B、C、D 四个数据各自经过 f1 和 f2 方法进行两次 hash 算法，然后分别指向位上面，只有当 f1 和 f2 指向的位上面都为 1 时，才会标记为存在。
小结：BF 算法虽然在一定程度上减少了 BitMap 算法中的哈希碰撞，但是终言之，只是减少而已，没法完全避免，就像上文举的案例2一样。
通过上面的图，其实很容易看出，上图中 hash function 的数量是 2，假如我们计算 3 次呢？或者 4 次甚至更多呢？诚然这可以更进一步避免数据的碰撞问题，但是太多的话却适得其反。
所以介绍优化之前我们先小结下 BF 算法的劣势，因为优化都是基于某些劣势来进行的：
所以，针对上面的两个点，我们逐个来突破下：
1、关于误判率
BF 算法优劣的影响因素，其实很容易就可以联想到，一个是根据插入的数据总量（n）来计算出最合适的位数组的大小（m）和 hash 函数的个数（k），还有一个便是最优的 误判率 （使用 P(error) 表示）的选择问题。
比如：我们假设 P 为 0.01，此时最优的 m 应大概是 n 的 13 倍，而 k，应大概为 8。
详细的证明过程见下文。
2、关于元素删除的需求
因为数据对应的位会牵动其它的数据，所以 BF 是不可以删除位数据的，那么如果有这样的需求呢？可以使用 couting Bloom Filter 来解决，大致思路就是使用一个 counter 数组来代替位数组。
什么意思呢？简言之就是在原来的 BF 算法的位上面，不再是用简单的 0 或 1 来表示了，而是存储该位上面的数据总量，比如有两个数据经过 hash function 计算都有指向同一个位，则将该位标记为2，代表有两个数据，当删除其中一个数据时，只需要将该位上面的 2 调整为 1 即可，如此便不再影响其它数据的正确性。
BF 算法虽然有着一定的缺点（主要是误判率），但是它的优点更为突出，所以应用场景也是很广的。
比如我们在爬虫业务下，有很多的 URL，我们可以通过 BF 算法来判断每个 URL 是否已经被我们的爬虫程序处理过。
再比如邮箱服务中垃圾邮件的过滤策略，由于垃圾邮件是海量的，我们不可能使用一个很完整的散列映射来标记每一个垃圾邮箱的地址，此处可以使用 BF 算法来标记，从而节约了容量。
另外，BF 算法在很多开源框架中也都有相应的实现，例如：
1、误判概率的证明和计算
假设布隆过滤器中的hash function满足simple uniform hashing假设：每个元素都等概率地hash到m个slot中的任何一个，与其它元素被hash到哪个slot无关。若m为bit数，则对某一特定bit位在一个元素由某特定hash function插入时没有被置位为1的概率为：
现在考虑query阶段，若对应某个待query元素的k bits全部置位为1，则可判定其在集合中。因此将某元素误判的概率为：
从上式中可以看出，当m增大或n减小时，都会使得误判率减小，这也符合直觉。 现在计算对于给定的m和n，k为何值时可以使得误判率最低。设误判率为k的函数为：
下面求最值：
这说明了若想保持某固定误判率不变，则布隆过滤器的 位数 m 与添加的元素数 n 应该是线性同步增加的。
2、设计和应用布隆过滤器的方法
应用时首先要先由用户决定添加的元素数 n 和期望的误差率 P。这也是一个设计完整的布隆过滤器需要用户输入的仅有的两个参数，之后的所有参数将由系统计算，并由此建立布隆过滤器。
系统首先要计算需要的内存大小 m bits:
这里需要特别注意的是，9.6 bits/element 不仅包含了被置为1的 k 位，还把包含了没有被置为1的一些位数。此时的
此概率为某 bit 位在插入 n 个元素后未被置位的概率。因此，想保持错误率低，布隆过滤器的空间使用率需为 50%。
代码比较长，文章中暂不完整展示，更完整的代码 demo 详见【链接】。
下面列出了一小部分代码块，作用是根据插入的元素数量和过滤器容器的大小来计算实际的误报率：
java filter 过滤器中文乱码 怎么解决啊？
1、首先编写一个Java类的filter代码。操作步骤：
(1)在myeclipse中新建一个java类，
(2)单击“Add”按钮，在弹出来的对话框中“选择接口”文本框中输入Filter，
并选择匹配好的类型javax.servlet
(3)单击“OK”按钮返回"New Java Class"对话，然后单击“Finish”按钮，就可以看到创建的过滤器框架:
过滤器类：Encoding.java,代码如下:
package com;
import java.io.IOException;
import javax.servlet.*;
public class Encoding implements Filter {
protected String encoding=null;
protected FilterConfig config;
public void destroy() {
// TODO Auto-generated method stub
}
public void doFilter(ServletRequest request, ServletResponse response,
FilterChain chain) throws IOException, ServletException {
if(request.getCharacterEncoding()==null){
//得倒指定的编码
String encode=getEncoding();
if(encode!=null){
//设置request的编码
request.setCharacterEncoding(encode);
response.setCharacterEncoding(encode);
}
}
chain.doFilter(request, response);
}
public void init(FilterConfig filterConfig) throws ServletException {
this.config=filterConfig; //得到web.xml中的配置编码
this.encoding=filterConfig.getInitParameter("Encoding");
}
protected String getEncoding(){
return encoding;
}
}
2、在web.xml文件写入以下代码：
?xml version="1.0" encoding="UTF-8"?
web-app version="2.5"
xmlns=""
xmlns:xsi=""
xsi:schemaLocation="
"
display-name/display-name
filter !-- 控制编码 --
filter-nameEncodingFilter/filter-name
filter-classcom.Encoding/filter-class
init-param !-- 初始化参数 --
param-nameEncoding/param-name
param-valueGB2312/param-value
/init-param
/filter
filter-mapping
filter-nameEncodingFilter/filter-name
url-pattern/*/url-pattern
/filter-mapping
/web-app
布隆过滤器
[TOC]
通过解决方案：
Java中如将数据存储在内存中，最简单的算法结构是HashMap。通过HashMap判断key是否存在，来判断数据是否存在。通过hash算法查找元素，时间复杂度基本是 O(1) （可能存在hash冲突后转换成链表或红黑树的情况，时间复杂度的影响可以忽略）。
使用HashMap速度很快，存储简单，绝大部分场景可以使用。但是HashMap 占用的空间比较大 ：
为什么出现布隆过滤器：
举例：
如1000万个Integer存储在内存中，占用空间为：4x32x10000000位，即1220兆。如布隆过滤器通过4字节存储（布隆过滤器通过多次hash对数据计算后--几次hash根据数据量指定，得到多个数据， 占用多个位 ），则占用空间为610M。比原有空间少一半。
个人觉得，此比较在字符等的比较中尤为有效。
一个字符串多个字符，根据编码方式，一个字符两个或三个字节，如10个字符，字符串存储占用20个字节，还有相关字符串相关的类信息的内存占用。
位存储，根据数据量的大小，hash的位数，灵活计算。如4个字节，则是原hashMap占用空间的五分之一。
（1）定义字节向量
先定义一个指定长度的字节数组（字节数组，数组内每个元素的值）。
如长度为8（一个字节大小），默认所有元素值均为0，如下：
（2）计算哈希值
将要写入过滤器的数据，根据一定数量的哈希函数，得到多个哈希值，再依次判断每个哈希值对应的索引。
如使用3个哈希函数，计算得到3个哈希值，判定哈希值对应的字节向量为为1，3，7。
（3）更新字节向量
将计算出的字节向量的索引， 对应的字节向量中的元素值更高为1 （无论之前为0或者为1，均更改为1）。如下：
（1）计算哈希值
将要判断过滤器中是否存在的数据，根据一定数量的哈希函数，得到多个哈希值，再依次判断每个哈希值对应的索引。
如使用3个哈希函数，计算得到3个哈希值，判定哈希值对应的字节向量为为1，3，7。
注意：哈希函数的判断方式和计算索引的方式，需和写入数据时完全一致。
（2）判断是否存在
如原字节数组中，对应1，3，7中存在的元素的值都为1。则判定为此元素 可能存在 ，但凡有一个元素的值不为1，则判定此元素 一定不存在 。
布隆过滤器，主要需实现的目标是， 在指定的数据个数范围内，满足误判率在设定的范围内 ，误判率太高的话，无法起到过滤数据的情况，误判率不能为0。
因此需要计算两个数据来满足 存储数据的个数 和 误判率 ：
使用布隆过滤器的决定性因素之一，就是此算法插入数据和查询数据的速度必须非常快。因此在对数据进行哈希运算的时候， 需选择计算快的哈希算法 。
而且， 写入数据以及查询数据的哈希算法，顺序和算法都需完全一致 。
待完善。。。。。
可以通过google的 guava ，在内存中轻松实现布隆过滤器。
无需手动计算满足字节数组的长度和哈希个数，只需要输入 拟输入数据的个数 和 期望误判率 即可。
不输入期望误判率的情况下，误判率为0.03，即100个非范围内的数据进行校验时，约三个数据会判定为存在。
多次执行，结果一致，根据结果判定：
内存的存储存在局限性，可以使用redis中的bitMap来实现字节数组的存储。
使用redis实现布隆过滤器。需要根据公式，手动计算字节数组的长度和哈希的个数。
实现过程，待完善。。。。。。
基于布隆过滤器的非法URL识别，有没有能用Java
假如有1亿个不重复的正整数（大致范围已知），但是只有1G的内存可用，如何判断该范围内的某个数是否出现在这1亿个数中？最常用的处理办法是利用位图，1*108/1024*1024*8=11.9，也只需要申请12M的内存。但是如果是1亿个邮件地址，如何确定某个邮件地址是否在这1亿个地址中？这个时候可能大家想到的最常用的办法就是利用Hash表了，但是大家可以细想一下，如果利用Hash表来处理，必须开辟空间去存储这1亿个邮件地址，因为在Hash表中不可能避免的会发生碰撞，假设一个邮件地址只占8个字节，为了保证Hash表的碰撞率，所以需要控制Hash表的装填因子在0.5左右，那么至少需要2*8*108/1024*1024*1024=1.5G的内存空间，这种情况下利用Hash表是无法处理的。这个时候要用到另外一种数据结构-布隆过滤器（Bloom Filter），它是由Burton Howard Bloom在1970年提出的，它结合了位图和Hash表两者的优点，位图的优点是节省空间，但是只能处理整型值一类的问题，无法处理字符串一类的问题，而Hash表却恰巧解决了位图无法解决的问题，然而Hash太浪费空间。针对这个问题，布隆提出了一种基于二进制向量和一系列随机函数的数据结构-布隆过滤器。它的空间利用率和时间效率是很多算法无法企及的，但是它也有一些缺点，就是会有一定的误判率并且不支持删除操作。
布隆过滤器的原理
1
布隆过滤器需要的是一个位数组（这个和位图有点类似）和k个映射函数（和Hash表类似），在初始状态时，对于长度为m的位数组array，它的所有位都被置为0
2
对于有n个元素的集合S={s1,s2......sn}，通过k个映射函数{f1,f2,......fk}，将集合S中的每个元素sj(1=j=n)映射为k个值{g1,g2......gk}，然后再将位数组array中相对应的array[g1],array[g2]......array[gk]置为1：
3
如果要查找某个元素item是否在S中，则通过映射函数{f1,f2.....fk}得到k个值{g1,g2.....gk}，然后再判断array[g1],array[g2]......array[gk]是否都为1，若全为1，则item在S中，否则item不在S中。这个就是布隆过滤器的实现原理。
当然有读者可能会问：即使array[g1],array[g2]......array[gk]都为1，能代表item一定在集合S中吗？不一定，因为有这个可能：就是集合中的若干个元素通过映射之后得到的数值恰巧包括g1,g2,.....gk，那么这种情况下可能会造成误判，但是这个概率很小，一般在万分之一以下。
很显然，布隆过滤器的误判率和这k个映射函数的设计有关，到目前为止，有很多人设计出了很多高效实用的hash函数。并且可以证明布隆过滤器的误判率和位数组的大小以及映射函数的个数有关。假设误判率为p，位数组大小为m，集合数据个数为n，映射函数个数为k，它们之间的关系如下：
p=2-(m/n)*ln2 可得 m=(-n*lnp)/(ln2)2=-2*n*lnp=2*n*ln(1/p)
k=(m/n)*ln2=0.7*(m/n)
可以验证若p=0.1，(m/n)=9.6，即存储每个元素需要9.6bit位，此时k=0.7*(m/n)=6.72，即存储每个元素需要9.6个bit位，其中有6.72个bit位被置为1了，因此需要7个映射函数。从这里可以看出布隆过滤器的优越性了，比如上面例子中的，存储一个邮件地址，只需要10个bit位，而用hash表存储需要8*8=64个bit位。
一般情况下，p和n由用户设定，然后根据p和n的值设计位数组的大小和所需的映射函数的个数，再根据实际情况来设计映射函数。
尤其要注意的是，布隆过滤器是不允许删除元素的，因为若删除一个元素，可能会发生漏判的情况。不过有一种布隆过滤器的变体Counter Bloom Filter，可以支持删除元素，感兴趣的读者可以查阅相关文献资料。
END
布隆过滤器的应用
布隆过滤器在很多场合能发挥很好的效果，比如：网页URL的去重，垃圾邮件的判别，集合重复元素的判别，查询加速（比如基于key-value的存储系统）等，下面举几个例子：
1.有两个URL集合A,B，每个集合中大约有1亿个URL，每个URL占64字节，有1G的内存，如何找出两个集合中重复的URL。
很显然，直接利用Hash表会超出内存限制的范围。这里给出两种思路：
第一种：如果不允许一定的错误率的话，只有用分治的思想去解决，将A,B两个集合中的URL分别存到若干个文件中{f1,f2...fk}和{g1,g2....gk}中，然后取f1和g1的内容读入内存，将f1的内容存储到hash_map当中，然后再取g1中的url，若有相同的url，则写入到文件中，然后直到g1的内容读取完毕，再取g2...gk。然后再取f2的内容读入内存。。。依次类推，知道找出所有的重复url。
第二种：如果允许一定错误率的话，则可以用布隆过滤器的思想。
2.在进行网页爬虫时，其中有一个很重要的过程是重复URL的判别，如果将所有的url存入到数据库中，当数据库中URL的数量很多时，在判重时会造成效率低下，此时常见的一种做法就是利用布隆过滤器，还有一种方法是利用berkeley db来存储url，Berkeley db是一种基于key-value存储的非关系数据库引擎，能够大大提高url判重的效率。
布隆过滤器的简易版本实现：
#includeiostream
#includebitset
#includestring
#define MAX 224
using namespace std;
bitsetMAX bloomSet; //简化了由n和p生成m的过程
int seeds[7]={3, 7, 11, 13, 31, 37, 61}; //使用7个hash函数
int getHashValue(string str,int n) //计算Hash值
{
int result=0;
int i;
for(i=0;istr.size();i++)
{
result=seeds[n]*result+(int)str[i];
if(result 224)
result%=224;
}
return result;
}
bool isInBloomSet(string str) //判断是否在布隆过滤器中
{
int i;
for(i=0;i7;i++)
{
int hash=getHashValue(str,i);
if(bloomSet[hash]==0)
return false;
}
return true;
}
void addToBloomSet(string str) //添加元素到布隆过滤器
{
int i;
for(i=0;i7;i++)
{
int hash=getHashValue(str,i);
bloomSet.set(hash,1);
}
}
void initBloomSet() //初始化布隆过滤器
{
addToBloomSet("");
addToBloomSet("");
addToBloomSet("");
}
int main(int argc, char *argv[])
{
int n;
initBloomSet();
while(scanf("%d",n)==1)
{
string str;
while(n--)
{
cinstr;
if(isInBloomSet(str))
cout"yes"endl;
else
cout"no"endl;
}
}
return 0;
}
关于java布隆过滤器代码和布隆过滤器 python的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。