Datentypen ArrayList vs TreeMap

[Neumi5694]

Ich befasse mich erst seit Kurzem mit Maps und mir ist der Gedanke gekommen, ob es sinnvoll wäre, größere Listen von Objekten durch solche zu ersetzen. Der Grund wäre die Suche nach bestimmten Objekten in der Liste.
Zur Zeit arbeite ich nach diesem Schema:

public class MyClass {
    private String id;
    //andere Eigenschaften
    public String getId() {
        return this.id;
    }
    public String setId(String newId) {
        this.id = newId;
    }
    public static MyClass getMyClass(String id, Iterable<MyClass> list) {
        if (list != null) {
            for(MyClass oneItem : list) {
                if (oneItem.getId().equals(id)) {
                    return oneItem;
                }
            }
        }
        return null;
    }
}

Wie sinnvoll wäre es, anstatt Listen ein TreeMap<String, MyClass> Objekt zu verwenden und das richtige Objekt per put-Methode zu ermitteln?

public class MyClass {
    private String id;
    //andere Eigenschaften
    public String getId() {
        return this.id;
    }
    public String setId(String newId) {
        this.id = newId;
    }
    public static MyClass getMyClass(String id, Map<String,MyClass> map) {
        if (map != null) {
            return map.get(id);
        } else {
            return null;
        }
    }
}

Sind TreeMaps performanter als eine "normale" Schleife?
Klar wird es etwas komplizierter, wenn man die Id eines Objektes ändern will, aber das passiert praktisch fast nie.

 

[InfectedBytes]

für so etwas wäre eine HashMap am schnellsten.

HashMap<String, MyClass> map = new HashMap<>();
map.put(obj.getId(), obj);
map.get("id123");

 

[Thallius]

für so etwas wäre eine HashMap am schnellsten.

HashMap<String, MyClass> map = new HashMap<>();
map.put(obj.getId(), obj);
map.get("id123");

Am schnellsten ist da relativ. Schnell hingeschrieben sicherlich aber für den Computer schwerer zu verarbeiten. Das bedeuetet Du sparst einmal Zeit beim Tippen aber der User wartet u.U. jedesmal auf das Ergebnis...

@TO: Man kann das nicht generalisieren. Es kommt immer auf die Anwandung an. Welche Abfragen werden benötiogt und wie oft werden die gemacht. Muss öfter sortiert werden? Nach welchen Kritierien werden die Daten gesucht? etc etc. Das alles spielt eine Rolle bei der Entscheidung welche Collection für den jeweiligen Anwendungsfall die beste ist.

I.d.R. würde ich aber sagen, je einfacher die Collection umso schneller sind erstmal die Zugriffe. Eine Index-Basierte Collection ist immer schneller als eine Key-Basierte. Es sei denn man holt die Daten eh IMMER nur nach Key und nie indem man einfach durch die Liste iteriert.

Du siehst, alles nicht so einfach. Es sei denn Du machst es Dir so einfach wie mein Vorposter und nimmst das was es DIR am einfachsten macht

Gruß

Claus

 

[InfectedBytes]

wenn man eine menge an objekten durch eine string id finden möchte, ist eine hashmap nunmal am schnellsten.
HashMaps haben nunmal nach Konstruktion einen konstante Zeitaufwand beim finden.
Sortierte Bäume (wie die TreeMap) haben hingegen eine logarithmische Laufzeit.

 

[Neumi5694]

Danke für die Infos.
Es geht um Artikellisten mit String-ID, diese haben die meisten Einträge (mehrere Hundert bis auch mal mehrere Tausend).
Für andere Listen mit maximal 50 Einträgen werde ich wohl bei der einfachen ArrayList beiben.

Ich werde wohl also mal die HashMap ins Auge fassen (und ich muss zugeben, dass ich dachte, dass die TreeMap eine Erweiterung der Hash-Map ist).

 

[InfectedBytes]

TreeMap baut eine sortierte Baumstruktur auf, und garantiert eine bestimmte Ordnung. Wenn du nun ein Element mit einer bestimmten ID innerhalb dieser Map suchen willst, muss die Struktur eben durchlaufen werden. Da sie aber sortiert ist, benötigst du eben nur logarithmische zeit.

Die HashMap gibt dir keinerlei Garantie über die Ordnung der Schlüssel. Allerdings kannst du dafür eben mit konstanter zeit über die ID das jeweilige Objekt bekommen. Dies geschieht durch Nutzung des jeweiligen hashcodes des Schlüssels, wodurch im Grunde direkt zum jeweiligen Objekt gesprungen wird.

 

[Thallius]

Sobald etwas vierstellig in der Anzahl wird, benutze ich immer Datenbanken.

Gruß

Claus