近邻索引可以减少需要比较的候选点，但没有进入候选集的真近邻，无法靠最后一次精确距离计算补回来。评价索引因此需要同时回答三个问题：漏了哪些近邻、保存了多少索引、每次查询花多少时间。

本篇只实现二进制Hamming空间中的位抽样LSH。精确扫描使用同一批数据、同一批查询和同一种并列顺序；HNSW作为另一类方法的延伸，不把LSH碰撞公式当作它的保证。

先固定距离和答案顺序

输入有n条D位二进制向量，D>0，每条用[0,2^D)中的整数表示，ID为输入位置。允许不同ID拥有相同向量。距离为异或结果的1位数，范围0到D；它不是实数向量的欧氏距离或余弦距离。

精确答案按“距离、ID”升序取前k项，k>0。n<k时返回全部n项，空数据返回空。查询整数必须位于同一D位范围，越界拒绝。并列距离也按ID排序，避免索引与参照只因选择不同的同距点而难以解释recall。

近似接口采用相同排序，但只对候选集排序，候选不足k时返回不足。没有候选时返回空，不自动回退到全扫描。否则一些配置会用完整扫描掩盖索引漏检，速度和质量的含义都会改变。

多张位抽样表

每张表独立抽取b个位位置，每次在0到D−1之间均匀选择，允许重复抽到同一个位置。把这些位依次拼成签名，相同签名的数据ID放入同一桶。构建L张表，b、L都要求正整数。

查询也计算L个签名，取对应桶的ID并集，然后按完整Hamming距离重排。候选去重以ID为单位；相同向量的不同记录仍是不同答案，不应合成一条。

此过程保证返回记录来自数据集，距离和候选内顺序正确，但不保证候选包含全局前k名。精确重排只消除候选内部的排序误差，不能恢复未被取出的ID。

碰撞概率与独立性

固定查询q和数据点x，设距离为d。一次均匀抽位命中相同位的概率是1−d/D。b次有放回独立抽样全部相同，才在一张表碰撞，所以

pd=(1−d/D)b.p_d=(1-d/D)^b.

L张表独立时，指定点在所有表都未碰撞的概率为

(1−pd)L.(1-p_d)^L.

这是对随机建表的概率，不要求输入向量各位独立。相反，如果所有表复用同一组位位置，就不能把同一次漏检的概率乘L次。固定PRNG种子只产生一组可复跑表，单次结果不等于对所有随机表取平均。

抽样方式也是条件。若改成不放回抽b个位置，碰撞概率应按相同位位置的组合数计算，不再一般等于上述幂。证明中的独立性不能从“看起来随机”四个字得到。

增大b降低远点碰撞，也降低近点碰撞；增大L提高指定点进入至少一个桶的概率，同时增加表空间和查询工作。对多个真近邻报告recall时，各点进入候选的事件未必独立，不能再无条件相乘。

一个近点被漏掉的实例

设D=4，一张表只抽最低位。查询0000，数据为0001和1110。前者距离1却在不同桶，后者距离3但最低位相同。k=1时索引返回远点，recall为0。

这个固定表反例没有否定碰撞概率定理：概率允许坏抽样。它说明“候选内精确重排”不能升级为“总能找到精确最近邻”。若查询由知道表内容的对手专门构造，固定查询的建表概率表述也不能原封不动套用。

操作数、内存与最坏退化

在向量及b位签名都能装入机器字、位提取和容器访问按常数成本的模型下，构建先抽取Lb个位位置，再处理Ln个签名，每个签名提取b个位，需要O(Lb(n+1))次基本工作。空数据也要支付抽样与空表创建成本。索引至少存Lb个位位置和Ln条桶内ID引用；原始向量存储另计，桶字典、签名和Python对象也要付空间。

设一次查询候选数为C。计算签名耗O(Lb)，合并桶还需读取实际桶项数，记为T，T最多Ln；精确距离和排序耗O(C+C log(C+1))。候选去重和字典访问的期望成本依赖哈希容器假设，不能只报O©而漏掉跨表重复读取。

