boost::unordered_flat_map default hash-methode

It0101

Hi zusammen

ich reviewe gerade Code eines Kollegen. Er hat das Problem, dass Daten falsch zugeordnet werden.

Er verwendet eine boost::unordered_flat_map, die ich bisher nicht verwendet habe, daher frage ich jetzt lieber hier.

boost::unordered_flat_map<std::string, T>

Garantiert die standardmäßige Hash-Methode dieser Map, dass der Hash, der sich aus einem beliebigen String ergibt wirklich unique ist?

grüße
Tobi

SeppJ

Natürlich sind die nicht garantiert eindeutig. Das ist doch der ganze Witz an Hashes und hash-basierten Containern.

Ansonsten kann ich nicht erraten, was hier wohl schief gehen könnte. Da kann allerlei passieren oder falsch interpretiert werden. Das einzige, was mich anspringt, weil es anders als bei einer "normalen" unordered_map ist, ist dass hier Pointer/Referenzen auf Elemente durch Einfügungen ungültig werden können.

Schlangenmensch

@It0101 Ich habe auch nicht die große Erfahrung mit Boost, aber die Default Hash Funktion ist boost::hash und die sollte mit std::string funktionieren: https://www.boost.org/doc/libs/master/libs/container_hash/doc/html/hash.html

It0101

Der Fehler tritt aber häufiger auf, d.h. vermutlich ist hier die Map nicht tatverdächtig. Da mir diese Konstruktion aber unbekannt ist, wollte ich aber lieber mal nachfragen.

wob

@It0101 sagte in boost::unordered_flat_map default hash-methode:

Garantiert die standardmäßige Hash-Methode dieser Map, dass der Hash, der sich aus einem beliebigen String ergibt wirklich unique ist?

Nein, und das muss auch nicht. Du kannst testweise eine Hash-Funktion übergeben, die eine Konstante returnt, d.h. für alle Elemente denselben Wert. Damit wird die map natürlich langsam, aber abgesehen von der Performance sollte alles weiterhin korrekt funktionieren. So kannst du Hash-Kollisionen getestet provozieren. Wenn der Hash gleich ist, werden die Keys einfach auf Gleichheit getestet.

Dein Kollege schafft es nicht zufällig irgendwie, die Keys nach Einfügen in die Map zu ändern? Ansonsten bleibt nur, den Fehler anderswo zu suchen.

Columbo

Um das mal auf einer taktischeren Ebene klarzustellen:
Ein STL/Boost Container hat mit allergroesster Sicherheit keine Bugs (d.h. prior sollte irgendwo bei 1:10^6) liegen. Solange Du Dich an den 'contract' hältst, sprich, alle preconditions einhältst, dann darfst Du davon ausgehen, dass alle postconditions auch halten.
Wenn der Container also wie unordered_map verwendet wird (insb. ohne Garantie irgendeiner Reihenfolge und ohne doppelte Keys), dann liegt der Fehler woanders.

Er hat das Problem, dass Daten falsch zugeordnet werden.

??? Wie soll man denn da ueberhaupt einen educated guess machen.

Entweder du konkretisierst das Problem, oder es bleibt bei Binsenweisheiten.

Finnegan

@Columbo sagte in boost::unordered_flat_map default hash-methode:

Solange Du Dich an den 'contract' hältst, sprich, alle preconditions einhältst, dann darfst Du davon ausgehen, dass alle postconditions auch halten.

Da würde ich auch erstmal ansetzen. Eine "Flat" Hash Map kann z.B. nicht die selben Garantien einhalten wie die std::unordered_map. Ich denke da z.B. an Referenzen auf Elemente, die bei letzterer auch nach einem Rehash gültig bleiben. Ich sehe nicht wie man das ohne die (nicht sehr effiziente) Indirektion in Implementierungen der std::unordered_map bewerkstelligen kann. Die boost::unordered_flat_map wird das denke ich nicht unterstützen, sonst wär sie nicht mehr "flat".

P.S.:

@SeppJ sagte in boost::unordered_flat_map default hash-methode:

Natürlich sind die nicht garantiert eindeutig. Das ist doch der ganze Witz an Hashes und hash-basierten Containern.

Mit Ausnahme von "Perfect Hashing"-Implementierungen natürlich, aber die haben ein anderes Anwendungsgebiet.

It0101

Ich habe den Fehler gefunden. Er lag ganz woanders. Die Map ist weiterhin als einwandfrei zu betrachten