是否有支持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

我的搜索尝试找到支持此属性的哈希函数失败最可能是因为没有使用正确的关键字进行搜索,因此即使您可以为我上面描述的内容描述正确的术语,它也会有所帮助

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