java - 是否可以通过 "hash"数字比较两个字符串？

Question

我有一个永远丢失的字符串。我唯一拥有的是一些神奇的哈希值。现在我有了一个新字符串，它可能与丢失的字符串相似或相同。我需要找出它有多近。

Integer savedHash = 352736;
String newText = "this is new string";
if (Math.abs(hash(newText) - savedHash) < 100) {
  // wow, they are very close!
}

是否有用于此目的的任何算法？

附言。文本长度不固定。

页数。我知道通常的哈希码是如何工作的。我对一种工作方式不同的算法很感兴趣，它能给我上面解释的功能。

pps。在一个非常简单的场景中，这个 hash() 方法看起来像:

public int hash(String txt) {
  return txt.length();
}

Answer 1

标准散列在这种情况下不起作用，因为关闭散列值并不意味着关闭字符串。事实上，大多数哈希函数旨在为相近的字符串提供非常不同的值，以便为任何给定的输入字符串集创建哈希值的随机分布。

如果您可以访问这两个字符串，那么您可以使用某种字符串距离函数，例如 Levenshtein distance .这会计算两个字符串之间的编辑距离，或将一个字符串转换为另一个字符串所需的编辑次数。

然而，在这种情况下，最好的方法可能是使用某种 fuzzy hashing技术。这样您就不必存储原始字符串，并且仍然可以获得一些相似性度量。