局部敏感哈希索引（Locality-Sensitive Hashing，LSH）是一种用在高维数据检索上的技术，特别适合近似最近邻搜索（Approximate Nearest Neighbor Search）这类问题。在高维空间里，传统的线性搜索会非常慢。LSH 的思路是把相似的数据点映射到同一个哈希桶（或相邻的桶）里，从而把检索做得更快。

我们先简单过一遍算法过程，弄清楚它的基本思路。假设有 7 个数据点，如下图：

我们再准备两个哈希函数，这两个函数要满足下面的条件：

1. 如果 a、b 两个数据点本来就相似，哈希函数有较高的概率（p1）把它们映射到同一个桶里。
2. 如果 a、b 两个数据点本来就不相似，哈希函数有较低的概率（p2）把它们映射到同一个桶里。

普通哈希和局部敏感哈希的区别，如下图：

可以看到，A 和 B 是相似的，C 和 D 是不相似的。普通哈希只负责做映射，而局部敏感哈希会把相似的数据点映射到同一个桶里、或者相邻的桶里，把不相似的数据点散到不同的桶里。

LSH 能在高维数据空间里找出相似的数据项，哪怕它们在空间中的绝对位置离得不算近，这就是所谓的”局部敏感性”。也正因如此，LSH 适合那些”找相似项”而非”精确匹配”的场景。

注意：局部敏感哈希是基于概率的，并不能百分之百保证上面说的两个条件。

不同的相似度度量方式，对应的、能满足上面两个条件的哈希函数也不一样。我们接着上面的例子，假设现在拿到两个满足条件的哈希函数，桶的数量设为 3，那么：

7 个数据点经过 hash-1、hash-2 两个函数分桶之后，结果如上图。来了一个查询数据点，先通过这两个哈希函数找到它落在哪个桶，然后就在这个桶或相邻桶里做最近邻搜索，如下图：

拿到候选数据点之后，再逐一做相似度比较，挑出真正相近的，如下图：

从这个过程能看出来，搜索时由于 LSH 会把相似数据项聚到同一个桶，查询时就只需要搜和查询项同桶的那批点，搜索空间和计算量都大大缩小了。

另外，每个局部敏感哈希函数都可以理解成从一个不同角度去观察这组向量，哈希函数越多，观察的角度就越多，搜索精度也越高，但代价是计算量会上去。