Double Hashing
-
Hallo.
Ich habe Probleme beim Double Hashing und zwar beim Löschen bzw. Suchen.
Das Einfügen funktioniert einwandfrei, je nachdem, ob ein Platz schon besetzt ist, sucht er mit der zweiten Funktion weiter bis frei oder Tabelle zu 90 Prozent voll.Doch wie funktioniert das mit dem Löschen, ich komme einfach nicht drauf.
Jetzt habe ich gerade gelesen, dass man die Daten, die man löschen möchte, nur als wiederfrei markiert, sie jedoch nicht wirklich löscht, stimmt das. ?
Wäre nett, könnte mir jemand helfen und mich aufklären .
Liebe Grüße Reinhard
-
ja, das stimmt.
und zwar so als wiederfrei, daß so ein gelöschter platz die suchschleife beim einfügen abbricht (klar, ein freier platz ist ja da), aber die suchschleife beim suchen nicht abbricht (die wird est duch nen jungfräulichen platz abgebrochen).die hashtable mutiert natürlich mit der zeit. ich würde drauf achten, daß immer 10% jungfräuliche plätze da sind und bei überfüllung die ganze ht kopieren. und evtl doch eher an ne ht mit verkettung der elemente denken. scheint mir schneller zu sein bei gleichem speicherplatzverbrauch.
-
"ja, das stimmt.
und zwar so als wiederfrei, daß so ein gelöschter platz die suchschleife beim einfügen abbricht (klar, ein freier platz ist ja da), aber die suchschleife beim suchen nicht abbricht (die wird est duch nen jungfräulichen platz abgebrochen)."Meinst du damit, wenn ich jetzt ein Element einfügen möchte, dass ich, wenn es entweder besetzt oder als wiederfrei markiert wurde, weitersuchen muss, bis ich einen tatsächlich freien Platz gefunden habe , oder? Müsste so sein, da ja das Element, das ich gelöscht habe, hier auf diesem Platz noch existiert?
Finde dies allerdings komisch, dass dies ELlement nicht wirklich gelöscht wird.
Ne verkettete Liste wäre besser, stimmt, hilft mir aber leider nicht .danke für den Tipp, werd mich gleich an die Arbeit machen
-
Original erstellt von Reinhard:
**Meinst du damit, wenn ich jetzt ein Element einfügen möchte, dass ich, wenn es entweder besetzt oder als wiederfrei markiert wurde, weitersuchen muss, bis ich einen tatsächlich freien Platz gefunden habe , oder? Müsste so sein, da ja das Element, das ich gelöscht habe, hier auf diesem Platz noch existiert?
Finde dies allerdings komisch, dass dies ELlement nicht wirklich gelöscht wird.
**Das fände ich auch komisch.
Bein Eifügen kannste den ersten nicht belegten Platz nehmen. Der muß nicht jungfräulich sein. EInfach rein damit.Beim Suchen eines konkreten Wertes aber kannste nicht beim ersten nicht belegten Platz schon aufhören. Denn beim Einfügen könnte er damals 5 Schleifenduchläufe gebraucht haben und nu ist auf dem 2. Plat ein gelöschter! Mußt bei gelöschten trotzdem weiterlaufen, damit du den 5. Platz findest. Bei nem jungfräulichen Platz kannste mit der Suchschleife aufhören.
-
@volkard: spielst du Ultima Online?
-
Original erstellt von <volkard-Fan>:
@volkard: spielst du Ultima Online?offensichtlich.
-
o.B.d.A.?
hätt ich nicht gedacht. Spielst du auch andere Spiele (z.B.?)?
-
Stimmt eigentlich ja.
Okay, zuerst meine Methode füs Einfügen:
int Hashtable::einfuegen(unsigned long wertP) //Zeiger übergeben ich weiß...{ int key,i; i=key=0; if (anzahl == 7) //Tabelle voll ? return 0; do { key =(wertP + i*(wertP %5+1)) %7; //Hashfunktion i++; } while ((besetzt[key])||(wiederfrei[key])); entry[key] = new Element(wertP); anzahl++; besetzt[key] =1; return 1; Nun löschen, ohne das Element zu löschen *g int Hashtable::loesche(unsigned long wertP) { int key,i; i=key=0; Element help(wertP); do { key=(wertP + i *(wertP % 5+1)) %7; if ( !entry[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; } und suchen : int Hashtable::suchen (unsigned long wertP) { int key,i; i=key=0; Element help(wertP); do { key =(wertP + i *(wertP % 5+1)) %7; if ( !entry[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; }
Wäre nett, könnte mir jemand sagen, ob es so gemeint ist.
[ Dieser Beitrag wurde am 24.04.2003 um 13:39 Uhr von Dimah editiert. ]
-
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.