这次kata的内容:实现一个布隆过滤器
布隆过滤器 (Bloom Filter)
什么是布隆过滤器呢?简单来说, 布隆过滤器可以告诉你一个元素是否在一个集合中.
有同学可能就会说了, 这很简单啊, 集合中本来就有所有的元素, 我只要检查输入内容是否在里面不就行了.
没错, 这种方法成功率最高(100%), 但是效率最低.
如果只是处理十个字符串、一百个字符串, 这都没问题, 但是如果要处理成百上千万的字符串, 显然是不可行的, 空间和时间都无法接受.
这时候该主角出场了——布隆过滤器.
布隆过滤器的核心思想就是用尽可能少的空间来存储尽可能多的内容, 同时尽量保证准确率.布隆过滤器本质上很像哈希表, 把一个大的空间映射到一个小的空间, 那么问题就来了, 如果两个不同元素映射到了同一个位置怎么办呢?哈希表有各种算法可以解决冲突, 但是布隆过滤器非常简单粗暴——我才不管你, 映射到同一个位置那就存同一个位置.
因此, 布隆过滤器的准确率并不是100%.准确地说, 布隆过滤器具有假阳性, 也就是说如果它告诉你一个元素在集合中, 那这个结果可能是错误的, 因为有可能这个元素和集合中另一个不同的元素映射到了同一位置.但是反过来, 如果它告诉你一个元素不在集合中, 那这个元素就肯定不在集合中.所以布隆过滤器在某些场景下是非常合适的.
为了进一步压缩空间同时提高准确率, 布隆过滤器有很多种改进方法, 其中比较常用的是把一个元素映射到结果集中的多个位(bit).举例来说, 假设每个元素会被映射到5个点, 那么两个元素只要有一个点不相同就可以判断出来；但是如果只映射到一个点, 那么这个点只要相同就无法准确判断了, 因此映射到多个点可以增加准确度.此外, 这个方法还可以压缩空间, 因为映射一个点的时候, 为了减少碰撞我们必须使用很大的空间, 但是映射多个点的时候, 多个点全部相同的概率很小, 所以我们就可以使用比较小的空间.
