常见大数据和空间面试题

2018-06-01
阅读 3 分钟
3.4k
过滤100亿黑名单 题目 假设有100亿个URL的黑名单,每个URL最多占用64B,设计一个过滤系统,判断某条URL是否在黑名单里。 要求 不高于万分之一的判断失误率;额外内存不超过30GB 答案 100亿个64B的URL需要640GB的内存,显然直接存哈希表不合理。考虑布隆过滤器,假设有一个长度为m的bit类型数组,如图所示: 输入阶段: ...