Double Hashing
-
meinste mit !entry[key] eher !besetzt[key]?
-
Ja sollte es, hab mich vertippt.
Ich habs nun so gelöst, dass, wenn er beim EInfügen auf einen "Wiederfrei" index, kommt, der Suchpfad aufhört,das dortige Element gelöscht und der neue Datensatz eingefügt wird, somit wird der Kollisionspfad nicht unterbrochen. FUnktioniert.int Hashtable::einfuegen(unsigned long *wertP) { int key,i; i=key=0; if (anzahl == 7) return 0; do { key =(*wertP + i*(*wertP %5+1)) %7; i++; if (wiederfrei[key]) { //wurde schon freigegeben? delete entry[key]; entry[key]=new Element(wertP); anzahl++; return 1; } } while (besetzt[key]) ; entry[key] = new Element(wertP); anzahl++; besetzt[key] =1; return 1; } int Hashtable::suchen (unsigned long *wertP) { int key,i; i=key=0; Element help(wertP); do { key =(*wertP + i *(*wertP % 5+1)) %7; if ( !besetzt[key] && !wiederfrei[key]) { cout << endl << " Das Element ist nicht vorhanden" << endl; return 0;} i=i+1; } while ( !(help==*entry[key])); cout << endl << "Das Element befindet sich an der Position " << key << endl; return 1; } int Hashtable::loesche(unsigned long *wertP) { int key,i; i=key=0; Element help(wertP); do { key=(*wertP + i *(*wertP % 5+1)) %7; if ( !besetzt[key] && !wiederfrei[key]) { cout << endl <<"Das Element befindet sich nicht in der Tabelle" << endl; return 0;} i++; }while (!(help==*entry[key])); wiederfrei[key]=1; anzahl--; cout <<"Erfolgreich geloescht!" <<endl; return 0; }[ Dieser Beitrag wurde am 24.04.2003 um 17:46 Uhr von volkard editiert. ]
-
Code Tags sind was feines
EDIT: Ups, da war Volkard schneller
[ Dieser Beitrag wurde am 24.04.2003 um 17:49 Uhr von MaSTaH editiert. ]
-
also einfuegen erscheint mir richtig.
bei suchen sollen welche mit wiederfrei[key] einfach übersprungen werden. wiederfrei[key] sagt, daß weitergesucht werden soll und nicht, daß das element nicht da ist.
und bei loesche wird ja gesucht wie beim suchen.
-
Er hört beim suchen und löschen eh nur auf, wenn nicht besetzt und nicht wiederfrei, ansonsten sucht er weiter, bis das element gefunden ! Nicht wiederfrei und nicht besetzt sagt ja, dass das zu suchende bzw. löschende Element nicht vorhanden sein kann.
-
Hallo. Könnte mir bitte jemand, der sich gut auskennt, seine Meinung schreiben, ob es richtig ist? Habe eigentlich nur noch eine kleine Lücke, und zwar , dass er beim Suchen auch ein Element, dass soeben gelöscht wurde, auch findet, das sollte wahrscheinlich nicht sein, ist aber klar, da das Element ja als nur wiederfrei markiert ist.
int Hashtable::einfuegen(unsigned long *wertP) { int key,i; i=key=0; if (anzahl == 7) return 0; do { key =(*wertP + i*(*wertP %5+1)) %7; i++; if (wiederfrei[key]) { delete entry[key]; entry[key]=new Element(wertP); besetzt[key]=1; anzahl++; return 1; } } while (besetzt[key]) ; entry[key] = new Element(wertP); anzahl++; besetzt[key] =1; return 1; } int Hashtable::suchen (unsigned long *wertP) { int key,i; i=key=0; Element help(wertP); do { key =(*wertP + i *(*wertP % 5+1)) %7; if ( !besetzt[key] &&!wiederfrei[key]) { cout << endl << " Das Element ist nicht vorhanden" << endl; return 0;} i=i+1; } while ( !(help==*entry[key])); cout << endl << "Das Element befindet sich an der Position " << key << endl; return 1; } int Hashtable::loesche(unsigned long *wertP) { int key,i; i=key=0; Element help(wertP); do { key=(*wertP + i *(*wertP % 5+1)) %7; if ( !besetzt[key] && !wiederfrei[key]) { cout << endl <<"Das Element befindet sich nicht in der Tabelle" << endl; return 0;} i++; }while (!(help==*entry[key])); wiederfrei[key]=1; besetzt[key]=0; anzahl--; cout <<"Erfolgreich geloescht!" <<endl; return 0; }
-
Original erstellt von Reinhard:
Er hört beim suchen und löschen eh nur auf, wenn nicht besetzt und nicht wiederfrei, ansonsten sucht er weiter, bis das element gefunden ! Nicht wiederfrei und nicht besetzt sagt ja, dass das zu suchende bzw. löschende Element nicht vorhanden sein kann.er hört beim suchen auf, sobald besetzt oder wiederfrei. er überspringt da kein wiederfrei.
-
//achte aufs continue! int Hashtable::suchen(unsigned long *wertP) { int key=0; int i=0; Element help=wertP; do { key =(*wertP + i *(*wertP % 5+1)) %7; if(wiederfrei[key]) continue; if (!besetzt[key]) { cout << endl << " Das Element ist nicht vorhanden" << endl; return 0; } i=i+1; }while ( !(help==*entry[key])); cout << endl << "Das Element befindet sich an der Position " << key << endl; return 1; }[/QB][/QUOTE]
-
Okay ich weiß, was du meinst.
Meine Frage: Angenommen, ich lösche in meiner Tabelle den Wert sechs, welcher am index 6 abgelegt ist. (wiederfrei[key]=1;besetzt[key]=0;Nun suche ich diesen Wert, den er ja eigentlich nicht mehr finden sollte, oder ? Und er findet ihn!
Ist das beim Hashen normal, dass er diesen Wert wieder findet?Reinhard
-
sollte nur passieren, wenn die 6 doppelt drin wäre. aber an der gleichen stelle sollte es nie passieren!
ich meine aber auch dass man vor dem continue noch i inkremetieren sollte, da es sonst doch ne endlosschleife werden müsste. also am einfachsten das inkrementieren gleich nach der berechnung von key packen.