Seite 1 von 1

Hashing

Verfasst: 15. Mai 2017 21:16
von felixd
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?

Re: Hashing

Verfasst: 16. Mai 2017 06:43
von Prof. Karsten Weihe
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