Welche Collection ist die richtige ? Listen mergen

[little_b]

Hallo,

Ich habe 2 Listen in die ich zusammenfügen (mergen) möchte.

Beispiel :

Liste A Object :
absolutePath (1)
serverDate (2)

Liste B Object :
absolutePath (1)
clientDate (3)

?Collection? AB Object :
absolutePath (1)
serverDate (2)
clientDate (3)


Das Object kommt nur einmal vor, wobei absolutePath der Key sein koennte.
Ist es in beiden Listen vorhanden, so wird ein AB Object daraus erzeugt.
Ist es nur in einer Liste vorhanden so wird auch ein AB Object daraus erzeugt
und nicht vorhandene Daten bleiben null.

TreeMap ist vorsortiert, keine Ahnung ob das wirklich ist was ich brauche.
Zum überprüfen ob es schon vorhanden ist wäre es vielleicht gut.
Ich möchte es später in einem JTable sortiert anzeigen lassen, aber ich
habe hier in der FAQ gelesen, das eine nachträgliche Sortierung besser
ist.
Ich weiss nicht wie effizient HashMap ist. Oder vielleicht doch eine Liste?

Es handelt sich dabei um maximal so an die 100.000 Objekte. Wobei ein
Objekt noch so 3-4 Attribute mehr hat als hier aufgeführt.


dank vorab,

basti

 

[Marco13]

Hi

Die Frage "HashMap oder Liste" ist imho etwas unsinnig. Bei einer Map werden Objekte auf andere Objeke abgebildet. Bei einer List stehen die Objekte nur hintereinander drin. Eine Alternative wäre noch eine Set (HashSet), wo sichergestellt ist, dass jedes Objekt nur einmal vorkommt.

Wo du das Ergebnis dann hinschreibst, ist aber eigentlich egal. Entscheidend ist, dass du zu jedem Objekt aus A schnell das passende Objekt aus B findest. Du könntest den Inhalt der Liste B dazu in eine HashMap einfügen, die den String (abolutePath) aus das jeweilige Objekt mappt.

List<Content> listA = ...
List<Content> listB = ...

HashMap<String, Content> mapB = new HashMap<String, Content>();
for (Content c : listB)
{
    mapB.put(c.getAbsolutePath(), c);
}

List<Content> result = new ArrayList<Content>();
for (Content cA : listA)
{
    // Hole aus der listB das Objekt cB, das den gleichen abolutePath hat, wie cA 
    Content cB = mapB.get(cA.getAbsolutePath();

    // Erstelle ein Content-Objekt, das alle Info's enthält, die
    // mindestens in einem der beiden Objekte enthalten sind
    // (cB kann auch null sein!)
    result.add(new Content(cA, cB));
}

bye

 

[Zunera]

Hallo little_b,

[edit: korrigierter Text - sorry vonwegen der Verwirrung]
also ich wüßte jetzt nicht, was gegen eine TreeMap spricht, sie scheint mir für dein Anliegen bestens geeignet, denn im Gegensatz zu einer Liste braucht eine TreeMap nur O(log n) Operationen zum Auffinden von vorhandenen Objekten, während in einer Liste die gesamte Liste bis zum gefundenen Objekt durchlaufen wird.
Also angenommen, es sind 10.000 Objekte in einer Liste, also braucht es im Durchschnitt 5.000 Vergleiche (MAX 10.000), bis das gewünschte Objekt gefunden ist, bei einer TreeMap mit ebensovielen Objekten MAXIMAL 14 Vergleiche!
Bei Listen KANN das Einsortieren wiederum effizienter sein, da ein Objekt einfach nur ans Ende (oder den Anfang) der Liste gehängt wird - bei einer TreeMap wird das Objekt (wiederum mit max. 14 Vergleichen) einsortiert (bei gleichem Beispiel).

Viele Grüße

[edit: HashMaps können bei guten Hashfunktionen günstiger sein]

 

[little_b]

Erstmal vielen Dank.

So wie ich das verstanden habe ist es bei meinem Problem schon wichtig
zwischen einer Liste und einer HashMap zu unterscheiden.

Der Vorteil gegenüber einer Liste ist das ich beim Zusammenfügen viel
Zeit spare. Ich müsste eine Liste einmal komplett durchlaufen um
nach zuschauen ob das Element schon vorhanden ist, hingegen ich bei
einer HashMap im Idealfall einen Suchzugriff von eins habe.

Ich habe mich für die HashMap entschieden und sortiere das später.

danke 🙂