java - 奇数/素数桶的可变范围字符串哈希函数

Question

有谁知道用于可变范围的桶的哈希函数(对于字符串，如果它重要的话)，它总是奇数(或质数，如果需要的话)？

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

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

这里是 some quick test code I whipped up which asserts this .

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

Answer 1

以 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() 已经返回分布良好的值，只需使用质数作为除数取模即可得到良好的分布。