领域算法
除了基础算法,工程中还有些"小而美"的算法值得了解。
一、字符串匹配
BF 暴力匹配简单但慢;KMP 用"部分匹配表"跳过不可能位置,把复杂度降到 O(n+m);BM 从右向左匹配,实际更快。
二、布隆过滤器
用多个哈希函数把元素映射到位数组,能高效判断"一定不存在 / 可能存在",误判率可控。常用于缓存穿透防护、去重。
三、一致性哈希
普通哈希在节点增减时几乎全部重映射;一致性哈希把节点与 key 映射到环上,只影响邻近数据,大幅减少数据迁移,是分布式缓存的基石。
# 简易布隆过滤器思想
bits = [0]*m
for h in hash_funcs: bits[h(x) % m] = 1