java哈希函数冲突

Question

尝试用 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;
} 

Answer 1

请记住哈希表(任何语言...)实际上工作原理:它由一个(通常是素数)组成em>“桶”的数量。哈希函数的目的只是将任何传入的键值转换为桶号。 (最坏的情况总是 100% 的传入键最终都在一个存储桶中，留下“链表”。)您只需努力设计一个哈希函数，“通常”会生成“广泛分散”的值分布，因此，当以(质数...)桶数为模进行计算时，“大多数时候，大多数桶”将“或多或少相等” “填充。 (但请记住:你永远无法确定。)

“冲突”是完全可以预料的:事实上，“它们一直在发生。”

以我的愚见，您“过度思考”了哈希函数:我认为根本没有令人信服的理由使用 Math.pow()。期望您生成的任何值都将通过取其绝对值模存储桶数来转换为哈希存储桶数。查看您是否想出了一个好的方法(对于您的数据...)的最佳方法是观察存储桶大小的最终分布。 (对于您的目的而言，它“足够好”了吗？)