布隆过滤器原理及使用
什么是布隆过滤器？我们来看这么一个场景：目标网站有上千万个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...
