我正在处理一个可能会出现哈希碰撞问题的系统。基本上,该系统引用哈希表+树形结构中的项目。但是,所涉及的系统首先将包含结构路径的文本文件编译成包含散列值的二进制文件,以提高性能。然而,由于这个原因,碰撞非常严重,因为结构不能存储具有相同哈希值的2个项目;请求项目的部分将没有足够的信息来知道它需要哪一个。
我的初始想法是使用2个哈希,可以使用2个不同的算法或相同的算法两次,并使用2个盐来使其更加抗碰撞。对于不同哈希算法具有相同哈希的两个项目非常不可能。
我希望出于空间原因保持哈希值为32位,因此我认为可以使用两个16位算法而不是一个32位算法。但是,那样不会增加可能哈希值的范围...
我知道转换为两个32位哈希将更加抗碰撞,但我想知道转换为2个16位哈希是否比单个32位哈希至少有一些收益?我不是最擅长数学的人,所以我不知道如何开始检查答案,除了强制执行它...
关于系统的一些背景:
项目由人命名,它们不是随机字符串,通常由单词、字母和数字组成,没有空格。这是一个嵌套的哈希结构,所以如果你有像{a => {b => {c => 'blah'}}}这样的东西,你将通过获取a/b/c的值来获得'blah'的值,编译的请求将是3个哈希值在直接序列中,即a、b和c的哈希值。
只有在给定级别上出现碰撞时才会出现问题。顶层项目和较低级别之间的冲突是可以接受的。你可以有{a => {a => {...}}},几乎保证在不同级别上发生碰撞(不是问题)。
实际上,任何给定级别可能只有少于100个需要散列的值,并且在同一级别上不会重复。
为了测试我采用的哈希算法(忘记了哪一个,但我没有发明它),我下载了整个CPAN Perl模块列表,将所有名称空间/模块拆分为唯一单词,最后对每个单词进行哈希搜索冲突,我遇到了0个冲突。这意味着算法对CPAN名称空间列表中的每个唯一单词具有不同的哈希值(或者我做错了)。这对我来说足够好,但它仍然在我的脑海中挥之不去。
我的初始想法是使用2个哈希,可以使用2个不同的算法或相同的算法两次,并使用2个盐来使其更加抗碰撞。对于不同哈希算法具有相同哈希的两个项目非常不可能。
我希望出于空间原因保持哈希值为32位,因此我认为可以使用两个16位算法而不是一个32位算法。但是,那样不会增加可能哈希值的范围...
我知道转换为两个32位哈希将更加抗碰撞,但我想知道转换为2个16位哈希是否比单个32位哈希至少有一些收益?我不是最擅长数学的人,所以我不知道如何开始检查答案,除了强制执行它...
关于系统的一些背景:
项目由人命名,它们不是随机字符串,通常由单词、字母和数字组成,没有空格。这是一个嵌套的哈希结构,所以如果你有像{a => {b => {c => 'blah'}}}这样的东西,你将通过获取a/b/c的值来获得'blah'的值,编译的请求将是3个哈希值在直接序列中,即a、b和c的哈希值。
只有在给定级别上出现碰撞时才会出现问题。顶层项目和较低级别之间的冲突是可以接受的。你可以有{a => {a => {...}}},几乎保证在不同级别上发生碰撞(不是问题)。
实际上,任何给定级别可能只有少于100个需要散列的值,并且在同一级别上不会重复。
为了测试我采用的哈希算法(忘记了哪一个,但我没有发明它),我下载了整个CPAN Perl模块列表,将所有名称空间/模块拆分为唯一单词,最后对每个单词进行哈希搜索冲突,我遇到了0个冲突。这意味着算法对CPAN名称空间列表中的每个唯一单词具有不同的哈希值(或者我做错了)。这对我来说足够好,但它仍然在我的脑海中挥之不去。