Aus einer Referenz ein Zahlencode generieren.
-
Bashar schrieb:
Du wirst es dem Benutzer überlassen müssen, eine Hashfunktion für seinen Key-Typ bereitzustellen.
Daran habe ich auch zuerst gedacht, jedoch dachte ich mir es gibt halt eine bestimmte möglichkeit aus referencen einen Int Wert zugenerieren.
Lassen wir mal die Hashtable aus dem Spiel.
Gibt es echt keinerlei "Zahlencode" den man aus Refernzen erzeugen kann? Ich habe es schon mit den Adressen versucht, jedoch hat es nicht so geklappt, wie ich das haben wollte.
-
Nein, nein. Du wendest einfach
std::hashdarauf an.
-
Daran habe ich auch zuerst gedacht, jedoch dachte ich mir es gibt halt eine bestimmte möglichkeit aus referencen einen Int Wert zugenerieren.
Man holt sich die Adresse und hat seine Zahl.
-
knivil schrieb:
Daran habe ich auch zuerst gedacht, jedoch dachte ich mir es gibt halt eine bestimmte möglichkeit aus referencen einen Int Wert zugenerieren.
Man holt sich die Adresse und hat seine Zahl.
Was fuer hashes aber eine furchtbar schlechte idee ist.
Der User muss eine hash Funktion implementieren. Entweder per std::hash oder als functor im Template.
PS:
generische Hashfunktionen sind soweit schrott. Lohnt sich also garnicht erst eine zu erfinden.
-
Shade Of Mine schrieb:
Man holt sich die Adresse und hat seine Zahl.
Was fuer hashes aber eine furchtbar schlechte idee ist.
Hatten wir in der Firma. Alle Adressen waren vom Heap und durch 8 teilbar, initial gab es 8 Buckets, die Hashfunktion war einfach modulo 8, vom Feinsten.
-
Was fuer hashes aber eine furchtbar schlechte idee ist
Anwendungsbedingt. Habe das mal fuer Kollisionsereignisse zwischen Objekten genutzt.
-
Alle Adressen waren vom Heap und durch 8 teilbar, initial gab es 8 Buckets, die Hashfunktion war einfach modulo 8, vom Feinsten.
Moment, die Hashfunktion war "Adresse modulo 8"?
-
Alle Adressen waren vom Heap und durch 8 teilbar, initial gab es 8 Buckets, die Hashfunktion war einfach modulo 8, vom Feinsten.
Man nimmt also den pointer, generierst daraus das hash und um wieder an den pointer zu kommen, siehst man später in der hashtable nach, die auch noch furchtbar schnell ist, weil dank Alignment alle Werte den gleichen hash bekommen. Hat deine Firma noch weitere großartige Vorschläge, wie man noch mehr Geschwindigkit herausholen kann?
-
Marthog schrieb:
Man nimmt also den pointer, generierst daraus das hash und um wieder an den pointer zu kommen,
Soweit noch kein Problem, habe ich auch schon gemacht. Musste zu den Objekten noch ein wenig Zusatzinfo speichern, ohne die Objekte zu verändern. Wäre zum Beispiel denkbar für einen Debug-Heap.
Marthog schrieb:
siehst man später in der hashtable nach, die auch noch furchtbar schnell ist, weil dank Alignment alle Werte den gleichen hash bekommen.
Tja, mein *17 von der ersten Seite hätte es schon gelöst, vermutlich hätte sie dann sogar eine ganz besonders gute gleichverteilung auf die Buckets bekommen.
-
volkard schrieb:
Marthog schrieb:
siehst man später in der hashtable nach, die auch noch furchtbar schnell ist, weil dank Alignment alle Werte den gleichen hash bekommen.
Tja, mein *17 von der ersten Seite hätte es schon gelöst,
durchachtteilbar*17 ist aber wieder durch acht teilbar.
Darum ist es zu empfehlen, dass die Anzahl Buckets eine Primzahl ist. Ganz einfach weil so Effekte kaum zu vermeiden sind.
-
iknowmath schrieb:
volkard schrieb:
Marthog schrieb:
siehst man später in der hashtable nach, die auch noch furchtbar schnell ist, weil dank Alignment alle Werte den gleichen hash bekommen.
Tja, mein *17 von der ersten Seite hätte es schon gelöst,
durchachtteilbar*17 ist aber wieder durch acht teilbar.
Stimmt auffallend, ihh, ist das böse.
iknowmath schrieb:
Darum ist es zu empfehlen, dass die Anzahl Buckets eine Primzahl ist. Ganz einfach weil so Effekte kaum zu vermeiden sind.
Ungern eine Division bezahle. Naja, wenn die Größe compilezeitkonstant ist, geht's ja.
