Ein tiefgreifendes Verständnis des Unterschieds zwischen HashMap und TreeMap in Java

Lassen Sie uns zunächst vorstellen, was Map ist. Im Array indizieren wir seinen Inhalt über den Array-Index, während wir in der Map das Objekt über das Objekt indizieren. Das für die Indizierung verwendete Objekt wird als Schlüssel bezeichnet, und das entsprechende Objekt wird als Wert bezeichnet. Dies nennen wir normalerweise Schlüssel-Wert-Paare.

HashMap verwendet Hashcode, um seinen Inhalt schnell zu durchsuchen, und alle Elemente in TreeMap behalten eine bestimmte feste Reihenfolge bei. Wenn Sie ein geordnetes Ergebnis benötigen, sollten Sie TreeMap verwenden (die Sortierreihenfolge der Elemente in HashMap ist nicht festgelegt). ).
HashMap nicht Thread-sicher TreeMap nicht Thread-sicher

Thread-Sicherheit
In Java spiegelt sich Thread-Sicherheit im Allgemeinen in zwei Aspekten wider:
1. Mehrere Threads greifen auf dieselbe Java-Instanz zu (lesen). und Modifizieren) stören sich nicht gegenseitig, was sich hauptsächlich im Schlüsselwort synchronisiert widerspiegelt. Wie ArrayList und Vector, HashMap und Hashtable
(letzteres hat vor jeder Methode das synchronisierte Schlüsselwort). Wenn Sie ein List-Objekt interatorieren und andere Threads ein Element entfernen, tritt das Problem auf.

2. Jeder Thread hat seine eigenen Felder und wird nicht von mehreren Threads gemeinsam genutzt. Es spiegelt sich hauptsächlich in der Klasse java.lang.ThreadLocal wider, bietet jedoch keine Unterstützung für Java-Schlüsselwörter wie „statisch“ und „transient“.
1.AbstractMap-Abstraktklasse und SortedMap-Schnittstelle
AbstractMap-Abstraktklasse: (HashMap erbt AbstractMap) überschreibt die Methoden equal() und hashCode(), um sicherzustellen, dass zwei gleiche Zuordnungen denselben Hash-Code zurückgeben. Zwei Karten sind gleich, wenn sie gleich groß sind, die gleichen Schlüssel enthalten und jeder Schlüssel in beiden Karten den gleichen Wert hat. Der Hash-Code einer Karte ist die Summe der Hash-Codes der Elemente der Karte, wobei jedes Element eine Implementierung der Map.Entry-Schnittstelle ist. Daher melden zwei gleiche Zuordnungen unabhängig von der internen Reihenfolge der Zuordnungen denselben Hash-Code.
SortedMap-Schnittstelle: (TreeMap erbt von SortedMap) Sie wird verwendet, um die geordnete Reihenfolge der Schlüssel beizubehalten. Die SortedMap-Schnittstelle bietet Zugriffsmethoden auf Ansichten (Teilmengen) des Bildes, einschließlich zweier Endpunkte. Die Verarbeitung einer SortedMap ist dasselbe wie die Verarbeitung eines SortedSet, mit der Ausnahme, dass die Sortierung anhand der Schlüssel der Karte durchgeführt wird. Elemente, die einer SortedMap-Implementierungsklasse hinzugefügt werden, müssen die Comparable-Schnittstelle implementieren, andernfalls müssen Sie ihrem Konstruktor eine Implementierung der Comparator-Schnittstelle bereitstellen. Die TreeMap-Klasse ist ihre einzige Implementierung.

2. Zwei herkömmliche Map-Implementierungen
HashMap: basierend auf der Hash-Tabellen-Implementierung. Die Verwendung von HashMap erfordert, dass die hinzugefügte Schlüsselklasse hashCode() und equal() klar definiert [hashCode() und equal() können überschrieben werden] Um die Nutzung des HashMap-Speicherplatzes zu optimieren, können Sie die anfängliche Kapazität und den Auslastungsfaktor optimieren.
(1)HashMap(): Erstellen Sie ein leeres Hash-Bild
(2)HashMap(Map m): Erstellen Sie ein Hash-Bild und fügen Sie alle Zuordnungen von Bild m hinzu
(3)HashMap( int initialCapacity): Erstellen Sie ein leeres Hash-Bild mit einer bestimmten Kapazität
(4)HashMap(int initialCapacity, float loadFactor): Erstellen Sie ein leeres Hash-Bild mit einer bestimmten Kapazität und einem bestimmten Lastfaktor
TreeMap: Basierend auf der Rot-Schwarz-Baum-Implementierung. Für TreeMap gibt es keine Optimierungsoptionen, da der Baum immer ausgeglichen ist.
(1)TreeMap(): Konstruieren Sie einen leeren Bildbaum
(2)TreeMap(Map m): Konstruieren Sie einen Bildbaum und fügen Sie alle Elemente im Bild m hinzu
(3)TreeMap(Comparator c ): Erstellen Sie einen Bildbaum und verwenden Sie einen bestimmten Komparator, um die Schlüsselwörter zu sortieren
(4)TreeMap(SortedMap s): Erstellen Sie einen Bildbaum, fügen Sie alle Zuordnungen im Bildbaum hinzu und verwenden Sie die geordneten Bild-s. Derselbe Komparator Sortieren

