java - 如何开发交通牌照号的哈希函数？

Question

开发一个哈希函数，为给定的交通牌照号码生成介于 0-4999(含)之间的索引值。你的散列函数应该产生尽可能少的冲突。哈希函数应该使用许可证号的属性。哈希方法应将许可证号作为单个字符串并返回索引值。我们假设许可证号采用以下格式:城市代码是 10 到 99 之间的数字(含 10 和 99)。三个字母是26个字符的英文字母表中的任意字母组合。两位数是介于 10 和 99 之间的数字。

我写了一些关于这个问题的东西但是，碰撞很多(1800 for 5k)

    static long printValue(String s) {
    long result = 0;
    for (int i = 0; i < s.length(); i++) {
        result += Math.pow(27, MAX_LENGTH - i - 1) * (1 + s.charAt(i) - 'A');
    }

    result = result % 5009;


    return (int) result;
}

public int hashF(String str) {

    String a = str.substring(0, 2);
    String b = str.substring(5, 7);
    String middle = str.substring(2, 5);

    int q = (int) printValue(middle);

    String last = a + q + b;

    int index = Integer.parseInt(last);
    index = index % 5009;
    return index;




}

Link for orjinal file of licence numbers.

这些是交通牌照号文件中的一些示例。碰撞次数必须为 300(最大值)。

65HNM2593DTV2394WPX2331RKK4615YXX9031MDV7445BOG9965JRM5077VXR5539TKY4180MJU7363QYE5738FCO8045欧瑞1617CHN7370SXR6387CVM7427EEE8532PFJ9150PBA6670TVK7215YLS2080MPM7421ZRN2036VVE8458IDW2477VDC8919BVK9328SUF63

Answer 1

你的问题不是你的代码，而是数学。即使是一个(对你来说很完美，但不是很有用)产生连续哈希值的哈希码，然后是 mod 5000，即

10AAA10 -> 0
10AAA11 -> 1
... etc
99ZZZ99 -> 600 (90 * 26 * 26 * 26 * 90) % 5000

统计上会产生超过 1800 次碰撞，并不比使用 String 的 hashCode 的最简单实现好:

 int hash = Math.abs(number.hashCode() % 5000);

---

这是一个愚蠢的练习，因为它在现实世界中没有用处。