布隆过滤器原理及使用
什么是布隆过滤器?我们来看这么一个场景:目标网站有上千万个URL,如何判断某个URL是否已经访问过?使用DB存储的话,就是把每个URL存入DB,然后每次访问URL前执行 1slect id from table where url = 'xxxx' 但随着URL数据量增多,每次请求前都要访问DB一次,效率非常低。当然,也可以用redis的set结构存储URL,优于DB存储,但也同样存在一个问题:耗费内存过多。如何解决?布隆过滤器! 布隆过滤器从本质上讲是一个位数组,位数组就是数组的每个元素都只占用1bit。每个元素只能是0或者1。这样申请一个10000个元素的位数组只占用 10000/8 = 1250B 的空间。布隆过滤器除了一个位数组,还有K个哈希函数。当一个元素加入布隆过滤器的时候,会进行如下操作: 使用K个哈希函数对元素值进行K次计算,得到K个哈希值。 根据得到的哈希值,在数组中把对应下标的值设置为1。 如上图:url1通过f1,f2,f3...