3. Zwei allgemeine Map-Eigenschaften
HashMap: geeignet zum Einfügen, Löschen und Positionieren von Elementen in Map.
Baumkarte: geeignet zum Durchlaufen von Schlüsseln in natürlicher oder benutzerdefinierter Reihenfolge.

4. Zusammenfassung
HashMap ist normalerweise etwas schneller als TreeMap (aufgrund der Datenstruktur von Bäumen und Hash-Tabellen). Es wird empfohlen, HashMap häufiger zu verwenden und TreeMap nur zu verwenden, wenn eine Sortierung der Karte erforderlich ist .

import java.util.HashMap; 
import java.util.Hashtable; 
import java.util.Iterator; 
import java.util.Map; 
import java.util.TreeMap; 
public class HashMaps { 
public static void main(String[] args) { 
Map<String, String> map = new HashMap<String, String>(); 
map.put("a", "aaa"); 
map.put("b", "bbb"); 
map.put("c", "ccc"); 
map.put("d", "ddd"); 
Iterator<String> iterator = map.keySet().iterator(); 
while (iterator.hasNext()) { 
Object key = iterator.next(); 
System.out.println("map.get(key) is :" + map.get(key)); 
} 
// 定义HashTable,用来测试 
Hashtable<String, String> tab = new Hashtable<String, String>(); 
tab.put("a", "aaa"); 
tab.put("b", "bbb"); 
tab.put("c", "ccc"); 
tab.put("d", "ddd"); 
Iterator<String> iterator_1 = tab.keySet().iterator(); 
while (iterator_1.hasNext()) { 
Object key = iterator_1.next(); 
System.out.println("tab.get(key) is :" + tab.get(key)); 
} 
TreeMap<String, String> tmp = new TreeMap<String, String>(); 
tmp.put("a", "aaa"); 
tmp.put("b", "bbb"); 
tmp.put("c", "ccc"); 
tmp.put("d", "cdc"); 
Iterator<String> iterator_2 = tmp.keySet().iterator(); 
while (iterator_2.hasNext()) { 
Object key = iterator_2.next(); 
System.out.println("tmp.get(key) is :" + tmp.get(key)); 
} 
} 
}

Die laufenden Ergebnisse sind wie folgt:
map.get(key) ist :ddd
map.get(key) ist :bbb
map.get(key) ist :ccc
map.get(key) ist :aaa
tab.get(key) ist :bbb
tab.get(key) ist :aaa
tab.get(key) ist :ddd
tab.get(key) ist :ccc
tmp.get(key) ist :aaa
tmp.get(key) ist :bbb
tmp.get(key) ist :ccc
tmp. get(key) ist :cdc
Die Ergebnisse von HashMap werden nicht sortiert, aber die von TreeMap ausgegebenen Ergebnisse werden sortiert.
Kommen wir zum Thema dieses Artikels. Lassen Sie uns zunächst ein Beispiel geben, um die Verwendung von HashMap zu veranschaulichen:

import java.util.*; 
public class Exp1 { 
public static void main(String[] args){ 
HashMap h1=new HashMap(); 
Random r1=new Random(); 
for (int i=0;i<1000;i++){ 
Integer t=new Integer(r1.nextInt(20)); 
if (h1.containsKey(t)) 
((Ctime)h1.get(t)).count++; 
else 
h1.put(t, new Ctime()); 
} 
System.out.println(h1); 
} 
} 
class Ctime{ 
int count=1; 
public String toString(){ 
return Integer.toString(count); 
} 
}

