将相似输入映射为相似输出的哈希函数？

Question

是否有一种哈希函数，其中输入中的小变化导致输出中的小变化？例如，类似于：

hash("Foo") => 9e107d9d372bb6826bd81d3542a419d6
hash("Foo!") => 9e107d9d372bb6826bd81d3542a419d7 <- note small difference

- Paul Wicks

---

那将是一个非常糟糕的哈希算法... - skaffman

对于密码哈希函数来说，是的，这样做是不好的，但我想将其用于其他方面。 - Paul Wicks

我认为您需要提供更多有关该函数预期目的的细节。确实没有具有该属性的加密哈希函数，但也许您正在寻找其他东西？ - Kris

"小变化"在输出中的定义是什么？是编辑距离（将哈希视为字符串）还是数值的数学距离（将哈希视为整数）？ - Rafał Dowgird

Answer 1

我不会称这为哈希，因为哈希的目的恰恰相反。但是，考虑到您所述的输入小变化产生小输出变化的目标，我建议使用soundex函数或Ratcliff算法。

- Chris Judge

Answer 2

我建议使用Mark Manasse的simhash算法（链接）。

- Jeff Kubina

Answer 3

一个简单的解决方案是对所有字节进行异或运算，然后取模N。例如，对于一个64位哈希值，你可以执行(input[0] ^ input[8] ^ input[16]) + 256*(input[1] ^ input[9] ^ input[17])等操作。 因此，"Foo"的哈希值为"Foo\0\0\0\0\0"，"Foo!"的哈希值为"Foo!\0\0\0\0"。

- MSalters

Answer 4

局部敏感哈希（LSH）降低高维数据的维度。LSH将输入项哈希，使得相似的项以高概率映射到同一个“桶”中：

https://en.wikipedia.org/wiki/Locality-sensitive_hashing

另请参见：https://en.wikipedia.org/wiki/Perceptual_hashing

这里有一个关于DNA序列的感知哈希的好例子：

http://arxiv.org/pdf/1412.5517.pdf

- gkcn