3

有谁知道可变范围的桶的散列函数（对于字符串，如果重要的话），它总是奇数（或素数，如果需要）？

本质上，我正在寻找一个散列函数，它将在 n 个桶上提供均匀分布，其中 n 是奇数（或素数，因为 n 会很小）。

Java.hashCode()提供统一分布，但仅适用于 2 的幂。

这是我编写的一些快速测试代码，它断言了这一点。

我在CS Theory StackExchange上交叉发布了这个，因为它似乎介于理论和工程之间。

4

1 回答 1

2

以 37 作为存储桶长度运行您的程序，并将散列部分替换为

for (String key : keys) {
    int hash = key.hashCode();
    int index = Math.abs(hash % buckets.length);
    buckets[index] = buckets[index] + 1;
}

导致以下结果：

Bucket 0: 4152
Bucket 1: 2593
Bucket 2: 2703
Bucket 3: 2620
Bucket 4: 2742
Bucket 5: 2647
Bucket 6: 2707
Bucket 7: 2673
Bucket 8: 2664
Bucket 9: 2685
Bucket 10: 2734
Bucket 11: 2708
Bucket 12: 2661
Bucket 13: 2678
Bucket 14: 2681
Bucket 15: 2662
Bucket 16: 2682
Bucket 17: 2667
Bucket 18: 2619
Bucket 19: 2572
Bucket 20: 2608
Bucket 21: 2669
Bucket 22: 2670
Bucket 23: 2629
Bucket 24: 2748
Bucket 25: 2651
Bucket 26: 2618
Bucket 27: 2628
Bucket 28: 2740
Bucket 29: 2608
Bucket 30: 2650
Bucket 31: 2645
Bucket 32: 2687
Bucket 33: 2699
Bucket 34: 2627
Bucket 35: 2715
Bucket 36: 2558
Mean: 2702.7027027027025
Standard Deviation: 245.8085241264752

这看起来相当不错。

您不是在测试String.hashCode(). 如果 HashMap 的hash()方法使用密钥的 hashCode，并且旨在尝试为其容量获得均匀分布，则您正在测试分布，这必须是 2 的幂。如果hashCode()已经返回分布良好的值，只需取模使用素数作为除数将导致良好的分布。

于 2013-02-02T20:31:58.740 回答