java哈希函数冲突

试图在Java中编写我自己的哈希函数。我知道这与java实现的一样，但是想自己测试一下。当我输入不同的值时我碰到碰撞，我不知道为什么。java哈希函数冲突

public static int hashCodeForString(String s) { 
int m = 1; 
int myhash = 0; 
    for (int i = 0; i < s.length(); i++, m++){ 
    myhash += s.charAt(i) * Math.pow(31,(s.length() - m)); 
    } 
return myhash; 
}

来源

2016-07-25 Earl Clark

'Math.pow（...）'返回一个double。这是否编译？ –

编译，是 –

Java String hashCode实现不使用'Math.pow'，而是使用int数学运算，并且允许int overflow作为计算的一部分。你的计算没有，这是一个巨大的差异。 –

请记住只是如何哈希表（任何语言...）实际上作品： 它由（通常是素数）数量的“桶”。散列函数的目的仅仅是将任何传入的键值转换为桶编号。（最糟糕的情况是，输入密钥的100％总是在一个桶中结束，留下“链接列表”。）您只是努力设计一个“典型”产生的散列函数一个“分散的”值分布，因此，当计算出模块时，“大部分时间内大部分桶”将被“或多或少地相等”填充。 （但要记住：你永远无法确定。）

“冲突”是完全可以预料的：事实上，“他们发生的事情。”

在我的愚见，你是“过度思考”的散列函数：我没有看到任何令人信服的理由使用Math.pow()。预计您生成的任何值将通过取其桶的数量的绝对值模转换为散列桶编号。最好的方法来看看你是否想出了一个好的（对于你的数据...）是观察桶尺寸的结果分布。（您的目的是否“足够好”？）

来源

2016-07-25 02:40:01

java哈希函数冲突

回答

相关问题