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

来源：8-3 缓存设计面试专题-(2)

luluoverflow

2021-04-06

如题~

写回答

1回答

求老仙

2021-04-07

已采纳

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

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

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

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

luluoverflow

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

2021-04-07

共1条回复

笑傲Java面试剖析大厂高频面试真题秒变offer收割机

深度剖析大厂面试高频真题，让你秒变offer收割机

1783 学习 · 314 问题

相似问题

回答 2

回答 1

回答 2

回答 1

回答 1