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

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

我有两组字符串值，并且在运行时提供了一个值。我需要从第二组中获取所有字符串的列表，该列表以第一组中的字符串开头并以查询值结束。这是一个大大简化的表示形式和描述:

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

我的搜索尝试找到支持该属性的哈希函数失败，很可能是由于未使用正确的关键字进行搜索而导致的，因此，即使您可以为我在上面描述的内容描述正确的术语，也会有所帮助

最佳答案

这是一个:

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的内存，这不是最快的方法，并且不可重复，但是足以用于概念验证。

关于java - 是否有一个字符串哈希函数支持h(x)+ h(y)= h(x + y)，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/29072253/