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