An in-depth understanding of the difference between HashMap and TreeMap in Java

First introduce what is Map. In the array, we index its content through the array subscript, while in the Map, we index the object through the object. The object used for indexing is called key, and its corresponding object is called value. This is what we usually call key-value pairs.

HashMap uses hashcode to quickly search its content, and all elements in TreeMap maintain a certain fixed order. If you need to get an ordered result, you should use TreeMap (the elements in HashMap The sorting order is not fixed).
HashMap non-thread safe TreeMap non-thread safe

Thread safety
In Java, thread safety is generally reflected in two aspects:
1. Multiple threads access the same java instance (read and modify) will not interfere with each other, which is mainly reflected in the keyword synchronized. Such as ArrayList and Vector, HashMap and Hashtable
(the latter has the synchronized keyword before each method). If you are interatoring a List object and other threads remove an element, the problem will arise.

2. Each thread has its own fields and will not be shared among multiple threads. It is mainly reflected in the java.lang.ThreadLocal class, but does not have Java keyword support, such as static and transient.
1.AbstractMap abstract class and SortedMap interface
AbstractMap abstract class: (HashMap inherits AbstractMap) covers the equals() and hashCode() methods to ensure that two equal mappings return the same hash code. Two maps are equal if they are equal in size, contain the same keys, and each key has the same value in both maps. The hash code of a map is the sum of the hash codes of the elements of the map, where each element is an implementation of the Map.Entry interface. Therefore, two equal mappings will report the same hash code regardless of the internal ordering of the mappings.
SortedMap interface: (TreeMap inherits from SortedMap) It is used to maintain the ordered sequence of keys. The SortedMap interface provides access methods to views (subsets) of the image, including two endpoints. Processing a SortedMap is the same as processing a SortedSet, except that the sorting is performed on the keys of the map. Elements added to a SortedMap implementation class must implement the Comparable interface, otherwise you must provide its constructor with an implementation of the Comparator interface. The TreeMap class is its only implementation.

2. Two conventional Map implementations
HashMap: based on hash table implementation. Using HashMap requires that the added key class clearly defines hashCode() and equals() [hashCode() and equals() can be overridden]. In order to optimize the use of HashMap space, you can tune the initial capacity and load factor.
(1)HashMap(): Construct an empty hash image
(2)HashMap(Map m): Construct a hash image and add all mappings of image m
(3)HashMap( int initialCapacity): Construct an empty hash image with a specific capacity
(4)HashMap(int initialCapacity, float loadFactor): Construct an empty hash image with a specific capacity and load factor
TreeMap: Based on Red-black tree implementation. There are no tuning options for TreeMap because the tree is always balanced.
(1)TreeMap(): Construct an empty image tree
(2)TreeMap(Map m): Construct an image tree and add all elements in image m
(3)TreeMap(Comparator c ): Build an image tree, and use a specific comparator to sort keywords
(4)TreeMap(SortedMap s): Build an image tree, add all mappings in the image tree s, and use the same as the ordered image s The same comparator sorting

3. Two general Map properties
HashMap: suitable for inserting, deleting and positioning elements in Map.
Treemap: Suitable for traversing keys in natural order or custom order.

4. Summary
HashMap is usually a little faster than TreeMap (due to the data structure of trees and hash tables). It is recommended to use HashMap more and only use TreeMap when sorted Maps are needed.

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

The running results are as follows:
map.get(key) is :ddd
map.get(key) is :bbb
map.get(key) is :ccc
map.get(key) is :aaa
tab.get(key) is :bbb
tab.get(key) is :aaa
tab.get(key) is :ddd
tab. get(key) is :ccc
tmp.get(key) is :aaa
tmp.get(key) is :bbb
tmp.get(key) is :ccc
tmp.get( key) is :cdc
The results of HashMap are not sorted, but the results output by TreeMap are sorted.
Let’s get to the topic of this article. Let’s first give an example to explain how to use 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); 
} 
}

In HashMap, get() is used to obtain value, put() is used to insert value, and ContainsKey() is used to check whether the object already exists. It can be seen that compared with the operation of ArrayList, apart from indexing its content through key, HashMap is not much different in other aspects.
As introduced before, HashMap is based on HashCode. There is a HashCode() method in the super class Object of all objects, but it, like the equals method, is not applicable to all situations, so we need to rewrite ourselves. HashCode() method. Here is an example:

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