做网站需要Excel表格吗公众号免费模板

做网站需要Excel表格吗,公众号免费模板,wordpress 线条不显示,企业网站运营数据结构#xff1a;布隆过滤器 布隆过滤器#xff08;Bloom Filter#xff09;是一种空间效率极高的概率型数据结构#xff0c;由霍华德布隆在1970年提出#xff0c;用于快速判断一个元素是否存在于一个集合中。它的核心特点是 存在误判的可能#xff0c;但不存在漏判布隆过滤器布隆过滤器Bloom Filter是一种空间效率极高的概率型数据结构由霍华德·布隆在1970年提出用于快速判断一个元素是否存在于一个集合中。它的核心特点是存在误判的可能但不存在漏判即若判断元素“不存在”则一定不存在若判断元素“存在”则可能存在存在一定的误判率支持高效的插入和查询操作且不支持删除元素普通布隆过滤器。资料https://pan.quark.cn/s/43d906ddfa1b、https://pan.quark.cn/s/90ad8fba8347、https://pan.quark.cn/s/d9d72152d3cf一、布隆过滤器的核心原理布隆过滤器的底层依赖二进制位数组和多个独立的哈希函数核心流程如下1. 初始化申请一个长度为m的二进制位数组初始值全为0选择k个独立的哈希函数h₁, h₂, ..., h_k每个哈希函数能将输入元素映射到[0, m-1]范围内的一个整数索引。2. 插入元素对于要插入的元素x依次通过k个哈希函数计算得到k个索引值h₁(x), h₂(x), ..., h_k(x)将二进制位数组中这k个索引对应的位置置为1。3. 查询元素对于要查询的元素y依次通过k个哈希函数计算得到k个索引值h₁(y), h₂(y), ..., h_k(y)检查位数组中这k个索引对应的位置若所有位置都是1→ 判定元素y可能存在存在误判若任意一个位置是0→ 判定元素y一定不存在。核心特性解释误判原因不同元素通过哈希函数计算后可能会映射到相同的索引位置导致“哈希冲突”。当一个不存在的元素的k个哈希索引恰好都被其他元素置为1时就会误判为“存在”。无漏判原因只有元素确实插入过其k个哈希索引才会全部置1若有一个位置为0则元素一定没插入过。二、关键参数与误判率计算布隆过滤器的性能由三个核心参数决定二进制位数组长度m位数组越长误判率越低但空间占用越高哈希函数个数k哈希函数越多误判率越低但插入和查询的时间复杂度越高集合中预期元素个数n即布隆过滤器需要存储的元素总数。误判率公式布隆过滤器的理论误判率P计算公式为P(1−e−knm)k P \left(1 - e^{-\frac{kn}{m}}\right)^kP(1−e−mkn​)k其中e是自然对数的底数。参数选择最优解为了最小化误判率P哈希函数个数k的最优值为kmnln⁡2≈0.693⋅mn k \frac{m}{n} \ln 2 \approx 0.693 \cdot \frac{m}{n}knm​ln2≈0.693⋅nm​此时的最小误判率为Pmin(12)ke−k2nm P_{min} \left(\frac{1}{2}\right)^k e^{-\frac{k^2 n}{m}}Pmin​(21​)ke−mk2n​例如若预期存储n100000个元素要求误判率P≤0.01%则可计算出m≈1917000约 235KBk≈13。三、布隆过滤器的实现示例PythonimportmathimporthashlibclassBloomFilter:def__init__(self,expected_n,error_rate0.01): 初始化布隆过滤器 :param expected_n: 预期存储的元素个数 :param error_rate: 允许的最大误判率 # 计算二进制位数组长度 mself.mself._calculate_m(expected_n,error_rate)# 计算最优哈希函数个数 kself.kself._calculate_k(expected_n,self.m)# 初始化二进制位数组用整数模拟bitarray 更高效这里用列表简化self.bit_array[0]*self.m# 哈希函数列表使用 hashlib 实现多个独立哈希self.hash_seeds[iforiinrange(self.k)]def_calculate_m(self,n,p):计算位数组长度 mm-(n*math.log(p))/(math.log(2)**2)returnint(math.ceil(m))def_calculate_k(self,n,m):计算最优哈希函数个数 kk(m/n)*math.log(2)returnint(math.ceil(k))def_hash(self,value,seed):单个哈希函数将 value 映射到 [0, m-1] 索引# 使用 MD5 哈希结合种子生成不同的哈希值md5hashlib.md5((str(value)str(seed)).encode(utf-8))# 将哈希结果转为整数取模得到索引returnint(md5.hexdigest(),16)%self.mdefadd(self,value):插入元素 valueforseedinself.hash_seeds:idxself._hash(value,seed)self.bit_array[idx]1defcontains(self,value):查询元素 value 是否存在forseedinself.hash_seeds:idxself._hash(value,seed)ifself.bit_array[idx]0:returnFalsereturnTrue# 使用示例if__name____main__:# 预期存储 10000 个元素误判率 1%bfBloomFilter(expected_n10000,error_rate0.01)# 插入元素test_set[felement_{i}foriinrange(10000)]forelemintest_set:bf.add(elem)# 测试存在的元素应返回 Trueprint(bf.contains(element_123))# True# 测试不存在的元素大概率返回 False小概率误判为 Trueprint(bf.contains(nonexistent_element))# False或 True误判# 输出参数print(f位数组长度 m:{bf.m})print(f哈希函数个数 k:{bf.k})四、布隆过滤器的特性1. 优点空间效率极高相比哈希表、红黑树等结构布隆过滤器仅用二进制位数组存储空间复杂度为O(m)远低于其他结构时间效率高插入和查询的时间复杂度均为O(k)k为哈希函数个数通常是常数效率极高支持并行操作哈希函数之间相互独立插入和查询可并行执行无数据存储布隆过滤器不存储元素本身仅存储二进制位适合敏感数据场景如密码黑名单。2. 缺点存在误判率无法 100% 准确判断元素存在误判率与m、k、n相关不支持删除操作普通布隆过滤器删除元素会导致误判率升高多个元素共享同一组二进制位无法获取元素本身布隆过滤器仅记录“存在性”无法存储元素的额外信息。3. 改进方案计数布隆过滤器将二进制位数组改为计数器数组每个位置存储整数插入时计数器加 1删除时减 1解决删除问题但空间占用更高分层布隆过滤器将多个布隆过滤器分层用于处理动态数据集降低误判率布隆过滤器联盟多个布隆过滤器协同工作适用于分布式系统。五、布隆过滤器的典型应用缓存穿透防护场景Redis 缓存中若查询一个不存在的 key请求会穿透到数据库导致数据库压力过大方案用布隆过滤器存储所有缓存的 key查询前先通过布隆过滤器判断 key 是否存在不存在则直接返回避免穿透。黑名单过滤场景垃圾邮件过滤、恶意 IP 拦截、违禁词检测方案将黑名单中的元素存入布隆过滤器快速判断新元素是否在黑名单中。分布式系统去重场景分布式爬虫去重、分布式任务调度去重方案多个节点共享一个布隆过滤器判断任务/URL 是否已被处理避免重复执行。数据库查询优化场景判断一个值是否存在于数据库的大表中方案将大表的主键存入布隆过滤器查询前先判断不存在则直接返回减少数据库查询次数。网络爬虫 URL 去重场景爬虫爬取 URL 时避免重复爬取相同页面方案用布隆过滤器存储已爬取的 URL新 URL 先查询布隆过滤器存在则跳过。六、布隆过滤器与其他数据结构的对比数据结构空间复杂度插入时间复杂度查询时间复杂度支持删除误判率适用场景布隆过滤器O(m)O(k)O(k)不支持普通版有海量数据的存在性判断哈希表O(n)O(1)平均O(1)平均支持无需存储元素及额外信息红黑树O(n)O(log n)O(log n)支持无有序数据的增删改查位图BitMapO(m)O(1)O(1)支持无整数集合的存在性判断无哈希冲突布隆过滤器的核心优势是极致的空间效率适合“允许少量误判、不支持删除、仅需存在性判断”的场景若需精确判断或存储元素信息则需选择哈希表等结构。