P9: Löschen

HolgerF
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 263
Registriert: 16. Jan 2007 14:20
Kontaktdaten:

Beitrag von HolgerF »

Laut Gallenbacher "macht man es aber nicht so"
Joah, heh, in allen mir bekannten Implementationen von Hash-Maps für C++ z. B. (die da gerade standardisiert wurden) wird erst gar kein Open Addressing benutzt, sondern verlinkte Listen für die Adressbereiche, womit man das Problem gleich gar nicht hat.

Aber ansonsten kann ich mir das nicht vorstellen. Ich müsste mir ja sonst das Objekt (Key) merken, das da vorher stand bzw. es eben gar nicht löschen, sondern nur markieren. DAS aber ist bedenklich, weil es hieße, dass das Objekt nicht deallokiert wird, was, je nach Funktion des Destruktors, ungewollt sein kann.
(Von den Leichen, wie du sagtest, mal ganz abgesehen, die stören doch die komplette Belegung der Hashmap)

Hyst
Mausschubser
Mausschubser
Beiträge: 70
Registriert: 5. Mai 2007 22:20

Beitrag von Hyst »

ja eben doch...

nehmen wir an:
meine hashtable spendet platz für 5 elemente. 75 % sind also 3.75
ich füge a, b, c ein... (die haben alle drei den selben hashwert.. also kollisionsbehandlung)... Belegung ist 3.. also < 75%

also von mir aus linke ich (oder wie auch immer) a->b->c
jetzt "lösche" ich b habe also eine b* leiche

a->b*->c

belegung ist jetzt EIGENTLICH nur 2...
jetzt lösche ich noch a und c
und habe
a*-> b* -> c*
belegung ist eigentlich 0 (habe aber 3 leichen)

wenn ich jetzt 2 elemente (d und e) einfüge, ist mein Belegungsfaktor 2 (also < 75%) aber meine hashtable ist VOLL, wegen den leichen...
natürlich kann ich die leichen jetzt mitzählen und schon beim element "d" die liste erweitern... neu hashen und die leichen wegschmeissen.
aber dann habe ich mit einem eigentlichen belegungsfaktor von 1 die tabelle erweitert (was gegen die 75% regelung spricht)

ich hoffe du hast verstanden was ich meine...
meine befürchtung ist ja nur, dass das "problem" bei erstellung der tests nicht wirklich bedacht wird.
oder (was noch schlimmer wäre) man berücksichtigt NICHT, dass jemand "richtig" löscht, und somit die hashtable erst später erweitert wird.

wie auch immer: ich hoffe die tests sind da flexibel, da wie shcon oben erwähnt keinerlei einschränkungen gemacht worden sind. und somit sollten beide lösungen zulässig sein

HolgerF
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 263
Registriert: 16. Jan 2007 14:20
Kontaktdaten:

Beitrag von HolgerF »

? Ich hab dir doch gar nicht widersprochen, im Gegenteil, ich argumentiere doch die ganze Zeit dafür, dass man Leichen bei erster Gelegenheit wieder benutzt.

Übrigens ist die Methode so auch z. B. in "Introduction to Algorithms" beschrieben, wo auch gleich noch der intelligente Hinweis steht, dass Open Addressing üblicherweise eben nicht verwendet wird, wenn Elemente gelöscht werden müssen, Chaining wie oben geschrieben ist da einfach zweckmäßiger...

Hyst
Mausschubser
Mausschubser
Beiträge: 70
Registriert: 5. Mai 2007 22:20

Beitrag von Hyst »

oh ... falsch verstanden sorry....

n-finity
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 101
Registriert: 22. Dez 2006 15:38
Kontaktdaten:

Beitrag von n-finity »

Akzeptiert das Testsystem deine og. Variante, Hyst?

yourmaninamsterdam
Nerd
Nerd
Beiträge: 681
Registriert: 26. Okt 2006 14:04
Kontaktdaten:

Beitrag von yourmaninamsterdam »

Wie du das löschen intern regelst, ist egal. Ich markiere Elemente als Gelöscht. Wenn aber ein Element eingefügt wird, bei dem die Hash- oder Kollisionfunktion auf ein Feld mit einer "Leiche" trifft, wird es da reingeschrieben und die Leiche entsprechende entfernt.

So akzeptiert das Testsystem es selbstverständlich auch.
Wenn man aber Leichen stehen lässt, aber die Überschreibung verbietet, dann wird das Programm im Testsystem auch mit aller Sicherheit scheitern.

Benutzeravatar
vwm
Mausschubser
Mausschubser
Beiträge: 94
Registriert: 7. Mai 2007 09:42
Wohnort: Rodenbach

