P9 TestRehashin2

Benutzeravatar
HerrDerFlammen
Mausschubser
Mausschubser
Beiträge: 79
Registriert: 16. Okt 2006 17:30
Wohnort: Dreieich
Kontaktdaten:

P9 TestRehashin2

Beitrag von HerrDerFlammen »

Testsuite: TestRehashing
Tests run: 2, Failures: 1, Errors: 0, Time elapsed: 0.053 sec

Testcase: testRehashing took 0.007 sec
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)


Kann mir jemand dazu was sagen? Natürlich zieh ich in meine Berechnungen für die Belegung auch die gelöschten Elemente mit ein, sonst kanns ja passieren, dass meine Tabelle zu 100% nur mit geloeschten belegt ist, und ich nix mehr einfuegen kann, was nicht schon einmal geloescht wurde (-> Problematik wurde ja bereits angesprochen)

edit: Das ist der einzige Test der noch fehlschlägt und ich hab ohne verkettung implementiert.
Das Lehren soll so sein, dass das Dargebotene als wertvolles Geschenk und nicht als saure Pflicht empfunden wird.
(Albert Einstein)

sonothar
Windoof-User
Windoof-User
Beiträge: 40
Registriert: 26. Okt 2005 00:15

Beitrag von sonothar »

also versteh ich dich richtig, dass du deine variable für die belegung nach dem löschen um 1 herabsetzt?
und hast du vielleicht die belegung auf >= 75% geprüft statt nur auf > 75%?
Bild

qveXx
Mausschubser
Mausschubser
Beiträge: 64
Registriert: 2. Dez 2005 19:02

Beitrag von qveXx »

Wieso berechnest du die gelöschten Objekte? Falls du einen Counter benutzt, dann muss der beim Löschen runter gezählt werden. Und es ist doch egal wenn deine Tabelle zu 100% aus gelöschten Elementen besteht (kann sie zwar nie, da ab 75% rehasht wird ;)) sobald du ein neues Element hinzufügst und auf eine Stelle mit einem gelöschten Objekt kommst, fragst du ab, ob das Element gelöscht ist oder nicht, weil es macht keinen Sinn gelöschte Objekte bis in alle Ewigkeit zu behalten.

Benutzeravatar
HerrDerFlammen
Mausschubser
Mausschubser
Beiträge: 79
Registriert: 16. Okt 2006 17:30
Wohnort: Dreieich
Kontaktdaten:

Beitrag von HerrDerFlammen »

Ich glaub ich bin nicht ganz richtig verstanden worden.
Kleines Beispiel:

HashMap mit size 5, extensionfaktor 2;
add(1)
add(2)
add(3)
rm(3)
rm(2)
rm(1)
add(4)
add(5)

Jetzt hab ich also 2 Elemente in meiner HashMap (+3gelöschte)
Wenn ich jetzt die gelöschten nicht in meine Belegung einbeziehe, dann hat sich meine Map nicht vergrößert und sie ist tatsächlich zu 100% belegt, weil 1*,2*,3*,4,5
Ich zähle also die gelöschten intern mit und erweiter meine Hashmap, wenn ich also element nummer 4 einfüge auf die größe 7 und füge dann noch die 5, also 1*,2*,3*,4,5,_,_.
Und nu bekomm ich den Test fehlgeschlagen. Wenn ich das aber nicht so mache, dann kann meine Tabelle tatsächlich zu 100% belegt sein und man kann nur noch gelöschte wieder einfügen...
Das Lehren soll so sein, dass das Dargebotene als wertvolles Geschenk und nicht als saure Pflicht empfunden wird.
(Albert Einstein)

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

Beitrag von HolgerF »

Nein, eben nicht. Du MUSST die gelöschten Plätze wiederverwenden, auch für andere Objekte als die, die vorher drin standen. Das erstbeste Objekt, das auf einem gelöschten Platz landen würde, wird dort eingefügt.

sonothar
Windoof-User
Windoof-User
Beiträge: 40
Registriert: 26. Okt 2005 00:15

Beitrag von sonothar »

wie holger schon gesagt hat, die wieder frei gewordenen pätze musst du auch als frei bezeichnen!!!

ich hoffe du weißt zu dem, dass, wenn du diese HashMap erweitern müsstest, dass du die auf 11 und nicht auf 7 erweitern musst!!!
5(table size) * 2(extensionfaktor) = 10 => 11 (nächste prim)
Bild

Antworten

Zurück zu „Archiv“