String zu Integer Hashing-Funktion mit Präzision

Ich möchte ein char-Array in ein int oder eine lange hash. Der resultierende Wert muss einem bestimmten Genauigkeitswert entsprechen. Die Funktion, die ich habe, ist unter Verwendung von unten angegeben:String zu Integer Hashing-Funktion mit Präzision

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); 
}

Der String gehasht werden soll, ähnlich wie „SAEUI1210.00000010_1“.

Dies führt jedoch in einigen Fällen zu doppelten Werten. Gibt es irgendwelche guten Alternativen, die den gleichen Hash für unterschiedliche String-Werte nicht duplizieren würden.

Quelle

2009-06-18 Gayan

Versuchen Sie es mit CRC 32: http://en.wikipedia.org/wiki/Crc32 –

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

Theoretisch verfügt ein 32-Bit-Hash über genügend Bereich, um alle ~ 6 Zeichenfolgen (A-Z, a-z, nur 0-9) zu haseln, ohne eine Kollision zu verursachen. In der Praxis sind Hashes keine perfekte Permutation der Eingabe. Bei einem 32-Bit-Hash können Hash-Kollisionen nach dem Hashing von ~ 16 Bit zufälliger Eingaben aufgrund der birthday paradox erwartet werden.

Angesichts einer statischen Reihe von Datenwerten, ist es immer möglich, eine speziell für sie entworfene Hash-Funktion zu konstruieren, die nie mit sich selbst kollidieren wird (natürlich wird die Größe der Ausgabe mindestens log(|data set|) sein. Allerdings erfordert es Sie alle möglichen Datenwerte im voraus wissen. Diese perfect hashing genannt wird.

aber sagen, dass here ein paar Alternativen, die Ihnen den Einstieg sollten

Quelle

2009-06-18 05:20:27 ASk

Welches ist die beste Hashing-Funktion, um die von Ihnen angegebenen und die, die ich gerade benutze, zu verwenden? Die Funktion, die ich verwende, scheint komplexer zu sein als djb2 und sdbm. Sind Kollisionen besser zu vermeiden? – Gayan

Die einzige Möglichkeit zu testen, welche Hash-Funktion für Ihre Zwecke "am besten" ist, besteht darin, einen Benchmark für ein Datensample durchzuführen, der Ihren erwarteten realen Daten entspricht. Die von Ihnen verwendete Funktion versucht nicht, die Eingangsbits zu stark zu mischen, um einen Hash zu erzeugen - bei jedem Schritt werden höchstens 4 oberste Bits gemischt; und in Strings der Länge <8, auch wenn das nicht passiert, akkumuliert Ihr Hash einfach alle Zeichen mit einer leichten Überlappung. – ASk

Jeder Hash wird Kollisionen haben. Zeitraum. Das nennt man Birthday Problem.

Sie können überprüfen, ob kryptografische Funktionen wie MD5 (relativ schnell und Sie kümmern sich nicht, dass es unsicher ist), aber es wird auch Kollisionen haben.

Quelle

2009-06-18 05:20:02 sharptooth

Perfekte Hashes per Definition nicht. – MSalters

Hashes die gleiche erzeugen (sie Kollisionen zu minimieren sind so konzipiert) Wert für verschiedene Eingaben - das ist was sie tun.Alles, was Sie tun können, ist eine Hash-Funktion mit ausreichender Verteilung zu erstellen oder Bittiefe (oder beides), um diese Kollisionen zu minimieren. Da Sie diese zusätzliche Einschränkung der Genauigkeit (0-5?) Haben, werden Sie Kollisionen viel öfter treffen.

Quelle

2009-06-18 05:20:33 Talljoe

MD5 oder SHA. Es gibt viele offene Implementierungen, und das Ergebnis ist sehr unwahrscheinlich, ein doppeltes Ergebnis zu erzeugen.

Quelle

2009-06-18 05:29:10

Ja. Aber meine Anforderung beinhaltet 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

True, aber die Konvertierung ist trivial - von 128 Bit bis 32 Bit Integer. Sie erhalten einen zweizeiligen Code (Hash, int-Konvertierung), der einen De-Facto-No-Collision-Hash erzeugt. –

String zu Integer Hashing-Funktion mit Präzision

Antwort

Verwandte Themen