0%

BloomFilter(布隆过滤器)是一种可以高效地判断元素是否在某个集合中的算法。

在很多日常场景中,都大量存在着布隆过滤器的应用。例如:检查单词是否拼写正确、网络爬虫的 URL 去重、黑名单检验,微博中昵称不能重复的检测等。

在工业界中,Google 著名的分布式数据库 BigTable 也用了布隆过滤器来查找不存在的行或列,以减少磁盘查找的 IO 次数;Google Chrome 浏览器使用 BloomFilter 来判断一个网站是否为恶意网站。

对于以上场景,可能很多人会说,用 HashSet 甚至简单的链表、数组做存储,然后判断是否存在不就可以了吗?

当然,对于少量数据来说,HashSet 是很好的选择。但是对于海量数据来说,BloomFilter 相比于其他数据结构在空间效率和时间效率方面都有着明显的优势。

但是,布隆过滤器具有一定的误判率,有可能会将本不存在的元素判定为存在。因此,对于那些需要 “零错误” 的应用场景,布隆过滤器将不太适用。具体的原因将会在第二部分中介绍。

阅读全文 »

前两天把实验室的一台旧台式机装上了 Ubuntu Server,打算当作测试服务器使用着玩。
装上之后意识到一个严重的问题:实验室电脑连接外网时候需要打开浏览器输入学号进行认证。

阅读全文 »

为什么会想到建立一个博客:

在此博客之前,我其实也用过新浪博客、CSDN、博客园,作为个人博客的载体,但对每个博客都并不是特别的满意。原因大概有下面几条:

  • 没有美观友好的支持代码。
  • 广告多。
  • 管理复杂,但可控性差。

目前该博客是使用 hexo+Next 主题 + Github 进行搭建。
事实上,当开始接触使用 hexo 时,我觉得满足了我对博客的诸多要求。我对它的为程序员而生、高度可定制性非常喜欢。而且,如有机会,可以自己写出满意的主题使用。

阅读全文 »