Die Leistung der TreeMap, HashMap und LinkedHashMap?

In der TreeMap - Elemente sind sortiert

In HashMap - Elemente sind nicht sortiert

So, wenn ich bedenke get, put und remove Methoden, welche Karte sollte ich für die Leistung?

  • Finden Sie in der Javadoc. HashMap angegeben ist, werden O(1): 'Konstante Leistung für die grundlegenden Operationen (get und put), vorausgesetzt, die hash-Funktion verteilt die Elemente richtig zu den Eimer'. TreeMap angegeben wird, um " garantiert log(n) Zeit Kosten für die containsKey, get, put und remove Operationen.
  • Ohne zu wissen, Ihre Kriterien für die Beurteilung, welche option besser wäre, diese Frage zu beantworten ist unmöglich. Klar, wenn Sie eine geordnete Sammlung nur TreeMap tun. Aber Sie wissen bereits, dass.
  • Ziemlich detailliert hier: difference-between-hashmap-linkedhashmap-and-treemap
  • Die akzeptierte Antwort sagt HashMap schneller ist. Aber die Javadocs für LinkedHashMap (Java 8) sagt, dass es geht deutlich schneller als HashMap. Also YMMV, je nach Ihren spezifischen Kriterien. Definitiv nicht verwenden TreeMap es sei denn, Sie benötigen Sie Sortieren, und verwenden Sie LinkedHashMap zu bewahren, insertion um.
InformationsquelleAutor Vicky | 2012-05-04
  1. 5

    Verwenden HashMap es sei denn, Sie haben ein Bedürfnis für die Bestellung. HashMap ist schneller.

    Sagte, Sie kann es einfach machen zu wechseln, indem Sie über die generische Schnittstelle, die als Ihre Erklärung:

     Map<String,String> M = new HashMap<String,String>();
 ...use M lots of places...

    Dann alles, was Sie tun müssen ist, wechseln Sie eine Stelle und der code verwendet die neue Karte geben.

    Edit:

    Eine einfache timing-test:

    import java.util.*;
class TimingTest {
  public static void main(String[] args) {
    Map<String,String> M = new HashMap<String,String>();
    long start = System.currentTimeMillis();
    for (int i = 0; i < 100000; i++) {
      M.put(Integer.toString(i), "foo");
    }
    long end = System.currentTimeMillis();
    System.out.println(end - start);
  }
}
    • Sie mir bitte sagen, Wie wird die hashmap schneller als treemap?? Treemap auf Werte zugreifen, die auf Tasten nacheinander. Können Sie mir bitte sagen, wie hashmap funktioniert??
    • Die Antwort ist mehr, als in diesem Kommentar. Nehmen Sie eine Daten-Strukturen-Klasse, oder Lesen, auf hash-Tabellen und rot-schwarz-Bäume auf Wikipedia. Hash-Tabellen sind O(1) fortgeführten arbeiten pro Betrieb, vorausgesetzt, dass eine gute hash-Funktion. Rot-schwarz-Bäume sind O(lg n) Arbeit pro Betrieb.
    • ok vielen Dank keith 🙂
    • Ich habe versucht, Beispiele für treemap und hashmap...ich eingegeben 100000 Eintrag in anzeigen und auf Sie zugreifen.. ich zählte die Zeit. aber das Ergebnis für meine Programme ist treemap-187 hashmap 206 bedeutet hashmap benötigt mehr Zeit...verwirrt, bitte erklären Sie mir, was ist Ihre Meinung dazu?
    • Habe ich nicht das gleiche Ergebnis. Putting 100000 Einträgen in einer Karte dauert etwa 60 msec für eine HashMap und 90 msec für eine TreeMap. Ich poste meinen code.
    • ok, Haben Sie versucht, mit beiden sequenziellen und nicht sequenziellen zahlen?

    InformationsquelleAutor Keith Randall
  2. 0

    Es hängt davon ab, wie schnell sich der hash und Vergleich die Funktionen sind auf den Tasten in der Karte angezeigt. Es hängt davon ab, ob Sie mehr daran interessiert, in der durchschnittlichen Fall Leistung oder worst-case-performance. Es hängt davon ab, ob Sie eine gute hash-Funktion angewendet, um Ihre Karte, Schlüssel, hash-Werte sollten gut verteilt die Hashfunktion die domain (ja, es hängt von Ihren Daten).

    Im Allgemeinen (wenn Sie kann nicht sein belästigt, um zu testen), eine hash-map ist oft eine gute Antwort, aber es ist auch unwahrscheinlich, dass es einen großen Unterschied machen, wenn Sie nicht über eine Tausende von Einträgen (für kleine Größen, eine "vec-Karte" kann auch gut funktionieren).

    InformationsquelleAutor dhardy
Schreibe einen Kommentar