布隆过滤器

  • 参考资料：
    布隆过滤器的原理和实现

  • 学习背景
    在我之前的文章Python爬虫项目：wiki距离中，通过集合存储和判断链接是否已经遍历过，占用内存很大，这里准备改用布隆过滤器来实现判断链接是否已经遍历过

  • 什么时候需要布隆过滤器？
    需要在大量的元素中查找某个元素是否存在，以下常规思路也可以解决，但是占用的空间太大，布隆过滤器是以位为单位。
    数组
    链表
    树、平衡二叉树、Trie
    Map (红黑树)
    哈希表

  • 布隆过滤器的实现过程
    元素通过哈希函数计算出某个数值，这个数值对应一个大二进制向量的某一位，加入的时候我们将其置1，查询的时候看是否为1。

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容