Beitrag von vwm »

Das Problem lässt sich doch ganz fein umgehen:

1. Ich weiß aus meinen Tests, dass ein Ersetzen der als gelöscht markierten Positionen passed.
2. Man erstelle sich einen Counter, der stets die aktuelle Zahl an Elementen beinhaltet.
3. Man inkremetiere den Counter beim erfolgreichen Hinzufügen und dekrementiere ihn beim erfolgreichen Entfernen.
4. Sollte das Einfügen den Counter derart verändern, dass er den Belegungsfaktor übersteigt, wird neu gehasht und dann erst eingefügt (und inkrementiert).

Das Resultat: Die Erweiterung der Hashtable hängt nicht von den Leichen ab.

yagami
Mausschubser
Mausschubser
Beiträge: 72
Registriert: 5. Okt 2006 03:02

Beitrag von yagami »

Testcase: testRemoveAndRehashing took 0.006 sec
FAILED
your table has not the correct size. may be you had count a removed object and expand your hashtable to early!
junit.framework.AssertionFailedError: your table has not the correct size. may be you had count a removed object and expand your hashtable to early!
at TestRehashing.testRemoveAndRehashing(TestRehashing.java:129)
ich bekomme diese fehler meldung aber ich verstehe nicht was hast löschen mit size von der Tabelle zu tun...nach dem löschen ändert sich die Tabllegrösse nicht oder?

HolgerF
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 263
Registriert: 16. Jan 2007 14:20
Kontaktdaten:

Beitrag von HolgerF »

Nein, aber wenn du beim Löschen die Objektanzahl nicht korrekt aktualisierst, könnte es bei der nächsten Einfügeoperation dazu kommen, dass du die Tabelle vergrößerst, obwohl das noch gar nicht nötig ist.

Werwolf
Windoof-User
Windoof-User
Beiträge: 39
Registriert: 10. Sep 2004 10:25

Beitrag von Werwolf »

Ich bekomme beim Test "testRemove" folgende Fehlermeldung :

after removing an existing object, which had a collision, function removeElement() returns true, instead of false.

Aber das soll es doch oder ?

Falls der zu löschende Schlüßel nicht existiert, dann gebe ich ein false zurück, und falls er existiert, wird er gelöscht, und ich gebe ein true, zurück.

Warum soll ich dan nein false zurück geben, wenn der Schlüßel, den ich lösche eine Kollision verursacht hat ?

Oder verstehe ich diese Fehlermeldung falsch ?

Benutzeravatar
Skullz
Mausschubser
Mausschubser
Beiträge: 44
Registriert: 23. Mai 2007 16:21

Beitrag von Skullz »

@Werwolf

Ich verstehe das so, dass zuerst addElement(x) aufgerufen wird und dann zwei Mal removeElement(x). Beim ersten Mal gibt er bei dir korrekterweise true aus, aber beim zweiten Mal existiert dieses Element nicht mehr, aber deine Implementierung gibt trotzdem ein true aus.

Ich vermute mal, du benutzt ne gelöscht-Flag, um entfernte Elemente zu kennzeichnen, vergisst das aber bei removeElement() zu bedenken, weswegen man bei dir auch bereits entfernte Elemente öfter "löschen" kann.
Schau da mal nach.

Benutzeravatar
Skullz
Mausschubser
Mausschubser
Beiträge: 44
Registriert: 23. Mai 2007 16:21

Beitrag von Skullz »

@yagami

Nach dem Löschen ändert sich zwar die Tabellengröße nicht, aber wenn du bei deiner Implementierung deine gelöschten Objekte nur als gelöscht markierst, kann es sein, dass du auch bereits gelöschte Elemente mitzählst, wenn du die Größe deiner HashTable errechnest. Somit bekommst du ein verfälschtes Ergebnis und wirst deine HashTable zu früh vergrößern, so dass du am Ende des Tests eben eine andere HashTable-Größe hast als sie eigentlich sein sollte.

Benutzeravatar
Gnomix
Computerversteher
Computerversteher
Beiträge: 306
Registriert: 31. Okt 2005 08:44

Beitrag von Gnomix »

Du musst prüfen, ob der Tabellenplatz leer ist oder das Element als gelöscht markiert ist, um dies zu umgehen.
Prüfst du nur auf leere Plätze, übersiehst du die als gelöscht markierten.
Ebenso mußt du beim suchen auch so lange suchen, bis du einen Platz findest, der leer ist, ist er nur als gelöscht markiert, gilt dies nicht.
Denn es könnte sein, dass du ein Element suchst, dass weiter hinten einsortiert ist, auf Grund der Kollisionsbehandlung.

Antworten

Zurück zu „Archiv“