假设我有大量的文档，我以某种方式哈希（例如Sha256）并存储它们的哈希值。是否有一种哈希技术可以让我通过查看它们的哈希来检查string1中是否包含string2？我想避免加载全文。
澄清一下：这与sim / min-hashing无关，寻找近似重复或Levenshtein距离。我正在寻找一种哈希算法，它可以通过查看哈希来以某种方式让我检查子串。
EG
var string1 = "bla bla bla cat dog bla bla";
var string2 = "cat dog";
var hash1 = HashAlgo(string1); // <-- magic goes here
var hash2 = HashAlgo(string2);
Assert.IsTrue(string1.Contains(string2));
Assert.IsTrue(hash1.Contains(hash2)); // <--- magic goes here
如果你考虑一下，这是可能的，这是没有意义的。
首先，所有SHA256哈希都具有完全相同的长度。我的答案基于SHA256，但据我所知，这适用于任何散列方法。
较大文件的哈希不可能包含两个较小的文件的哈希值，因为只有当所有三个哈希值彼此相等时才可能。
其次，想想我可以从1000个字符的文档中获取多少100个字符的子串。它不仅仅是10（如1000/100 = 10），而是900.将子串表示为索引边界，有很多可能性：
共有900种选择。假设您的初始文档没有以任何方式重复（因此您没有得到两个相等的子串），这将导致900（假定的）唯一哈希值。
这900个唯一的哈希不能都是初始文件哈希的子串。
此外，考虑到我们甚至没有想过其他长度的子串！假设任何可能的子串长度，你最终可以得到999,000个不同的子串（但当然其中一些会有重复）
而这甚至没有考虑到原始文档可能超过1000个字符的事实。对于具有n个字符的任何文档，您可以期望找到n *（n-1）个子串（长度在1和n之间），主要是唯一的哈希值。
只要你处于1077（更准确地说是2256）的数量级，这种可能值的扩展只会是平稳的，因为这可能存在多少个独特的SHA哈希值。 餐巾的背面，这将是一个1038字节的文件。一旦你到达那个文件大小，所有可能的子串（任何长度）都必须包含至少一个副本。
我想你可以看出为什么你的建议在数学上是不可能的。
我会将此作为旁注，但superpermutations是一个值得关注的切入话题，以了解这是多么不可能。对于7个唯一字符，如果要包含7个字符的所有可能排列，则需要5907个数字的superpermutation。这是我们发现（最小）superpermutations的最高N.
对于900个唯一哈希（=十六进制字符的唯一排列）的初始示例，它们都将包含在“主”哈希中，主哈希的最小所需长度简直无法计算。但是作为一个绝对最小值（你可以证明不能进入），你的主哈希值必须是963个字符长（如果你假设每个64个字符的子字符串总是给你一个唯一的新哈希）