Assoziativer Speicher welche Unterschiede?

[redbomber]

Hi zusammen,
kennt sich von euch jemand mit assoziativen Speichern aus?


Folgende Situation:
Ich habe sehr große Datenmengen.
diese sollen in einen solchen assoziativen Speicher eingetragen werden.
Der Zugriff erfolgt über die jeweilige Position der Daten (Key). Viele Positionen sind jedoch NICHT besetzt.
Der Zugriff erfolgt meist in aufsteigender Key Reihenfolge (z.B. suche nach den Daten an Position 10-1000).


Folgende Lösung bisher:
Zuerst hatte ich das ganze mit einer normalen HashMap gemacht.
Momentan verwende ich jedoch eine TreeMap, da diese ja sortiert ist und somit der Zugriff doch bestimmt schneller erfolgt. Vorallem wenn ich auf die Daten meist in aufsteigender Key Reihenfolge zugreife.

Problem ist aber dass vorallem die TreeMap viel Speicherplatz benötigt. Dies kommt vermutlich durch ihre Organisation (also auch leere Blätter im Tree besetzen den Speicher!?)
Zudem ist das befüllen der TreeMap recht langsam.
Bestimmt langsamer als in der HashMap, aber das müsste ich nochmal genauer nachmessen.

Fällt euch denn spontan ein anderer assoziativer Speicher ein?
Kennt jemand den SparseVector? Hat dieser hier eventuell hier Vorteile?

 

[Puste]

Worauf kommt es denn an? insert, remove, find? Also welche Operationen sind Laufzeitkritisch?

Weil je nach Anforderung tut es auch ein Array

 

[Marco13]

Oder um einen bestimmten Aspekt von Puste's (gerechtfertigter) Frage zu konkretisieren: Sind die Daten dynamisch, oder werden sie nur EINmal erstellt und danach immer nurnoch abgefragt?

 

[redbomber]

also die Daten werden nur einmal hinzugefügt,
danach bleibt dieser Assoziative Speicher immer gleich.

Es erfolgen dann nur noch Zugriffe.

 

[Ebenius]

TreeMap mit leeren Blättern? Hab ich was verpasst?

 

[ice-breaker]

Der Zugriff erfolgt über die jeweilige Position der Daten (Key). Viele Positionen sind jedoch NICHT besetzt.

wenn viele Positionen nicht besetzt sind, und die Daten nur einmal erstellt werden, frage ich mich was der Sinn dahinter ist? Denn Lücken um etwas einzufügen, werden dann ja nicht benötigt.

Der Zugriff erfolgt meist in aufsteigender Key Reihenfolge (z.B. suche nach den Daten an Position 10-1000).

Hmm, was sagst du zu Bäumen (Binärbaum, da Hauptspeicherorientiert)?
Die sind intern schon sortiert für deine Range-Suche (10 - 1000) und die Key-Positionen könnte man durch sowas wie einen Primary-Key sehr gut umsetzen. Also quasi nen Baum mit deinen Keys füllen und beide Anforderungen werden durch den Baum automatisch abgedeckt.