前言
普通的哈希函数是为了建立索引，提高数据查询速度；或是为了数据加密，防止数据篡改。哈希函数一般是不具有相似相邻性的，即原来的状态是相邻或相似的，通过哈希映射后依然是相邻或相似的。而在数据查重或索引时，这种相似相邻的性质能够起到很大的作用，比如在推荐领域，我们经常使用余弦距离作为评价指标判断用户是否对物品感兴趣，余弦距离越小说明用户对物品越感兴趣。当需要对用户进行推荐时，不可能会对所有物品都计算一遍余弦距离，这时候就可以利用相似相邻的性质在大量的物品向量中寻找和用户向量相似的物品向量，这样的物品向量往往和用户向量会有更小的余弦距离。局部敏感哈希和SimHash是两种可以利用相似相邻性质的哈希算法。
局部敏感哈希
局部敏感哈希需要满足以下两个性质：
(1) 如果$d(x,y)\le d_1$，则$h(x)=h(y)$的概率$\ge p_1$
(2) 如果$d(x,y)\ge d_2$，则$h(x)=h(y)$的概率$\le p_2$
其中$d_1\le d_2$，$p_1\ge p_2$。符合上述两个性质的哈希函数称为$(d_1,d_2,p_1,p_2)-sensitive$。局部敏感哈希就是使用这些哈希函数进行映射，使得映射到同一个桶的对象相邻或相似的概率尽量大，映射到不同桶的对象相邻或相似的概率尽量小。
例子：汉明距离
当使用汉明距离作为不同对象之间的距离度量时，可以设计一个哈希函数，这个哈希函数等概率地选择对象的01向量中的一位作为该对象的哈希值。我们现在分析一下若两个01向量的汉明距离是$d$时，两个01向量被分到同一个桶的概率为$1-\frac{d}{n}$，其中$n$是01向量的长度。可以看到，这个哈希函数是$(d_1,d_2,1-\frac{d_1}{n},1-\frac{d_2}{n})-sensitive$的。但是这个哈希函数存在一个问题，因为只有两个桶，所以$p_2$的值也很大，我们的目标是希望在增大$p_1$的同时也可以缩小$p_2$。一种方法是增大哈希函数的桶数，比如随机选取$k$个位置的值，这样桶的个数就变成$2^k$。这种方法可以缩小$p_2$，防止误判，但同时也缩小了$p_1$，降低了查全召回。但是如果我们是为了找最相似的，增大$p_1$可以通过缩小$d_1$的方式得到。除了汉明距离，余弦距离，杰卡德距离，欧几里得距离均可以设计相应的哈希函数，详情可查看博客：https://blog.csdn.net/icvpr/article/details/12342159
SimHash
SimHash主要用于网页文本内容去重，原理是对相似的对象有大概率映射到相似的桶中。与局部敏感哈希不同，SimHash不要求映射到相同的桶的，只需要哈希值也是相似的即可。SimHash可以分为五个步骤：分词、Hash、加权、合并、降维。
分词
分词步骤是对文本内容进行分词，得到一个一个的词。同时，分词后每个词都可以得到一个权重。
Hash
哈希是对分词后的文本的每一个词单独进行哈希，每个词都能得到一个01串。
加权
将每个词的01串中的0替换成-1，每个词的串都乘上分词步骤中得到的权重。
合并
将文本中每个词的串合并加起来，得到一个关于文本的数字串。
降维
将得到的数字串，大于0的部分替换成1，小于0的部分替换成0，得到一个01串
比较
每个文本都得到一个01串，规定如果两个文本的01串的汉明距离小于等于3时，两个文本就是非常相似的。在比较时使用到利用鹤巢原理，将01串分成四部分，当两个01串的汉明距离小于等于3时，总是会有一部分相同的，可以基于此过滤掉大部分不符合条件的，再对剩余的少数进行匹配。因为是使用的汉明距离，所以也可以使用前面提到的局部敏感哈希进一步哈希提高查询匹配效率。