是否有一种字符串哈希函数支持h(x) + h(y) = h(x+y)？

Question

我将尝试使用字符串的哈希值来节省空间。我有一个非常具体的要求，简化描述如下：

我有两组字符串值，并在运行时提供一个值。我需要获取第二组中所有以第一组字符串开头并以查询值结尾的字符串列表。以下是一个显著简化的表示和描述：

set1:
my_test_val_1
my_test_val_2

set2:
my_test_val_1_extended_to_another_value
my_test_val_2_extended_as_well

我的目标是保持这些集合的哈希值如下：

set1:
hash(my_test_val_1)
...

set2:
hash(my_test_val_1_extended_to_another_value)

为了节省空间并且当查询中出现“_extended_to_another_value”时，使用具有加法分配属性的哈希函数执行以下操作：

hash(my_test_val_1) + hash('_extended_to_another_value') = hash_value_to_search

我尝试寻找一个支持此属性的哈希函数，但我的搜索尝试失败了，很可能是由于没有使用正确的关键词进行搜索，因此即使您可以描述上述内容的正确术语，也会有所帮助。

- mahonya

---

你只依赖于保存哈希值吗？你处理哈希冲突的计划是什么？ - Jon Skeet

从生成的哈希函数中，您需要哪些属性？最终哈希可以使用多少位？ - dhke

需要获取第二个集合中所有以第一个集合中的字符串开头并以查询值结尾的字符串列表。[你是否在寻找Trie？]（http://en.wikipedia.org/wiki/Trie） - Sergey Kalinichenko

也许类似于前缀哈希树的数据结构在这里是相关的？ - Kris

@JonSkeet 是的，哈希碰撞是个问题，但我可以接受低碰撞率，并进行一些广泛的测试（这些都是合成数据，因此我可以在大规模上进行测试），以确定是否存在任何碰撞率。 - mahonya

这个问题的一个有趣的推广是，是否可能找到任何操作和哈希函数 h、# 和 §，使得 h(x) # h(y) = h(x § y)。 - Lii

Answer 1

这是一个例子：

import java.util.Random;
public class StringHasher {
    private static int[] CHAR_HASHES = new int[65536];
    static {
        Random rng = new Random();
        for(int k = 0; k < 65536; k++)
            CHAR_HASHES[k] = rng.nextInt();
    }
    public static int hash(String s) {
        int result = 0;
        for(int k = 0; k < s.length(); k++) {
            result += CHAR_HASHES[s.charAt(k)];
        }
        return result;
    }
}

事实证明，任何这样的哈希都必须通过添加字符串组成字符的所有哈希值来构建 - 否则，例如 h("hello") = h("h") + h("e") + h("l") + h("l") + h("o") 将不成立。

注意：这意味着您无法拥有非常抗碰撞的哈希，因为每个包含相同字符的字符串将具有相同的哈希，如前一段所述。

为每个单字符字符串选择随机值的哈希应该提供接近最佳的碰撞抵抗力，平均而言。这会浪费256 KiB的内存，也不是最快的方法，也不可重复，但足以作为概念验证。

- user253751

---

我会考虑使用质数来填充CHAR_HASHES。此外，对于哈希线性性的后果进行观察也是值得的。 - Kris

@Krystian 我不知道如何选择具有良好碰撞抗性的字符哈希（但随机数可以使用）。 - user253751

Answer 2

您可以使用一些主流的哈希算法，并尝试使用在线数据库进行破解。如果x和y足够短，您可能会在MD5或SHA在线破解哈希数据库中找到它，如果您解密了它，那么您就可以继续使用您的算法。

如果您的应用程序是在线的，它可以使用这种方法。缺点是在某些极端情况下，您可能会得到与正确值相同的哈希代码的错误值，但这种情况的概率非常低。

这基本上是一种黑客行为，但是您正在根据自己的要求进行这种操作，因此这可能对您来说是可以接受的。

以下是在线哈希数据库的示例：

• http://www.md5online.org/
• http://www.dehashme.com/

- Saša