Rufen Sie in HashMap den Wert über get() ab, fügen Sie den Wert über put() ein und verwenden Sie ContainsKey(), um zu überprüfen, ob das Objekt bereits vorhanden ist existiert. Es ist ersichtlich, dass sich HashMap im Vergleich zur Funktionsweise von ArrayList, abgesehen von der Indizierung des Inhalts über den Schlüssel, in anderen Aspekten nicht wesentlich unterscheidet.
Wie bereits erwähnt, basiert HashMap auf HashCode. Es gibt eine HashCode()-Methode in der Superklasse Object aller Objekte, die jedoch, wie die equal-Methode, nicht auf alle Situationen anwendbar ist, daher müssen wir uns selbst neu schreiben . HashCode()-Methode. Hier ist ein Beispiel:

import java.util.*; 
public class Exp2 { 
public static void main(String[] args){ 
HashMap h2=new HashMap(); 
for (int i=0;i<10;i++) 
h2.put(new Element(i), new Figureout()); 
System.out.println("h2:"); 
System.out.println("Get the result for Element:"); 
Element test=new Element(5); 
if (h2.containsKey(test)) 
System.out.println((Figureout)h2.get(test)); 
else 
System.out.println("Not found"); 
} 
} 
class Element{ 
int number; 
public Element(int n){ 
number=n; 
} 
} 
class Figureout{ 
Random r=new Random(); 
boolean possible=r.nextDouble()>0.5; 
public String toString(){ 
if (possible) 
return "OK!"; 
else 
return "Impossible!"; 
} 
}

在这个例子中，Element用来索引对象Figureout,也即Element为key，Figureout为value。在Figureout中随机生成一个浮点数，如果它比0.5大，打印"OK!"，否则打印"Impossible!"。之后查看Element(3)对应的Figureout结果如何。 

结果却发现，无论你运行多少次，得到的结果都是"Not found"。也就是说索引Element(3)并不在HashMap中。这怎么可能呢？ 
原因得慢慢来说：Element的HashCode方法继承自Object，而Object中的HashCode方法返回的HashCode对应于当前的地址，也就是说对于不同的对象，即使它们的内容完全相同，用HashCode（）返回的值也会不同。这样实际上违背了我们的意图。因为我们在使用 HashMap时，希望利用相同内容的对象索引得到相同的目标对象，这就需要HashCode()在此时能够返回相同的值。在上面的例子中，我们期望 new Element(i) (i=5)与 Elementtest=newElement(5)是相同的，而实际上这是两个不同的对象，尽管它们的内容相同，但它们在内存中的地址不同。因此很自然的，上面的程序得不到我们设想的结果。下面对Element类更改如下： 

class Element{ 
int number; 
public Element(int n){ 
number=n; 
} 
public int hashCode(){ 
return number; 
} 
public boolean equals(Object o){ 
return (o instanceof Element) && (number==((Element)o).number); 
} 
}

在这里Element覆盖了Object中的hashCode()和equals()方法。覆盖hashCode()使其以number的值作为 hashcode返回，这样对于相同内容的对象来说它们的hashcode也就相同了。而覆盖equals()是为了在HashMap判断两个key是否相等时使结果有意义（有关重写equals()的内容可以参考我的另一篇文章《重新编写Object类中的方法》）。修改后的程序运行结果如下： 
h2: 
Get the result for Element: 
Impossible! 
请记住：如果你想有效的使用HashMap，你就必须重写在其的HashCode()。 
还有两条重写HashCode()的原则： 
[list=1] 
不必对每个不同的对象都产生一个唯一的hashcode，只要你的HashCode方法使get()能够得到put()放进去的内容就可以了。即"不为一原则"。 

生成hashcode的算法尽量使hashcode的值分散一些，不要很多hashcode都集中在一个范围内，这样有利于提高HashMap的性能。即"分散原则"。至于第二条原则的具体原因，有兴趣者可以参考Bruce Eckel的《Thinking in Java》，在那里有对HashMap内部实现原理的介绍，这里就不赘述了。 
掌握了这两条原则，你就能够用好HashMap编写自己的程序了。不知道大家注意没有，java.lang.Object中提供的三个方法：clone()，equals()和hashCode()虽然很典型，但在很多情况下都不能够适用，它们只是简单的由对象的地址得出结果。这就需要我们在自己的程序中重写它们，其实java类库中也重写了千千万万个这样的方法。利用面向对象的多态性——覆盖，Java的设计者很优雅的构建了Java的结构，也更加体现了Java是一门纯OOP语言的特性。

更多Java中HashMap和TreeMap的区别深入理解相关文章请关注PHP中文网！