爬虫数据去重:
- 使用md5生成指纹判断页面是否变化
- 数据存入mongodb,对关键字进行复合索引(千万以下)
- 对数据关键字进行哈希映射,生成指纹判断是否在redis的指纹集合中,并可通过是否过滤判断request对象是否进队,对request对象进行过滤(千万级别)
- 布隆过滤器,实现大数据去重(亿级别)
布隆过滤器:
实现:
- 先通过预期失误率p、期望样本数量n,计算需要的位数组长度m
m=-n*lnp / (ln2)**2
k=ln2 * m/n
- 再根据m、n、k,计算真实的失误率,因为m,k向上调整,所以真实失误率 < 预期失误率
p=(1-e**(-nk/m))**k
- 将数据(key)通过k个哈希函数得到k个哈希值
- 将得到的哈希值对m取模运算,得到位数组对应的索引位置
index=hashcode(key)&(m-1)
- 如果保存,将位数组中对应的索引位置变为1
- 如果查询,判断位数组对应的索引是否全为1,全为1则存在
原理:hashmap
- 可以将值映射到hashmap的key,在o(1)时间复杂度内返回结果
- hashmap的默认长度为16,每次扩展都是2的次幂
哈希函数特性:
- 哈希碰撞:哈希函数不同的输入可以得到相同输出结果,输入域有限,输出域无限
- 离散性:输出域每个结果在整个输出域中都是均匀分布的
如对本文有疑问,
点击进行留言回复!!
相关文章:
-
-
-
实时流式计算系统中的几个陷阱
随着诸如Apache Flink,Apache Spark,Apache Storm之类的开源框架以及诸如Google Dataflow之类的云框架的增...
[阅读全文]
-
-
-
-
-
字符串相似度处理函数
oracle里面查比如存储过程里面与表SALES有关jobs: SELECT * FROM (SELECT a.name,upper(b.what)AS...
[阅读全文]
-
-
一小时搭建实时数据分析平台
实时数据分析门槛较高,我们如何用极少的开发工作就完成实时数据平台的搭建,做出炫酷的图表呢? 如何快速的搭建实时数据分析平台,首先我们需要实时数据的接入端...
[阅读全文]
-
网友评论