Une compréhension approfondie de la différence entre HashMap et TreeMap en Java

Tout d’abord, présentons ce qu’est Map. Dans le tableau, nous indexons son contenu via l'indice du tableau, tandis que dans la Map, nous indexons l'objet via l'objet. L'objet utilisé pour l'indexation est appelé clé et son objet correspondant est appelé valeur. C'est ce que nous appelons habituellement les paires clé-valeur.

HashMap utilise le hashcode pour rechercher rapidement son contenu, et tous les éléments de TreeMap conservent un certain ordre fixe. Si vous avez besoin d'obtenir un résultat ordonné, vous devez utiliser TreeMap (les éléments de HashMap L'ordre de tri n'est pas fixe. ).
HashMap non-thread-safe TreeMap non-thread-safe

Sécurité des threads
En Java, la sécurité des threads se reflète généralement sous deux aspects :
Plusieurs threads accèdent à la même instance Java (lecture). et modifier) ​​n'interféreront pas les uns avec les autres, ce qui se reflète principalement dans le mot-clé synchronisé. Tels que ArrayList et Vector, HashMap et Hashtable
(ce dernier a le mot-clé synchronisé avant chaque méthode). Si vous interagissez avec un objet List et que d'autres threads suppriment un élément, le problème surviendra.

2. Chaque fil de discussion a ses propres champs et ne sera pas partagé entre plusieurs fils de discussion. Cela se reflète principalement dans la classe java.lang.ThreadLocal, mais ne prend pas en charge les mots clés Java, tels que statique et transitoire.
Classe abstraite 1.AbstractMap et interface SortedMap
Classe abstraite AbstractMap : (HashMap hérite d'AbstractMap) remplace les méthodes equals() et hashCode() pour garantir que deux mappages égaux renvoient le même code de hachage. Deux cartes sont égales si elles sont de taille égale, contiennent les mêmes clés et si chaque clé a la même valeur dans les deux cartes. Le code de hachage d'une carte est la somme des codes de hachage des éléments de la carte, où chaque élément est une implémentation de l'interface Map.Entry. Par conséquent, deux mappages égaux rapporteront le même code de hachage quel que soit l’ordre interne des mappages.
Interface SortedMap : (TreeMap hérite de SortedMap) Elle est utilisée pour maintenir l'ordre ordonné des clés. L'interface SortedMap fournit des méthodes d'accès aux vues (sous-ensembles) de l'image, y compris deux points de terminaison. Le traitement d'un SortedMap est identique au traitement d'un SortedSet, sauf que le tri est effectué sur les clés de la carte. Les éléments ajoutés à une classe d'implémentation SortedMap doivent implémenter l'interface Comparable, sinon vous devez fournir à son constructeur une implémentation de l'interface Comparator. La classe TreeMap est sa seule implémentation.

2. Deux implémentations de Map conventionnelles
HashMap : basé sur l'implémentation de tables de hachage. L'utilisation de HashMap nécessite que la classe de clé ajoutée définisse clairement hashCode() et equals() [hashCode() et equals() peuvent être remplacés]. Afin d'optimiser l'utilisation de l'espace HashMap, vous pouvez régler la capacité initiale et le facteur de charge.
(1)HashMap() : Construisez une image de hachage vide
(2)HashMap(Map m) : Construisez une image de hachage et ajoutez tous les mappages de l'image m
(3)HashMap( int initialCapacity) : Construisez une image de hachage vide avec une capacité spécifique
(4)HashMap(int initialCapacity, float loadFactor) : Construisez une image de hachage vide avec une capacité et un facteur de charge spécifiques
TreeMap : Basé sur l'implémentation d'un arbre rouge-noir. Il n'existe aucune option de réglage pour TreeMap car l'arborescence est toujours équilibrée.
(1)TreeMap() : Construisez un arbre d'images vide
(2)TreeMap(Map m) : Construisez un arbre d'images et ajoutez tous les éléments dans l'image m
(3)TreeMap(Comparator c ) : Créez une arborescence d'images et utilisez un comparateur spécifique pour trier les mots-clés
(4)TreeMap(SortedMap s) : Créez une arborescence d'images, ajoutez tous les mappages dans l'arborescence d'images et utilisez les images ordonnées Le même comparateur tri

3. Deux propriétés générales de Map
HashMap : convient pour insérer, supprimer et positionner des éléments dans Map.
Treemap : convient pour parcourir les clés dans l'ordre naturel ou dans un ordre personnalisé.

4. Résumé
HashMap est généralement un peu plus rapide que TreeMap (en raison de la structure des données des arbres et des tables de hachage). Il est recommandé d'utiliser davantage HashMap et de n'utiliser TreeMap que lorsque le tri de la carte est requis. .

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)); 
} 
} 
}

Les résultats d'exécution sont les suivants :
map.get(key) est :ddd
map.get(key) est :bbb
map.get(key) est :ccc
map.get(key) est :aaa
tab.get(key) est :bbb
tab.get(key) est :aaa
tab.get(key) est :ddd
tab.get(key) est :ccc
tmp.get(key) est :aaa
tmp.get(key) est :bbb
tmp.get(key) est :ccc
tmp. get(key) is :cdc
Les résultats de HashMap ne sont pas triés, mais les résultats générés par TreeMap sont triés.
Venons-en au sujet de cet article. Donnons d'abord un exemple pour illustrer comment utiliser HashMap :

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); 
} 
}

Dans HashMap, récupérez la valeur via get(), insérez la valeur via put() et ContainsKey() pour vérifier si l'objet est déjà existe. On peut voir que par rapport au fonctionnement d'ArrayList, mis à part l'indexation de son contenu via une clé, HashMap n'est pas très différent sur d'autres aspects.
Comme introduit précédemment, HashMap est basé sur HashCode. Il existe une méthode HashCode() dans la super classe Object de tous les objets, mais elle, comme la méthode equals, n'est pas applicable à toutes les situations, nous devons donc nous réécrire. .Méthode HashCode(). Voici un exemple :

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中文网！