布隆过滤器这里的哈希为什么只哈希四位字符 （比如ACCG），为什么不直接哈希ACCGTAG ？

Question

如题~

Answer 1

求老仙 2021-04-07 12:10:03

同学你好， 这个问题提的很好。

布隆过滤器的思路是用多个位代表一个串存不存在。

比如说ACCGTAG -> ACCG  CGTA  GTAG ， 然后hash 3个，对应3个比特。 那么判断的准确率就高。如果直接hash，对应的是一个bit，冲突率高，准确率低。 

核心问题是，布隆过滤器要节省空间。用少量的空间，给出一个模糊的判断。

• 提问者 luluoverflow #1

  我明白了，布隆过滤器不能像一般的哈希表那些把key-value存下来（因为这样太浪费空间），所以无法用链地址法避免冲突，但是又要保证一定准确率，所以采用了分段hash的方法。
  总的来说，布隆过滤器只是一个过滤器，不是字典或者集合。