LSH局部敏感哈希原理

可视化演示

展示LSH哈希投影桶划分、SimHash符号编码与AND-OR级联构造的召回率调节过程。

LSH核心思想

快递中心的老张管着分拣线。传统分拣按“运单号”操作：运单号差一位数字，包裹就被甩到完全不同的传送带，永远不会出现在同一个分拣口。这套体系做“精确查找”很高效，但面对“找出所有地址相似的包裹”就彻底失灵了——因为相似不是相等。

向量检索面临的正是同样的困境。在Embedding检索中，每个用户、商品、文档都被表示成一个几百维的浮点向量。查询到来时，我们要找出与它“相似”（距离近）的TopK个向量。暴力线性扫描要比较全部数据，亿级规模下无法实时响应；普通哈希函数（如MD5）对输入极其敏感，向量稍微变化一点，哈希值就面目全非，相似的向量根本不会落入同一个桶。

LSH（Locality-Sensitive Hashing，局部敏感哈希）正是为解决“相似查找”而生的哈希函数族。它的核心特征是局部敏感：原始空间中距离近的点，哈希后以高概率落入同一个桶；距离远的点，落入同一桶的概率很低。形式化地说：

查询时只需对查询向量做同样的哈希，再只搜索它所在桶内的候选点，搜索范围就从全量压缩到一个小分拣口。老张终于松了口气：上亿件包裹不需要全翻，只要去对应片区找，速度提升了几个数量级。

哈希家族对比

老张的快递中心有不同的业务线：生鲜要按温度分拣，重货要按楼层分拣，加急件要按时效分拣。一套规则不可能满足所有需求。LSH同样如此——不同的距离度量，要选不同的哈希家族。

• 普通哈希：要求输入完全相同才映射到同一位置，适合精确查找与去重，无法承载“相似”语义。

• MinHash：面向Jaccard相似度，适合集合型数据，如文本去重、购物记录比对。

• SimHash：面向余弦相似度，适合高维稠密文本向量，常用于网页去重。

• p-stable LSH：面向欧氏距离，适合通用Embedding向量，是向量检索的主力。

选错哈希家族，就像用温度分拣标准去分拣重货，毫无意义。比如两台手机用户向量用欧氏距离衡量更自然，套用MinHash的集合视角反而不合适。最经典的Jaccard相似度定义是：

所以工程上的第一课是：先看你的数据用什么距离度量，再选对应的LSH哈希族。老张总结道：包裹按什么属性分拣，取决于客户在乎什么属性。

MinHash原理

两个购物袋，想知道里面商品重叠了多少。逐个比对（精确计算Jaccard）费时费事。一个巧妙办法：给所有可能商品随机排一个顺序（随机置换），然后各自取“袋子里排在最前面的商品”作为袋子的标签。如果两个袋子的标签经常相同，说明它们内容高度重叠。

MinHash正是这个“标签法”的数学化。对集合S，施加随机置换π，定义最小哈希值为集合中π(x)最小的元素。它的关键定理非常漂亮：

实际操作中，我们用k个独立置换生成k维签名向量，再用签名中相同位置的比例估计相似度：

这就像老张给每个分拣口挂上“代表商品标签”，几百个标签一对比，两个袋子像不像一目了然。标签越多，估计越准，这就是MinHash的无偏估计特性。

欧式哈希族

老张遇到新挑战：有些包裹是用GPS坐标定位的，地图上没法天然划出“片区”。怎么办？答案很简单——随机画平行线。把地图切成等宽的条形区域，两个包裹落在同一条形区的概率，随它们的实际距离增大而衰减。多画几组不同方向的平行线，就构成多个哈希表。

这就是p-stable LSH的核心思想。对d维向量v，哈希函数定义为：

其中a是服从标准正态分布N(0,1)的d维随机向量，b在[0,w)上均匀随机，w是带宽。直观理解：a·v把v投影到随机方向a上，投影值再除以带宽w取整，就落到了某个“条形区”。

碰撞概率随距离c的增大而衰减，精确表达式为：

老张的地图被切成一条条“分拣带”，两个点若落进同一条带，说明它们在某个随机方向上位置相近。多组随机方向叠加，相似度判断就更可靠。

检索全流程

用户拿着查询单来了。老张的完整流程分四步：先查分拣表确定去哪个分拣口（哈希），再从分拣口搬出那一堆包裹（候选集），然后逐个仔细核对地址（精确距离），最后挑出最相近的包裹交给用户（TopK）。

离线阶段：对所有向量计算L个哈希函数的值，放入L张哈希表。每张表的key是哈希值，value是落在这个桶里的向量ID列表。

