Hashing

[Lukases2]

Hallo,

ich habe folgende Aufgabe:

Gegeben seien Wörter der Form Ziffer [Ziffer] Buchstabe. Die eckigen Klammern drücken dabei optionale Teilwörter aus. Als Buchstabe sind die 26 Buchstaben des lateinischen Alphabets zugelassen, als Ziffern 0 bis 9.

Entwerfen Sie eine Hashfunktion, die sämtliche Wörter exakt gleichmäßig auf eine 143 Plätze umfassende Tabelle (indiziert von 0 bis 142) verteilt.

Folgendes habe ich mir überlegt:

Wenn ich die nur die obligatorischen Teilwörter verwende, komme ich auf 10 x 26 = 260 verschiedene Teilwörter. Die kann ich schon mal nicht gleichmäßig auf 142 verschiedene Tabellenplätze verteilen. Auf diese Weise habe ich rechnerisch schon ein wenig herum experimentiert, aber ich bin zu keinem Ergebnis gekommen. Hat jemand vielleicht eine Idee?

 

[Tobse]

Du hast insgesamt 10 x 260 + 100 * 26 = 2860 Möglichkeiten. 2680 / 143 = 20. Wenn du also immer 20 Möglichkeiten zu einem Hashwert zusammenfasst, geht das ganze genau auf.

Jetzt musst du im prinzip nurnoch die umrechnung von der "Ziffer [Ziffer] Buchstabe" Form in eine Zahl zwischen 1 und 2860 realisieren.

 

[Lukases2]

Ich habe jetzt die Zahlen so zugeordnet:

00A := 0
00B := 1
...
00Z := 26
01A := 27
01B := 28
...
99Z := 2599

+

0A := 2601
0B := 2602
...
9Z := 2860

Ich habe also die Werte ohne optionale Ziffer durchnummeriert und strikt von den Werten mit optionaler Ziffer getrennt.
Wie kann ich das jetzt noch formal korrekt darstellen?

 

[Tobse]

Was meinst du mit "formal korrekt darstellen"? Bei dieser Hashfunktion könnte man noch eine Hashtabelle anlegen. Bei größeren Hashwerten (wie z.B. MD5, SHA) verweist man immer auf die Umrechnungsformel.

 

[Lukases2]

In der VL hatten wir sowas wie
h(x) := x mod 5
um Werte in die Hashtabelle einzufügen. Ist sowas hier auch möglich?

 

[Tobse]

Ja. Du brauchst eine Formel um die Ziffern und Buchstaben in Zahlen zwischen 1 und 2680 umzurechnen, ich nenne sie jetzt mal s(z, b) und s(z1, z2, b)

Dann kannst du Schreiben:
h(z, b) := ceil(s(z, b) / 20)
h(z1, z2, b) := ceil(s(z1, z2, b) / 20)

 

[Lukases2]

ceil() drückt die Werte also quasi in die Tabelle?

 

[Tobse]

ceil() drückt die Werte also quasi in die Tabelle?

So kann man das sagen, ja. Ohne das ceil bekommst du ja Nachkommastellen, also im Endeffekt wieder 2680 verschiedene Zahlen.

EDIT: Das ceil ist quasi die eigentliche Hashfunktion bei der ganzen Sache.