Kann man Hash-Kombinationen erkennen und ausnutzen?

[Schrompf]

Hi!

Mir kam gerade die vage Ahnung einer Idee, die ich gerne mal mit euch teilen will.

Ich habe Dreiecke. Dreiecke haben drei Positionen. Ich kann zu einer Position XYZ einen Hash bilden, indem ich (zum Beispiel) jeden Wert in den Bereich +-32'767.0f transformiere und den Integer davon mit irgendner Primzahl multipliziere, um die Information über die kompletten z.B. 32Bit Hashwert breitzuschmieren. Dann XOR der drei, oder auch noch bissl Rot und Mult, und ich habe einen halbwegs tauglichen Hash für eine 3D-Position.

Wenn ich jetzt plump die Hashes der beiden Endpunkte XORe, hab ich den Hash einer Kante. Ok, die hau ich jetzt in ne std::unordered_map und hab mit drei Lookups alle Nachbarn eines Dreiecks. Ich hab jetzt keine Idee, wie eine unordered_map Map implementiert ist, aber wenn ich Zeit und Lust hab, schlug xq vor, könne ich ja eine auf Basis von Cuckoo Filters implementieren. Hm. Schaumermal.

Die eigentliche Frage ist jetzt aber: ich kann jetzt auch einen Hash von einem Dreieck bilden, indem ich die Hashes der drei Eckpunkte verXORe. Benachbarte Dreiecke haben jetzt zwei von drei Hashes in dieser Kombi identisch. Kann ich das irgendwie ausnutzen? Gibt es irgendnen coolen Trick, wie ich ausgehend von einem Hash erkenne, welche Hashes daraus gebildet wurden? Könnte ich meine Einzel-Hashes eines Eckpunkts irgendwie poisonen, so dass ich von nem 2-Hash ausgehend erkenne, ob ein anderes Element mit diesem 2-Hash und einen zusätzlichen dritten Element gebildet wurde?

Je länger ich darüber nachdenke, desto mehr stelle ich fest, dass mir die reine Erkennung, ob zwei Hashes einen ähnlichen Stamm haben, gar nix bringt. Ich müsste ja trotzdem jeden mit jedem Eintrag vergleichen. Wahrscheinlich komme ich wirklich besser, wenn ich einfach jede Kante in ne HashMap schmeiße und pro Nachbar halt drei Lookups mache.

[Jonathan]

Was ist denn die Anwendung davon? Ich verstehe nicht ganz, worauf du hinaus willst.

Wenn du Nachbarn finden willst, gibts ja z.b. die Winged-Edge Datenstruktur, wo schon allerhand Zusatzinfos für direkten Zugriff gespeichert sind. Die sollte sich halbwegs effizient generieren lassen und dann kannst du all deine TriangleMesh Operationen ziemlich leicht und effizient damit implementieren.

Wenn du wirklich Hashs benutzen willst, dann klingt das eher ein bisschen nach Kodierungstheorie: Der Mesh ist nicht nur eine Zufallszahl (also z.B. kein Krzptografischer Hash) sondern kodiert ganz gezielt bestimmte Eigenschaften. Und dann wird es ja ganz schnell auch um Effizienz gehen, du brauchst ja einerseits genügend Bits im Hash um Kollisionen zu vermeiden, andererseits darfst du nicht zu viele Bits haben, ansonsten könntest du ja ganz einfach Meta-Daten wie die Indizes von Vertexen oder so speichern und dann direkt benutzen. Ganz einfach nachgedacht, mit 16bit für einen Index kannst du 65k Punkte adressieren, ein 32bit Wert der eine Kante darstellt, kann also nicht für Modelle mit mehr als 65k Vertexen funktionieren, zumindest nicht wenn man Kanten zwischen beliebigen Punkten ermöglichen will. Und wenn du den Hash wie oben skizziert berechnest wirst du vermutlich wesentlich früher Kollisionen bekommen - und dann isses nicht mehr robust.

[Schrompf]

Hashes und Hash-Konflikte sind mir bekannt. Das nehme ich schon in Kauf. Mir geht's eher um die mathematischen Eigenschaften von kombinierten Hashes. Wenn ich zum Beispiel XOR als Operation nehme, kann ich die drei Hashes dreier Punkte auch wieder ent-kombinieren und die Reihenfolge der Hashes ist egal. Die Frage war also eher, ob jemand was kennt, ob man diese Kombination irgendwie ausnutzen könnte.

[Jonathan]

Hm, aber ist das nicht einfach nur Assoziativgesetz? Du kannst ja auch das Produkt oder die Summe von 3 Zahlen wieder auseinander nehmen, wenn du eine oder zwei dieser Zahlen kennst. Das erscheint mir erstmal nicht sonderlich spektakulär. Interessanter wäre die Zerlegung, wenn man keine der ursprünglichen Zahlen kennt. Etwa das Produkt von Primzahlen, aber vermutlich würde man dann wirklich einfach etwas triviales nehmen, etwa 2 16 Bitzahlen hintereinander in einer 32 Bit Zahl speichern. Nichts davon erscheint mir erstmal irgendwie sehr Hash-spezifisch.