localitysensitivehashing(LSH)，中文名为局部敏感哈希，用于解决在高维空间中查找相似节点的问题。如果直接在高维空间中进行线性查找，将面临维度灾难，效率低下，LSH的作用就是把原来高维空间上的点都映射到一个或多个hashtable的不同的位置上，这个位置术语上称作桶(buckets)。

　　lsh映射原则是什么

　　它映射的原则是：原来在高维空间中就很接近的点，会以很大的概率被映射到同一个桶中。这样，如果再给你一个高维空间上的点，你只需要按照同样的方式也把这个点映射到一个桶中，而在同一个桶中点都是有很大概率在原来高维空间中是相似的，这样就可以直接对这个桶中的元素进行查找即可，大大的提高了查找的效率。

　　(1)一个或多个hashtable：为什么要多个hashtable?

　　(2)很接近：以怎样的方式来衡量高维空间中的点是接近的。

　　(3)很大的概率被映射到同一个桶中：如何保证原来高维空间中相近的点以很大的概率被映射到同一个桶中。

　　接下来就具体说说上面的3个问题，为了方便理解，按照3,2,1的顺序来分别解释：

　　lsh的做法有啥

　　如何保证原来高维空间中相近的点以很大的概率被映射到同一个桶中：

　　LSH的做法是在原来的高维空间中随机均匀的画很多个平面，具体有多少个可以用一个参数k来表示。高维空间中的每一点和这些平面就会有一个位置划分关系，比如点在平面上还是在平面下，分别对应1和0，这样每一个点就会形成一个长度为k的一个编码，被叫做汉明编码(hamingcode)，其实就是一串0,1组成的二进制编码。汉明距离被定义为：两个汉明编码中每一位有多少是不同的数量，它就是一个数字，代表这2个汉明编码有多少位是不同的。这样，原来高维空间中很接近的点，它们对应的汉明编码也应该大致相同，汉明距离就应该很小，完全相同则为0，因为它们如果在原来高维空间中很接近，则它们和这些平面的关系也很接近，对应的汉明编码也就很相似。如果把每一个汉明编码看作是一个桶，这样就相当于把原始高维空间中的相近的点以一个很大的概率都映射到了同一个桶里面了。这个概率具体有多大呢，这就和原始空间被划分的细致程度有关了，也就是平面的个数k，这个k越大，对应的所有可能的汉明编码数量也就是2k个，也就是桶的个数为2k个。