09 bloom filter

reflection

If you want to judge often 1 Whether the elements exist , What would you do ？

 It's easy to think of using hash tables （HashSet、HashMap）, Take the element as key Go find * Time complexity ：O(1), But space utilization is not high , Need to occupy more memory resources

If you need to write a web crawler to climb 10 100 million website data , To avoid climbing to duplicate websites , How to judge whether a website has been crawled ？

 Obviously ,HashSet、HashMap Not a very good choice

Whether there is low time complexity 、 Solutions that use less memory ？

 The bloon filter （Bloom Filter）

 

The bloon filter （Bloom Filter）

1970 It was proposed by bron

 It is a probabilistic data structure with high spatial efficiency , It can be used to tell you ： An element must not exist or may exist

Advantages and disadvantages

 advantage ： Space efficiency and query time are far more than general algorithms

 shortcoming ： There is a certain rate of miscalculation 、 Delete difficult

It is essentially a long binary vector and a series of random mapping functions （Hash function ）

Common applications

 Web blacklist system 、 Spam filtering system 、 Crawler's web address duplication system 、 Solve the problem of cache penetration

 

 

The principle of Bloom filter

Suppose the bloom filter consists of 20 Bit binary 、 3 It's a hash function , Each element can be processed by hash function to generate an index position

 Additive elements ： Set the index position generated by each hash function to 1

 Query whether the element exists

* If there is a hash function, the generated index position is not 1, It means that there is no （100% accuracy ）

* If the index position generated by each hash function is 1, It means existence （ There is a certain rate of miscalculation ）

 

 

add to 、 The time complexity of query is ：O(k) ,k Is the number of hash functions . The space complexity is ：O(m) ,m Is the number of binary bits

The misjudgment rate of Bloom filter

 

Implementation of the bloom filter

Guava: Google Core Libraries For Java

https://mvnrepository.com/artifact/com.google.guava/guava