专栏名称: 程序猿
本微信公众号:imkuqin,为程序员提供最新最全的编程学习资料的查询。目前已经开通PHP、C/C++函数库、.NET Framework类库、J2SE API查询功能。
今天看啥  ›  专栏  ›  程序猿

一道腾讯面试题:如何快速判断某 URL 是否在 20 亿的网址 URL 集合中?

程序猿  · 公众号  · 程序员  · 2019-09-22 22:24
来自:张振伟的博客链接:https://zhangzw.com/20190521.html何为布隆过滤器还是以上面的例子为例:判断逻辑:多次哈希:Guava的BloomFilter创建BloomFilter最终还是调用:使用:算法特点使用场景假设遇到这样一个问题:一个网站有 20 亿 url 存在一个黑名单中,这个黑名单要怎么存?若此时随便输入一个 url,你如何快速判断该 url 是否在这个黑名单中?并且需在给定内存空间(比如:500M)内快速判断出。可能很多人首先想到的会是使用 HashSet,因为 HashSet基于 HashMap,理论上时间复杂度为:O(1)。达到了快速的目的,但是空间复杂度呢?URL字符串通过Hash得到一个Integer的值,Integer占4个字节,那20亿个URL理论上需要:20亿*4/1024/1024/1024=7.45G的内存,不满足空间复杂度的要求。这里就引 ………………………………

原文地址:访问原文地址
快照地址: 访问文章快照