Hashing

Bei Postings zu Aufgabe Nr. x auf Blatt Nr. y lassen Sie Ihr Betreff bitte mit "y.x: " beginnen, gefolgt von einer möglichst präzisen Überschrift, danke!

Moderator: Algorithmen und Datenstrukturen

Forumsregeln
Bei Postings zu Aufgabe Nr. x auf Blatt Nr. y lassen Sie Ihr Betreff bitte mit "y.x: " beginnen, gefolgt von einer möglichst präzisen Überschrift, danke!
felixd
Nichts ist wie es scheint
Beiträge: 23
Registriert: 14. Mai 2017 22:15

Hashing

Beitrag von felixd » 15. Mai 2017 21:16

Hallo,

ich habe eine theoretische Frage.

Betrachten wir die rudimentäre Hashfunktion für Strings, mit c einer Konstante und z dem Zeichen an der Stelle, sowie der länge l:

\((\sum^{l}_{i=0} c_i * z_i) \mod l\)

Nun kann dabei, selbst bei Verwendung von 64 bit Zahlen, natürlich leicht ein Überlauf auftreten. Daher wird folgende Formel empfohlen:

\((\sum^{l}_{i=0} c_i * (z_i \mod l)) \mod l\)

Aber kann uns eine Überlauf nicht egal sein? Es passiert doch deterministisch und maschinenunabhängig gleich (zumindest in Java). Wir würden uns insgesamt l - wenn auch günstige - Rechenoperationen sparen und müssten am Ende ggf. nur noch das Ergebnis wieder in den positiven Bereich "shiften".

Wäre das eine sinnvolle Alternative?

Prof. Karsten Weihe
Moderator
Moderator
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Hashing

Beitrag von Prof. Karsten Weihe » 16. Mai 2017 06:43

felixd hat geschrieben: Wäre das eine sinnvolle Alternative?
In Java wäre das zumindest eine gangbare Alternative (ob sinnvoll, weiß ich nicht). Aber die Vorlesung sollte nicht auf Java-Spezifika basieren, daher diese Überlaufbehandlung.

KW

Antworten

Zurück zu „AuD: Theoretische Aufgaben“