局部敏感哈希（Locality Sensitive Hashing）

局部敏感哈希索引（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 可以将相似的数据项映射到相同的桶中，因此在查询时，可以仅搜索与查询项相同桶中的数据点，从而大大减少了搜索的空间和计算时间。

另外，使用的每个局部敏感的哈希函数可以理解为对一个包含了信息的向量不同角度的观察，更多的哈希函数意味着更多角度的观察，可以提高搜索的精度，但可能会增加计算成本。