Zwei Hashtables statt einer?

[LoN_Nemesis]

Hallo,

folgendes Szenario:

Ich habe eine eigene Klasse mit relativ vielen Variablen(~50 ints, 5 Strings und einige booleans). Davon erzeuge ich dann Instanzen, maximal sind es ca. so bis 100 Stück auf einmal. Ich verwalte diese in einer Hashtable und benutze als Schlüssel java.awt.Point, da ich sehr oft die Überprüfung machen muss, ob an einer bestimmten Stelle eine dieser Instanzen ist. Aber nun muss ich auch noch ziemlich oft überprüfen, ob ein NPC (das ist meine Klasse) noch lebt. Das mache ich über den Namen, denn der ist eindeutig. Allerdings ist es nun ziemlich ineffizient, wenn ich die Hashtable von vorne bis hinten durchsuchen muss, da ich ja als Schlüssel nur die Position habe. Die verändert sich aber im Laufe der Zeit und ist deshalb kein eindeutiger Identifikator für eine Instanz.

Sollte ich eine zweite Hashtable anlegen, mit dem gleichen Inhalt der ersten und hier den Namen als Schlüssel verwenden? Denn eigentlich speichert die Hashtable ja nur Referenzen auf Objekte wenn ich das richtig verstanden habe, also sollte doch der Speichermehrbedarf nicht so gravierend sein? Oder täusche ich mich und ich sollte statt einer Hashtable lieber eine andere Datenstruktur nehmen, bei der man für beide Suchen die gleiche Zeit hätte?

 

[Anmeldeboykottierer]

Denn eigentlich speichert die Hashtable ja nur Referenzen auf Objekte wenn ich das richtig verstanden habe, also sollte doch der Speichermehrbedarf nicht so gravierend sein?

Hi, an sich werden nur Referenzen gespeichert, egal wo. Das hat halt ganz generell einige Vorteile, aber das ist ein Thema für sich.

Was dein Problem angeht, du hast nur ca. 100 Instanzen? Da kannst du mit dem Weg auf jeden Fall arbeiten. Der Speicherbedarf für eine Referenz beträgt 4 Byte oder du jetzt also 400 oder 800 Byte belegen würdest, dass merkst du gar nicht an Unterschied.
Das Hauptproblem dürfte eher die Perfomance sein. Hier ist es wichtig sich die (möglichen) Datenstrukturen genauer anzuschauen.
Im Fall einer Hashlist geht das finden eines Eintrags sehr schnell. Du berechnest halt den Hash, schaust an der berechneten Position nach, alles linear. Das Problem ist es, dass du zwei Listen konsistent halten musst. Das was bei einer Hashlist zeit kostet ist das Berechnen der Hashes. Man möchte natürlich nicht den gesamten Speicher einfach mal für eine Hashtable verwenden, sondern möglichst nur die Menge an Speicher reservieren (und entsprechende Hashes berechnen), wie gerade benötigt werden. Dann wird die Map dyn. erweitert, neue Hashes erstellt und die alten Einträge entsprechend neu angeordnet.
Bei zwei Maps hast du also diesen Overhead auch gleich 2x.
Du siehst, dass hier irgendwann der Overhead größer werden dürfte als wenn du über eine Liste iterierst. Ohne hier sagen zu können und auch zu wollen, wann genau das der Fall wäre, bei gerademal zwei Listen und in der Größenordnung dürfte es noch lange nicht der Fall sein.
Da sollte aber auch das Durchsuchen von 100 Einträgen nicht wirklich viel Zeit kosten, hättest du ein paar zig-tausend NPCs, dann sieht dass eher anders aus.

Gruß Der Anmeldeboykottierer

 

[LoN_Nemesis]

Hallo,

vielen Dank für die Antwort. Ich werde nun 2 Hashtables führen. Das von dir angesprochene Problem tritt ja nur auf, wenn die Hashtable verändert wird, also wenn Objekte hinzukommen. Das passiert aber eigentlich alles nur einmal, also wenn ich das Level lade dann füge ich alle NPCs zu der Hashtable dazu. Während der "Hauptschleife" des Programmes wird dann nur sehr selten ein NPC hinzugefügt oder gelöscht, ich denke da kann ich auch locker 2 Hashtables führen.

 

[LoN_Nemesis]

Ähm da fällt mir ein, was passiert eigentlich wenn sich die Position eines NPCs verändert? Dann hat er neue Koordinaten, steht aber in der Hashtable immer noch mit den alten drin oder was?

 

[Leroy42]

steht aber in der Hashtable immer noch mit den alten drin oder was?

Die Hashtable verwaltet nur Referenzen, wenn sich nur die Instanzvariablen
deiner NPC-Instanzen ändern und du kein new NPC(...) aufrufst, sind auch die
in deiner Hashtable stehenden NPCs mitverändert, da es sich eben um ein-
unddasselbe Objekt handelt.

 

[LoN_Nemesis]

Hm, das verstehe ich nicht so ganz. Mein Schlüssel sind die Koordinaten einer Instanz. Soweit ich über Hashtables Bescheid weiss, berechnet sich der Hashwert (und damit der Speicherort eines Elementes) direkt aus dem Schlüssel.

Nehmen wir also an, ich plaziere einen NPC (einen Hufschmied!) an den Welt Koordinaten (13,97) und übergebe das Schlüssel/Wert Paar der Hashtable. Angenommen diese hat die Kapazität 10 und der berechnete Hashwert ist 8, der Hufschmied wird nun also an Position 8 gespeichert. Wenn sich nun seine Koordinaten ändern, dann würde sich auch sein Schlüssel ändern. Also der Hufschmied bewegt sich nun, sagen wir er geht in eine Taverne. Gleichzeitig erschaffe ich an der alten Position des Hufschmiedes einen neuen NPC, per geskriptetem Ereignis oder so. Dann gebe ich diese in die Hashtable, die dann folgende Feststellung trifft: Ah der Schlüssel ist bereits vorhanden, also überspeichere ich den alten Wert. Das ist aber falsch, denn in Wirklichkeit sollen beide NPCs in der Table sein, was auch kein Problem darstellt, da sie unterschiedliche Positionen haben.

Hm, doch lieber eine stinknormale Liste? Oder verstehe ich was falsch?

 

[SlaterB]

wenn sich der Schlüsse ändert, hat die Map natürlich ihre Probleme, da hast du schon recht,

nur allgemein gilt, dass es kein Problem ist, ein Objekt in der Map in einem anderen Kontext zu benutzen/ ändern,
wenns aber den Schlüssel betrifft..

naja du wirst schon wissen was du tust, hast ja selber die Probleme beschrieben