企业网站模板包含什么,维度 网站建设,线上商城介绍,购物中心设计前言 大家好吖#xff0c;欢迎来到 YY 滴 数据结构 系列 #xff0c;热烈欢迎#xff01; 本章主要内容面向接触过C的老铁 主要内容含#xff1a; 欢迎订阅 YY滴 数据结构 专栏#xff01;更多干货持续更新#xff01;以下是传送门#xff01; 目录 一.布隆过滤器产生的… 前言 大家好吖欢迎来到 YY 滴 数据结构 系列 热烈欢迎 本章主要内容面向接触过C的老铁 主要内容含 欢迎订阅 YY滴 数据结构 专栏更多干货持续更新以下是传送门 目录 一.布隆过滤器产生的前提二.布隆过滤器的原理基本场景【1】布隆过滤器的核心原理重要性质【2】布隆过滤器的基本场景1快速判断广告是否推送过——不需要精确的场景2快速判断昵称是否注册过——需要精确的场景 三.布隆过滤器一般不支持删除四.布隆过滤器的经典例题【1】给两个文件分别有100亿个query我们只有1G内存如何找到两个文件交集分别给出精确算法和近似算法————哈希切分【2】如何扩展BloomFilter使得它支持删除元素的操作 一.布隆过滤器产生的前提 我们在使用新闻客户端看新闻时它会给我们不停地推荐新的内容它每次推荐时要去重去掉 那些已经看过的内容。用服务器记录了用户看过的所有历史记录当推荐系统推荐新闻时会 从每个用户的历史记录里进行筛选过滤掉那些已经存在的记录。 如何快速查找呢 用哈希表存储用户记录缺点浪费空间用位图存储用户记录缺点位图一般只能处理整形如果内容编号是字符串就无法处理 了。将哈希与位图结合即布隆过滤器 二.布隆过滤器的原理基本场景
【1】布隆过滤器的核心原理重要性质 布隆过滤器是由布隆Burton Howard Bloom在1970年提出的 一种紧凑型的、比较巧妙的概 率型数据结构特点是高效地插入和查询可以用来告诉你 “某样东西可能存在或者一定不存在”它是用 多个哈希函数 将一个数据映射到位图结构中 。此种方式不仅可以提升查询效率也可以节省大量的内存空间。 如下图1所示 某样东西可能存在baidu 与other 通过哈希函数Hash1Hash2都同时映射到相同位置发生了哈希冲突。所以当我们根据该位置下定义baidu/Other存在则可能出现误判这种误判无法消除所以只能下定义——某样东西可能存在 如下图2所示 某样东西一定不存在比如只有位图3号位置被标识为1则一定能说明baidu和Other一定不存在 【2】布隆过滤器的基本场景
1快速判断广告是否推送过——不需要精确的场景 比如我们在【一】中提出的我们在使用新闻客户端看新闻时它会给我们不停地推荐新的内容它每次推荐时要去重去掉那些已经看过的内容。 2快速判断昵称是否注册过——需要精确的场景 根据布隆过滤器的性质它会告诉你 “某样东西可能存在或者一定不存在”如果每一次查询都访问数据库会增加数据库查询负载降低效率因此我们设置一个布隆过滤器把所有昵称都放到这个过滤器中 如果显示昵称不存在则支持输入昵称如果显示昵称存在则表示其可能存在再到数据库中进行精确查询 三.布隆过滤器一般不支持删除 布隆过滤器不能直接支持删除工作因为在删除一个元素时可能会影响其他元素。 四.布隆过滤器的经典例题
【1】给两个文件分别有100亿个query我们只有1G内存如何找到两个文件交集分别给出精确算法和近似算法————哈希切分 我们先有一个内存大小基本概念1G约为10亿byte假设一个query平均为30byte那么100亿query就约为3000亿byte约为300G 哈希切分的基本概念 是将一个大文件利用哈希的原理 将其分为若干个小文件。 相同的数据都被分到同一个文件里 在此题中如下图所示即A和B中相同的query就会进入相同的小文件中 【2】如何扩展BloomFilter使得它支持删除元素的操作 多个位标识同一个值使用 引用计数