最坏C=n、T=Ln，索引可以比精确扫描更慢。D超过机器字长时，异或、bit_count和抽位还涉及多字成本；即使D很小，有放回抽样仍允许b很大，签名的移位、求和与哈希也会产生多字成本。Python实现不证明任意D或b下这些运算都是常数时间。这里也没有借用提前找到一个半径内近邻就停止的LSH算法查询界，接口实际收集候选并排序取top-k。

同一数据上的测量

实现接口为HammingLSH(values,dimensions,bits,tables,rng)，query(value,k)返回ID列表与候选数。仓库根目录运行：

1
python3 examples/advanced-algorithms/check_hamming_lsh.py

本次Python 3.14.4、macOS arm64运行退出码为0。D=32、n=512，生成64个查询，每个从数据中选一点翻转三个不同位，k=5。数据种子20260920、索引种子20260921，九组参数共用同一数据与查询。

精确参照枚举全部ID并按完整距离与ID排序。这是朴素扫描加全排序基线，时间含O(n log(n+1))排序，没有优化成只维护k项的选择算法。recall@5定义为索引答案与该精确答案的ID交集大小除以5；一般n<k时分母用min(k,n)，空真值不参与平均。

每种方法先热身一次，之后五轮交替运行顺序，计时包含全部64个查询及结果列表生成，排除索引构建与验证。构建时间另记，GC保持开启；下表是本次五轮批次耗时的中位数，不是单次请求延迟或置信区间。

b L 平均recall@5 索引字节 扫描批次中位数ms 索引批次中位数ms
4 1 119/320 20704 5.371 0.409
4 4 241/320 60764 5.634 1.579
4 16 157/160 220052 5.434 4.271
8 1 53/320 31912 5.502 0.116
8 4 9/20 106228 5.595 0.391
8 16 31/40 463204 5.402 1.404
12 1 33/320 60416 5.536 0.114
12 4 43/160 259828 5.350 0.321
12 16 149/320 1119328 5.408 1.147

这里的索引字节是按对象身份去重后，抽样位置与桶容器、签名键和ID的getsizeof总和，不含实例、数据副本或分配器，非RSS。实现另复制一份数据列表，原始数据及其副本空间不能因表中未计就视为不存在；逻辑桶内ID引用数为Ln。

b=4从一张表增加到16张，平均recall由119/320升到157/160，耗时和索引空间也上升。b=12、L=16保存更多小桶对象，却只得到149/320；参数变化并不保证质量与字节数单调对应。所有配置在这组小数据上比朴素全排序基线快，不能外推为任意n、D、查询分布或优化扫描实现的优势。

检查还独立枚举42组小维度抽样概率；对九配置的576个查询，绕开桶字典遍历数据，逐位判断是否符合任一表的抽样条件，再核对候选与重排结果。重复向量、空数据、k>n、8种非法输入和前述坏表反例均实际检查。

完整五轮计时、逐查询recall、候选数、源码与输入SHA、时钟分辨率保存在writing-plans/advanced-algorithms/evidence/hamming-lsh-results.json。有限抽样枚举检查公式的这些实例，固定种子矩阵记录实际测量；一般碰撞公式仍由独立抽位的概率推导支持。

HNSW的参数不属于碰撞公式

HNSW通过分层近邻图搜索候选。原论文的M控制图连接规模，efConstruction控制构建时的候选搜索宽度，查询ef控制搜索过程保留的候选集合大小。ef不是距离计算总次数的硬上限，不能用它直接代替查询操作数。

它没有本篇“独立抽坐标、按签名相等入桶”的随机过程，因此不能把(1−p_d)^L贴到HNSW上。比较其速度与质量需要在相同数据、距离、答案定义和资源口径下测量；论文数据集上的经验曲线也不是任意输入的召回率保证。

本篇没有构建或测量HNSW索引。其机制用于区分证明对象，全部运行数字只来自位抽样LSH与精确扫描。

练习

  1. D=8、d=2、b=3、L=4时，写出指定点被漏掉的精确概率表达式。若4张表完全相同，哪一步乘法失效？
  2. 数据含多个不同ID的同一向量，k=3。解释为什么候选去重应按ID进行，并分别说明固定ID排序与只按距离评估时recall定义可能怎样变化。

参考资料