Frage an hash, c++ – String-to-Integer-Hashing-Funktion mit Präzision

4

Ich möchte ein char-Array in ein int oder ein long-Array hacken. Der resultierende Wert muss einem bestimmten Genauigkeitswert entsprechen. Die von mir verwendete Funktion ist unten angegeben:

<code>int GetHash(const char* zKey, int iPrecision /*= 6*/)
{
        /////FROM : http://courses.cs.vt.edu/~cs2604/spring02/Projects/4/elfhash.cpp

        unsigned long h = 0;
        long M = pow(10, iPrecision);

        while(*zKey)
        {
                h = (h << 4) + *zKey++;
                unsigned long g = h & 0xF0000000L;
                if (g) h ^= g >> 24;
                h &= ~g;
        }            

        return (int) (h % M);
}
</code>

Die zu hashende Zeichenfolge ähnelt "SAEUI1210.00000010_1".

Dies führt jedoch in einigen Fällen zu doppelten Werten. Gibt es gute Alternativen, die nicht den gleichen Hash für verschiedene Zeichenfolgenwerte duplizieren würden?

Versuchen Sie es mit CRC 32:en.wikipedia.org/wiki/Crc32 Akira Yamamoto

Deine Antwort

4   die antwort
1

MD5 oderSHA. Es gibt viele offene Implementierungen, und es ist sehr unwahrscheinlich, dass das Ergebnis zu einem doppelten Ergebnis führt.

Ja. Zu meiner Anforderung gehört aber auch, dass das Ergebnis eine ganze Zahl sein muss. MD5-Hashes enthalten sowohl Ints als auch Zeichen. Ich denke, es ist das gleiche für SHA-Algorithmen Gayan
Stimmt, aber die Konvertierung ist trivial - von 128 Bit auf 32 Bit Integer. Sie erhalten einen 2-zeiligen Code (Hash, Int-Konvertierung), der de facto keinen Kollisions-Hash erzeugt. Adam Matan
2

Jeder Hash wird Kollisionen haben. Zeitraum. Das nennt man einGeburtstagsproblem.

Möglicherweise möchten Sie überprüfen, ob kryptografische Funktionen wie MD5 vorhanden sind (relativ schnell und es ist Ihnen egal, ob sie unsicher sind), es treten jedoch auch Kollisionen auf.

Perfekte Hashes per Definition nicht. MSalters
2

Hashes erzeugen für verschiedene Eingaben den gleichen Wert - das ist, was sie tun. Sie können lediglich eine Hash-Funktion mit ausreichender Verteilung oder Bittiefe (oder beidem) erstellen, um diese Kollisionen zu minimieren. Da Sie diese zusätzliche Genauigkeitsbeschränkung (0-5?) Haben, werden Sie viel häufiger auf Kollisionen stoßen.

13

Die eigentliche Definition eines Hashs ist, dass er für einige Werte doppelte Werte erzeugt, da der Hash-Wertebereich kleiner ist als der Speicherplatz der Hash-Daten.

Theoretisch hat ein 32-Bit-Hash genügend Reichweite, um alle ~ 6 Zeichenketten zu hashen (nur A-Z, a-z, 0-9), ohne eine Kollision zu verursachen. In der Praxis sind Hashes keine perfekte Permutation der Eingabe. Bei einem 32-Bit-Hash können Sie aufgrund von mit Hash-Kollisionen rechnen, nachdem Sie ~ 16 Bit zufälliger Eingaben gehasht habenGeburtstagsparadoxon.

Bei einem statischen Satz von Datenwerten ist es immer möglich, eine speziell für sie entwickelte Hash-Funktion zu erstellen, die niemals mit sich selbst kollidiert (natürlich ist die Größe der Ausgabe mindestens gleich groß)log(|data set|). Sie müssen jedoch alle möglichen Datenwerte im Voraus kennen. Das nennt manperfektes Hashing.

Davon abgesehenHier Es gibt ein paar Alternativen, die Ihnen den Einstieg erleichtern sollten (sie wurden entwickelt, um Kollisionen zu minimieren).

Die einzige Möglichkeit zu testen, welche Hash-Funktion für Ihre Zwecke "am besten" ist, besteht darin, einen Benchmark für die Datenprobe durchzuführen, der Ihren erwarteten realen Daten entspricht. Die von Ihnen verwendete Funktion versucht nicht, die Eingabebits zu stark zu mischen, um einen Hash zu erstellen. In jedem Schritt werden höchstens 4 oberste Bits eingemischt. und in Strings mit einer Länge von <8 akkumuliert Ihr Hash einfach alle Zeichen mit einer leichten Überlappung. ASk
Welches ist die beste Hashing-Funktion, die Sie aus den in dem von Ihnen bereitgestellten Link angegebenen Funktionen und der Funktion, die ich gerade verwende, verwenden können. Die von mir verwendete Funktion scheint komplexer zu sein als djb2 und sdbm. Bedeutet das, dass es besser ist, Kollisionen zu vermeiden? Gayan

Verwandte Fragen