场景
海量高维数据查找与某个数据最相似的一个或者多个数据。与其它基于 Tree 的数据结构，诸如 KD-Tree、SR-Tree 相比，它较好地克服了 Curse of Dimension，能够将 KNN 的时间复杂度缩减到 sub-linear。LSH 多被用于文本、多媒体（图像、音频）的相似性判断。
simhash
谷歌的文档去重算法。主要步骤：
- 对文本进行分词和加权，权重越大，单词重要性越高
- 对单词进行 hash：
- 加权：对 hash 进行加权
- 合并：单词 hash 相加，得到句子的 hash
- 降维：每一位大于 0 记为 1，小于 0 记为 0
比较的时候只需要计算两个 hash 的海明距离：两个二进制串对应的位有几个不一样，那么海明距离就是几，值越小越相似（异或）。
局部敏感
存储：
1、将一个 64 位的 simhash code 拆分成 4 个 16 位的二进制码。（图上红色的 16 位）
2、分别拿着 4 个 16 位二进制码查找当前对应位置上是否有元素。（放大后的 16 位）
3、对应位置没有元素，直接追加到链表上；对应位置有则直接追加到链表尾端。（图上的 S1 — SN）
查找：
1、将需要比较的 simhash code 拆分成 4 个 16 位的二进制码。
2、分别拿着 4 个 16 位二进制码每一个去查找 simhash 集合对应位置上是否有元素。
2、如果有元素，则把链表拿出来顺序查找比较，直到 simhash 小于一定大小的值，整个过程完成。
与一般 Hash 的区别
局部敏感 hash 可以比较相似度，普通的 hash 不可以
