Was ist der Standard-Hashcode, den Mathematica verwendet?

Ich habe ein Reverse Engineering für die 32- und 64-Bit-Windows-Version von Mathematica 10.4 gemacht und das habe ich gefunden:

32 BIT

Es verwendet eine Fowler-Noll-Vo-Hash-Funktion (FNV-1, mit Multiplikation vorher) mit 16777619 als FNV-Primzahl und 84696351 als Offset-Basis. Diese Funktion wird auf Murmur3-32 Hash-Wert der Adresse der Daten des Ausdrucks angewendet (MMA verwendet einen Zeiger, um einen zu behalten) Instanz jeder Daten). Die Adresse wird schließlich auf den Wert aufgelöst - für einfache Maschinen-Ganzzahlen ist der Wert unmittelbar, für andere ist es etwas komplizierter. Die implementierende Funktion Murmur3-32 enthält in der Tat einen zusätzlichen Parameter (standardmäßig 4, Sonderfall, der sich wie in Wikipedia verhält), der auswählt, wie viele Bits aus dem Ausdruck struct in input ausgewählt werden sollen. Da ein normaler Ausdruck intern als ein Array von Zeigern dargestellt wird, kann man den ersten, den zweiten usw. nehmen, indem man wiederholt 4 (Bytes = 32 Bit) zum Basiszeiger des Ausdrucks hinzufügt. Wenn Sie also 8 an die Funktion übergeben, erhalten Sie den zweiten Zeiger, 12 den dritten und so weiter. Da interne Strukturen (große ganze Zahlen, Maschinen-Ganzzahlen, Maschinen-Realzahlen, große Realzahlen usw.) unterschiedliche Elementvariablen haben (zB eine Maschinen-Ganzzahl hat nur einen Zeiger auf int, einen komplexen 2 Zeiger auf Zahlen usw.), für jede Ausdrucks-Struktur Es gibt einen "Wrapper", der seine internen Mitglieder in einem einzigen 32-Bit-Hash kombiniert (im Grunde genommen mit FNV-1-Runden). Der einfachste Ausdruck für Hash ist eine Ganzzahl.

Die Funktion murmur3_32() hat 1131470165 als Seed, n = 0 und andere Parameter wie in Wikipedia.

Wir haben also:

mit "^" bedeutet XOR. Ich habe es wirklich nicht versucht - Zeiger werden mit WINAPI EncodePointer() kodiert, so dass sie zur Laufzeit nicht ausgenutzt werden können. (Kann es sich lohnen, unter Linux mit einer modifizierten Version von EncodePonter in Wine zu laufen?)

64 BIT

Sie verwendet eine FNV-1-64-Bit-Hash-Funktion mit 0xAF63BD4C8601B7DF als Offset-Basis und 0x100000001B3 als FNV-Primzahl, zusammen mit einem SIP64-24 Hash ( hier ist der Referenzcode) mit die ersten 64 Bit von 0x0AE3F68FE7126BBF76F98EF7F39DE1521 als k0 und die letzten 64 Bit als k1. Die Funktion wird auf den Basiszeiger des Ausdrucks angewendet und intern aufgelöst. Wie im 32-Bit-Rauschen murmur3 gibt es einen zusätzlichen Parameter (standardmäßig auf 8 gesetzt), um auszuwählen, wie viele Zeiger aus der Eingabe-Ausdrucksstruktur auszuwählen sind. Für jeden Ausdruckstyp gibt es einen Wrapper zum Zusammenfassen von Strukturelementen in einen einzelnen Hash mittels FNV-1 64-Bit-Runden.

Für eine Maschinen-Ganzzahl haben wir:

Auch ich habe es nicht wirklich versucht. Könnte jemand versuchen?

Nicht für schwache Nerven

Wenn Sie sich ihre Hinweise zur internen Implementierung ansehen, sagen sie, dass "Jeder Ausdruck enthält eine spezielle Form von Hash-Code, der sowohl bei der Mustererkennung als auch bei der Mustererkennung verwendet wird. "

Der Hash-Code, auf den sie sich beziehen, ist derjenige, der von diesen Funktionen generiert wird - an einer Stelle in der normalen Ausdruckswrapper-Funktion gibt es eine Zuweisung, die den berechneten Hash in die Ausdrucksstruktur selbst einfügt.

Es wäre sicherlich cool zu verstehen, wie sie diese Hashes für Pattern Matching-Zwecke nutzen können. Also habe ich versucht, durch den BigInteger-Wrapper zu laufen, um zu sehen, was passiert - das ist der einfachste zusammengesetzte Ausdruck. Es fängt an, etwas zu überprüfen, das 1 zurückgibt - weiß was nicht. So wird es ausgeführt

mit hashMachineInteger () ist das, was wir vorher gesagt haben - inklusive Werte.

Dann liest es die Länge in Bytes der bigInt von der Struktur ( bignum_length ) und läuft

Beachten Sie, dass murmur3_32() aufgerufen wird, wenn 4 * bignum_length größer als 8 ist (kann sich auf den Maximalwert von Maschinen-Ganzzahlen $MaxMachineNumber 2^32^32 beziehen und umgekehrt, was ein bigInt sein soll).

Also, der endgültige Code ist

Ich habe einige Hypothesen über die Eigenschaften dieser Konstruktion gemacht. Das Vorhandensein vieler XORs und die Tatsache, dass 16777619 + 67918732 = 84696351‬ dazu führen kann, dass man denkt, dass irgendeine Art von zyklischer Struktur ausgenutzt wird, um Muster zu prüfen - d. H. Den Offset subtrahieren und durch die Primzahl dividieren oder so ähnlich. Die Software Cassandra verwendet den Murmur-Hash-Algorithmus zur Token-Generierung - siehe diese Bilder für was ich meine mit" zyklische Struktur ". Vielleicht werden für jeden Ausdruck verschiedene Primzahlen verwendet - muss noch überprüft werden.

Ich hoffe, es hilft

Es scheint, dass Hash die interne Data'HashCode-Funktion aufruft, sie dann durch 2 teilt, die ersten 20 Ziffern von N [..] und dann das IntegerPart plus eins nimmt, das heißt: