第 276 题：实现向量检索的LSH，哈希函数族的设计。
题目
实现向量检索的LSH，哈希函数族的设计。
完整讲解
一、LSH 与向量检索
- 近似最近邻：高维向量中找与 query 最近的 top-k，精确解代价高。LSH（局部敏感哈希） 用一族哈希函数，使相似向量以高概率落入同一桶，检索时只查 query 所在桶（及邻近桶），实现亚线性时间与空间。
二、哈希函数族的设计
- 目标：若 $d(u,v)$ 小则 $\Pr[h(u)=h(v)]$ 大；若 $d(u,v)$ 大则 $\Pr[h(u)=h(v)]$ 小。对欧氏距离常用 p-stable LSH（如用随机投影 + 桶宽为 $w$ 的量化）；对余弦相似度可用随机超平面：$h(x)=\text{sign}(r^\top x)$，$r$ 为随机单位向量，两向量同侧则同桶。
- 多表与多哈希：单次哈希碰撞率可能不够，取 $L$ 个表，每表用 $k$ 个哈希函数串联（$g=(h_1,\ldots,h_k)$），向量落入 $g$ 对应的桶。增大 $L,k$ 可调节 recall 与 bucket 大小；通常 $k$ 大则桶更细、$L$ 大则 recall 提高。
- 实现：预计算每表每桶的向量 id 列表；query 时算 $g(q)$ 取对应桶，在桶内做精确距离或二次哈希；可结合多 probe（查相邻桶）提 recall。
三、推荐中的应用
- 双塔或 embedding 产出 user/item 向量后，用 LSH 做大规模候选检索；需调参 $L,k,w$ 与数据规模，平衡延迟、recall 与内存。
面试要点
- 能说清 LSH 的目的（相似向量高概率同桶、近似最近邻），以及哈希函数族需满足的性质。
- 能说明一种函数族（如随机超平面求余弦、p-stable 求欧氏）及多表多哈希、多 probe 的作用。
记忆要点
- LSH：相似向量高概率同桶；函数族如随机超平面（余弦）、p-stable（欧氏）；多表多哈希调 recall。
- 检索：query 哈希取桶，桶内精确算或二次哈希；可多 probe 邻桶。