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

Question

开发一个哈希函数，为给定的交通牌照号码生成一个介于 0-4999（含）之间的索引值。你的散列函数应该产生尽可能少的冲突。哈希函数应该使用许可证号的属性。哈希方法应将许可证号作为单个字符串和 return 索引值。我们假设许可证号采用以下格式：城市代码是 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（最大值）。

65HNM25 93DTV23 94WPX23 31RKK46 15YXX90 31MDV74 45BOG99 65JRM50 77VXR55 39TKY41 80MJU73 63QYE57 38FCO80 45欧瑞16 17CHN73 70SXR63 87CVM74 27EEE85 32PFJ91 50PBA66 70TVK72 15YLS20 80MPM74 21ZRN20 36VVE84 58IDW24 77VDC89 19BVK93 28SUF63

Answer 1

你把车牌分成三部分没问题。但是将中间值转换为一个数字，散列它，然后将两个外部字符串相加，将其全部转换为一个整数，然后最后执行一个 modulo 就......很尴尬。

我会先将前缀 (10-99) 转换为整数，然后减去 10 以获得范围 0-89。

然后，对于每个字母，我将结果乘以 26，然后加上字母的索引 (0-25)。

第三，我将整个结果乘以90（最后部分的范围），将最后2个字符转换为整数，减去10将10-99范围转换为0-89，然后添加到之前的结果。

最后，mod 5000 的结果达到所需的 0-4999 范围。

伪代码：

result = toInt(prefix) - 10

foreach letter in middle:
    result = result * 26  + ( letter - 'A' )

result = result * 90  +  ( toInt(suffix) - 10)

result = result % 5000

Answer 2

你的问题不是你的代码，而是数学。即使是一个（对你来说很完美，但不是很有用）产生连续哈希的哈希码，然后是 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);

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

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

How to Develop a Hash function for traffic license numbers?

java

data-structures

hash

hashtable