莱芜做网站公司布恩网站删除

莱芜做网站公司,布恩网站删除,河北seo网络优化培训,宁波建设工程学校这是一个用空间换时间#xff0c;专门解决“是否存在”问题的概率型数据结构。第一层#xff1a;本质与要解决的问题 布隆过滤器的核心价值是#xff1a; 用一个极小的空间成本#xff0c;快速判断一个元素“绝对不存在”或“可能存在”于一个超大规模集合中。 它要解决的痛…这是一个用空间换时间专门解决“是否存在”问题的概率型数据结构。第一层本质与要解决的问题布隆过滤器的核心价值是用一个极小的空间成本快速判断一个元素“绝对不存在”或“可能存在”于一个超大规模集合中。它要解决的痛点庖丁解牛场景缓存穿透恶意请求大量不存在的数据如不存在的用户ID导致每次请求都穿透缓存直达数据库造成数据库压力。安全领域快速判断一个URL是否属于恶意网站黑名单黑名单通常极大无法全部放入内存。推荐系统判断一篇文章是否已经被推荐给用户避免重复推荐。关键特性空间效率极高使用一个位数组bit array表示超大规模集合。查询效率极高查询时间固定为O(k)k是哈希函数个数。100%准确的“不存在”如果布隆过滤器说一个元素不存在那它一定不存在。微小的误判率“存在”如果布隆过滤器说一个元素存在它可能实际不存在假阳性。这是为节省空间付出的代价。第二层解剖内部结构——三大核心组件布隆过滤器可以看作一个精密的“联合检测系统”。1. 位数组一个长度为m的二进制数组bit array初始所有位都为0。这是布隆过滤器的存储主体非常紧凑。索引: [0][1][2][3][4][5][6][7][8][9]...[m-1] 值: 0 0 0 0 0 0 0 0 0 0 ... 02. 哈希函数组一组k个独立且均匀的哈希函数如hash1,hash2, …,hashk。它们的任务是将任意输入元素映射到[0, m-1]范围内的k个不同位置。比喻像k个不同的公证员负责对元素进行多重身份认证。3. 元素你要判断是否存在于目标集合中的对象如用户ID、URL。第三层工作流程庖丁解牛我们通过添加元素和查询元素两个过程来深入理解。场景用一个布隆过滤器判断用户ID是否存在防止缓存穿透假设位数组长度m 10哈希函数个数k 3(h1, h2, h3)要添加的用户ID12345步骤一添加元素add(12345)哈希计算将元素12345分别用k个哈希函数计算得到k个位置。h1(12345) 2h2(12345) 5h3(12345) 8置位操作将位数组中这k个位置的值设置为1。操作前: [0][0][0][0][0][0][0][0][0][0] 操作后: [0][0][1][0][0][1][0][0][1][0] ^ ^ ^ 2 5 8庖丁解牛添加元素12345并不是存储元素本身而是在位数组中留下一个独特的“指纹”第2、5、8位被标记。步骤二查询元素exists(12345)哈希计算同样用k个哈希函数计算12345得到相同的位置[2, 5, 8]。检查位数组检查这些位置上的值是否全部为1。位置21 ✅位置51 ✅位置81 ✅返回结果“可能存在”。因为它的“指纹”与之前记录的匹配。步骤三查询不存在的元素exists(99999)哈希计算计算99999假设得到位置[1, 5, 9]。检查位数组位置10 ❌位置51 ✅位置90 ❌返回结果“肯定不存在”。因为它的“指纹”中有一位第1位为0表明这个元素从未被添加过。第四层误判率假阳性的庖丁解牛为什么会有误判假设我们现在添加第二个用户ID67890h1(67890) 1h2(67890) 5// 注意位置5已经被12345占用了h3(67890) 9置位后位数组变为[0][1][1][0][0][1][0][0][1][0] ^ ^ ^ ^ 1 2 5 8,9 (9是新的)现在查询一个从未添加过的元素xyz假设哈希后位置为[1, 2, 9]。检查发现位置1为1位置2为1位置9为1。全部为1布隆过滤器错误地返回“可能存在”。误判的根本原因哈希冲突。不同元素的哈希位置可能重叠当重叠足够多时一个新元素的“指纹”可能完全被已存在元素的“指纹”覆盖。第五层参数设计的数学原理误判率取决于三个核心参数n预期要添加的元素数量。m位数组的长度位数。k哈希函数的个数。数学关系庖丁解牛当m越大位数组越长或k越合适时误判率p越低。有一个著名的公式用于估算最优的k和pk (m / n) * ln(2) // 最优哈希函数个数 p ≈ (1 - e^(-k * n / m))^k // 近似误判率实践指导如果预期有1百万个元素愿意接受1%的误判率大约需要9.6MB的位数组。同样的元素数量如果要求误判率降至0.1%大约需要14.4MB。相比直接存储1百万个原始数据如ID布隆过滤器的空间效率是数量级的提升。第六层PHP实现示例以下是布隆过滤器的简化实现帮助理解其内部机制classSimpleBloomFilter{private$bitArray;private$size;private$hashFunctions;publicfunction__construct($size,$hashFunctions){$this-bitArrayarray_fill(0,$size,false);$this-size$size;$this-hashFunctions$hashFunctions;}// 添加元素publicfunctionadd($item){foreach($this-hashFunctionsas$hashFn){$index$hashFn($item)%$this-size;$this-bitArray[$index]true;}}// 检查元素是否存在publicfunctionexists($item){foreach($this-hashFunctionsas$hashFn){$index$hashFn($item)%$this-size;if(!$this-bitArray[$index]){returnfalse;// 肯定不存在}}returntrue;// 可能存在}}// 使用示例模拟3个哈希函数$bloomnewSimpleBloomFilter(1000,[function($str){returncrc32($str.salt1);},function($str){returncrc32($str.salt2);},function($str){returncrc32($str.salt3);}]);// 添加黑名单URL$bloom-add(http://malicious.com);$bloom-add(http://phishing.com);// 检查URL$urlhttp://safe.com;if($bloom-exists($url)){echo警告该URL可能在黑名单中\n;}else{echoURL安全可继续访问。\n;// 绝对安全}总结布隆过滤器的“骨骼图”组成部分庖丁解牛分析比喻位数组核心存储结构一个二进制位数组。一个巨大的、有m个格子的检查板。哈希函数将元素映射到位数组的k个特定位置。k个公证员负责在检查板上做标记。添加元素计算k个位置并将这些位置标记为1。公证员在检查板的k个格子上盖章。查询元素计算k个位置如果全为1则“可能存在”否则“肯定不存在”。检查k个格子是否都有章。误判率因哈希冲突导致不同元素标记重叠的概率。不同人碰巧在相同的k个格子上盖了章。空间效率用极小的空间表示超大规模集合。用一张小检查板代表一个巨大的名单。适用场景缓存穿透保护爬虫URL去重垃圾邮件过滤集合成员初步判断不适用场景要求100%准确性的场景需要实际获取元素本身的场景布隆过滤器只判断存在性布隆过滤器是算法设计中“空间换时间”和“概率化思维”的经典体现理解它对于处理大数据量下的存在性判断问题非常有帮助。