海量数据处理总结

备战百度,在海量数据处理的主题上做一个总结。
详情来自http://www.cnblogs.com/pkuoliver/archive/2010/10/02/mass-data-topic-1.html

1.Bloom Filter

将数据通过hash函数映射到位数组,比如hash(str)=3则将位数组第三位置为1
对每一条数据都用k个hash函数进行映射,也就是一条数据会将位数组的最多k位的值置1
在查找数据是否存在的时候,则对其进行k次hash,如果位数组中对应的各位都被置1了,则说明该数据已经存在(明显是有一定错误率的)
Bloom Filter可以用来实现数据字典,进行数据的判重,或者集合求交集.
同时,对其进行改进,即位数组每一位不再是0/1,而是数据出现的次数counter,那么出现数据则+1,删除数据则-1,这样可以实现删除操作。

实例:

Continue Reading…