在线查询阶段：

1. 对查询向量q分别计算L个哈希值

2. 从L张表中取出对应桶，合并去重得到候选集C

3. 对C中的向量用原始度量（如欧氏距离）精确计算

4. 排序并返回TopK结果

召回率是衡量候选集质量的核心指标：

其中G是暴力搜索得到的真实TopK集合，C是LSH候选集。

老张常说：“分拣口捞得快不快是速度，捞得全不全就是召回率。” LSH用小小的概率损失换来了惊人的速度提升，这正是它在工业界被广泛接受的原因。

参数与调优

分拣线太粗（一个口容纳半个城区），找得全但翻找慢；太细（每个小区一个口），翻得快但容易漏。老张的解法是“AND-OR级联”：先做k次精确匹配（AND），再用L张表重复（OR）。

AND操作：使用k个哈希函数，要求k个值全部相等才认为碰撞。这让桶更精细，候选更少，但碰撞概率从p降为p^k。OR操作：构建L张独立哈希表，任何一张表命中即可进入候选。这给了相似对“L次补救机会”。两级合并后的整体命中概率为：

实际工程中常用k=8~12、L=32~128。画出“候选规模-召回率”的S曲线：相似对概率接近1，不相似对概率接近0，两者之间出现明显分界。老张的调参心得：先定可接受延迟，再选k保精度，最后用L拉召回，三者是跷跷板。

工程实战

现实中的快递中心，周一处理生鲜订单，周二应对大促爆仓——不同业务、不同量级、不同SLA。LSH工程落地同样要围绕场景定制方案。

• 广告推荐：用户向量与广告向量在亿级规模下做相似召回。离线把广告向量全部哈希入桶，在线对用户向量查桶取候选，再精排出TopK广告。

• 语义搜索：查询与文档用BERT映射到同一向量空间。LSH做第一层粗筛，把候选从百万压到几千，再交给重排序模型精细打分。

• 混合索引：LSH负责粗筛候选，HNSW等图索引负责在候选内做更精确的近邻搜索，两者组合兼顾速度与精度。

• 内存压缩：用乘积量化（PQ）压缩向量存储，或用布隆过滤器压缩桶ID，减少哈希表内存占用。

候选集规模可以用期望公式估算：

老张在季度总结会上说：LSH不是银弹，它解决的是“海里捞针第一步”的问题。把候选范围缩小到可以精确计算之后，后面的精排、重排序才能发挥价值。

AI 应用场景

Python 演示

import random PRIME = 2**31 - 1 def item_id(item):    """把字符串稳定映射为整数, 保证可复现"""    code = 0    for ch in item:        code = (code * 127 + ord(ch)) % PRIME    return code def make_hashes(num_hashes, seed=42):    rng = random.Random(seed)    hashes = []    for _ in range(num_hashes):        a = rng.randint(1, PRIME - 1)        b = rng.randint(0, PRIME - 1)        hashes.append((a, b))    return hashes def minhash_signature(items, hashes):    ids = [item_id(x) for x in set(items)]    sig = []    for a, b in hashes:        vals = [((a * x + b) % PRIME) for x in ids]        sig.append(min(vals))    return sig def estimate_jaccard(set_a, set_b, hashes):    sig_a = minhash_signature(set_a, hashes)    sig_b = minhash_signature(set_b, hashes)    same = sum(1 for x, y in zip(sig_a, sig_b) if x == y)    return same / len(hashes) if __name__ == "__main__":    set_a = {"苹果", "香蕉", "樱桃", "葡萄", "芒果"}    set_b = {"苹果", "香蕉", "西瓜", "草莓", "柠檬"}    truth = len(set_a & set_b) / len(set_a | set_b)    est = estimate_jaccard(set_a, set_b, make_hashes(300))    print(f"真实 Jaccard: {truth:.3f}")    print(f"MinHash 估计: {est:.3f}")

1. hashes.append((a, b))用一条(a,b)直线模拟一次随机置换，种子固定保证可复现
2. ids = [item_id(x) for x in set(items)]先把集合内元素稳定编码成整数，消除Python hash随机性
3. vals = [((a * x + b) % PRIME) for x in ids]对每个元素施加随机哈希变换并取模防止溢出
4. sig.append(min(vals))集合内最小哈希值就是该维签名，对应“随机置换下最靠前的商品”
5. same = sum(1 for x, y in zip(sig_a, sig_b) if x == y)对齐比较两个签名向量，统计相同位数
6. return same / len(hashes)相同位置占比即Jaccard相似度的无偏估计

常见误区

面试题