Kennt jemand diese Hash-Funktion?

[Gast]

Hi Leute,

ich bin einen C-Quellcode am überarbeiten, in dem folgende Hash-Funktion für Strings vorkommt:
static int hash ( const char *szName, int maxsize, int length )
{
static int mmult[] = {
262139, 259459, 256889, 254291, 251701, 249133, 246709, 244247,
241667, 239179, 236609, 233983, 231289, 228859, 226357, 223829,
221281, 218849, 216319, 213721, 211093, 208673, 206263, 203773,
201233, 198637, 196159, 193603, 191161, 188701, 186149, 183761,
181303, 178873, 176389, 173897, 171469, 169049, 166471, 163871,
161387, 158941, 156437, 153949, 151531, 149159, 146749, 144299,
141709, 139369, 136889, 134591, 132169, 129641, 127343, 124853,
122477, 120163, 117757, 115361, 112979, 110567, 108179, 105727,
103387, 101021, 98639, 96179, 93911, 91583, 89317, 86939, 84521,
82183, 79939, 77587, 75307, 72959, 70793, 68447, 66103
};

int n = 0;
for (int j = 0; j < length; ++j )
{
int iName = szName[j];
n += mmult[j] * iName;
}
return ( abs ( n ) % maxsize ); /* integer abs */
}

Das Problem ist, dass die zu hashenden Strings auf eine Länge von 80 Chars beschränkt sind, da das Array mmult[] nur 80 Elemente hat. Es ist aber notwendig, dass ich auch längere Strings hashen kann. Dazu müsste ich die Funktion so abändern, dass mmult[] mehr Elemente enthält (z.B. 100), leider habe ich keine so rechte Idee, was für Werte ich da eintragen müsste. Welches System hinter den 80 bereits vorhanden Einträgen steckt, verstehe ich nämlich auch nicht. Kann mir da jemand weiterhelfen? Sind das vielleicht aufeinanderfolgende Primzahlen?

[ScottManDeath]

Du koenntest auch Hashs fuer jede Gruppe von 80 Chars berechnen und die dann alle XOR nehmen.

[Marscel]

Sind das vielleicht aufeinanderfolgende Primzahlen?

Ja, richtig erkannt.

[Gast]

@ScottManDeath: Danke, das werde ich mal ausprobieren :)

@Marscel: ok, es sind Primzahlen, aber keine direkt aufeinander folgenden. Zwischen z.B. 262139 und 259459 gibt es noch jede Menge andere Primzahlen, es ist daher nicht so ohne weiteres ersichtlich, wie mmult[] fortzusetzen wäre.

[Trap]

Laut Google kommt die Hashfunktion aus https://projects.coin-or.org/svn/CoinUtils/trunk/CoinUtils/src/CoinModelUseful.cpp

Du könntest eine andere nehmen. Google hat benutzt unter anderem http://code.google.com/p/smhasher/ (wobei die für größere Daten optimiert ist, bei Strings bis 80 Zeichen ist die Funktion oben vielleicht besser).

[AlecWhite]

Bei der Hash funktion geht es doch im wesentlich nur um die Primzahlen (und deren Multiplikation) und die Modulo divison - sehr stark an die RSA angelehnt - daher würde ich sagen, ohne es weiter zu testen, das mmult prinzipiell nur aus zufälligen Primzahlen bestehen muss.

Das macht prinzipiell auch Sinn, da durch die Primzahlen Multiplikation und die Modulo Division die Unumkehrbarkeit der Funktion gewährleistet ist.

[Coda]

Einfachste Lösung:

n += mmult[j % 80] * iName;

Ist halt nicht unbedingt performant. Kommt aber drauf an wie schlau der Compiler ist ;)


sehr stark an die RSA angelehnt - daher würde ich sagen, ohne es weiter zu testen, das mmult prinzipiell nur aus zufälligen Primzahlen bestehen muss.

Das macht prinzipiell auch Sinn, da durch die Primzahlen Multiplikation und die Modulo Division die Unumkehrbarkeit der Funktion gewährleistet ist.
Das ist kein kryptografisch sicherer Hash und mit RSA hat das auch nichts zu tun. Nichtmal ansatzweise.

[Gast]

Falls die obige Funktion verwendet werden soll/muss,
stellt die Merkle-Damgard-Konstruktion eine Möglichkeit dar,
um die Eingabelänge zu vergrößern -- sicherlich nicht die schnellste/beste Möglichkeit für das reine Hashen von Strings, aber zumindest keine Pi-mal-Daumen-Lösung.

Siehe Wikipedia:
http://de.wikipedia.org/wiki/Merkles_Meta-Verfahren

[pest]

das mit den 80 hat schon seinen Grund :rolleyes:

ich habe mal angenommen das die Primzahlen irgendwie gleichverteilt in ihrem Intervall sind, also 164121 der Mittelwert ist

genauso wie ich angenommen habe das 128 der mittlere Wert der Eingaben ist

dann gibt es ab ca. 100 Zeichen einen Überlauf in 32-Bit signed integer.