Wie entwickelt man eine Hash-Funktion für Verkehrslizenznummern?

Question

Entwickeln Sie eine Hash-Funktion, um einen Indexwert zwischen 0 und einschließlich 4999 für eine bestimmte Verkehrslizenznummer zu generieren. Ihre Hash-Funktion sollte so wenig Kollisionen wie möglich erzeugen. Die Hash-Funktion sollte die Eigenschaften von Lizenznummern verwenden. Hash-Methode sollte die Lizenznummer als eine einzelne Zeichenfolge nehmen und einen Indexwert zurückgeben. Wir gehen davon aus, dass die Lizenznummern das folgende Format haben: Der Stadtcode ist eine Zahl zwischen 10 und einschließlich 99. Drei Buchstaben sind eine Buchstabenkombination aus dem englischen Alphabet mit 26 Zeichen. Zweistellige Nummer ist eine Nummer zwischen 10 und 99 inklusive.

Ich schrieb etwas über diese Frage aber, Kollisionen gibt eine Menge (1800 für 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.

Dies sind nur einige Beispiele aus der Datei der Anzahl Verkehrszulassung. Kollisionen müssen 300 (maximal) sein.

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

Answer 1

Ihr Problem ist nicht der Code, sondern Mathematik.Selbst ein (ideal für Sie, aber nicht sehr nützlich) Hash-Code, der in Folge Hashes erzeugt, die dann mod 5000, dh

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

wird statistisch produzieren über 1800 Kollisionen und ist nicht besser als die einfachste Implementierung, was zu verwenden String des hashCode:

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

---

es ist eine dumme Bewegung, da sie keine realen Welt Verwendung hat.

Answer 2

Ihre Spaltung des Kennzeichens in 3 Teile ist in Ordnung. Aber das Umwandeln der Mitte in eine Zahl, das Hashing, das Hinzufügen der zwei äußeren Strings, das Umwandeln dieses Ganzen in eine Ganzzahl und das anschließende Ausführen eines Modulos, das ist ... peinlich.

Ich würde damit beginnen, das Präfix (10-99) in eine ganze Zahl zu konvertieren und dann 10 subtrahieren, um den Bereich 0-89 zu erhalten.

Dann würde ich für jeden Buchstaben das Ergebnis mit 26 multiplizieren und den Index des Buchstabens hinzufügen (0-25).

Drittens würde ich das ganze Ergebnis mit 90 multiplizieren (der Bereich des letzten Teils), die letzten 2 Zeichen in eine ganze Zahl umwandeln, 10 subtrahieren, um den 10-99 Bereich auf 0-89 zu konvertieren und zu addieren das Ergebnis von früher.

Schließlich mod das Ergebnis mit 5000, um zum erforderlichen 0-4999 Bereich zu gelangen.

---

Pseudo-Code:

result = toInt(prefix) - 10 

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

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

result = result % 5000