P
waldiwaldi schrieb:
hi,
ich weiss die hash funktion ist nicht gerade geeignet hier...aber was mache ich wenn die hash funktion einen hash liefert und dieser schon in der tabelle vorhanden ist? wie finde ich das richtig element wieder?
Alles schreiben nur noch über den const_cast schmarrn, zurück zu dir:
Also es ist ganz normal, dass es zu einer sog. Kollision kommt. Du möchtest N Elemente auf M abbilden. Für N <= M ist das theoretisch möglich, doch nur wenn es eine Hashfunktion gibt, die das in konstanter Laufzeit schafft, also unabhängig von N ist. Es fängt schonmal so an, dass die Elemente vielleicht gar nicht durchnummeriert sind und keine direkt (ideale) Abbildung ohne Kollision möglich ist. Deshalb wählt man ein M relativ größer als N (wobei die Größe davon abhängig ist, wie wahrscheinlich man sich eine nicht konstante Laufzeit doch erlauben kann). Also wenn du so willst ist Hashing zu einem Prozentsatz konstant und zu einem Prozentsatz Laufzeit linear (Überlaufstrategie). Im Grunde genommen instabil.
Deshalb ist die richtige Wahl einer guten Hashfunktion so wichtig. Und nun zurück zu deiner Frage: Bei einer Kollision kommt die Überlaufstrategie zum Einsatz. Es gibt verschiedene Strategien, aber für gute Hashfunktion und großen M kann man sich eine lineare Suche erlauben. Z.B. fügt man ein Element bei einer Kollision in den nächste freie Feld. Es gibt verschiedene Hasingmethoden, du musst hier abwägen, was du brauchst! Offenes Hashing, geschlossenes Hashing, distributed Hashing, uvm. einfach googlen!
Dadurch, dass die Hashfunktion auch ein anderes Element auf den gleichen HAshwert abbilden kann, musst du immer nochmal den direkten Test machen ob es wirklich das Element ist, denn Hashing hilft die genau genommen nur über einen Zugriffspfad, aber sagt dir nie 100% ob es wirklich das ELement ist!
