Hashing
Verfasst: 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?
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?