Java에서 HashMap과 TreeMap의 차이점에 대한 심층적인 이해

먼저 Map이 무엇인지 소개하겠습니다. 배열에서는 배열 첨자를 통해 콘텐츠의 색인을 생성하고, 맵에서는 객체를 통해 객체의 색인을 생성합니다. 색인에 사용되는 객체를 키라고 하며 해당 객체를 값이라고 합니다. 이것이 우리가 일반적으로 키-값 쌍이라고 부르는 것입니다.

HashMap은 콘텐츠를 빠르게 검색하기 위해 해시코드를 사용하며, TreeMap의 모든 요소는 일정한 고정 순서를 유지합니다. 정렬된 결과를 얻으려면 TreeMap을 사용해야 합니다(HashMap의 요소 정렬 순서는 고정되어 있지 않습니다). ).
HashMap 비스레드 안전 TreeMap 비스레드 안전

스레드 안전성
Java에서 스레드 안전성은 일반적으로 두 가지 측면으로 반영됩니다.
여러 스레드가 동일한 Java 인스턴스에 액세스합니다(읽기). 및 수정)은 서로 간섭하지 않으며 이는 주로 동기화된 키워드에 반영됩니다. ArrayList 및 Vector, HashMap 및 Hashtable
등(후자는 각 메소드 앞에 동기화 키워드가 있음) List 객체를 상호작용하는 중이고 다른 스레드가 요소를 제거하는 경우 문제가 발생합니다.

2. 각 스레드에는 자체 필드가 ​​있으며 여러 스레드 간에 공유되지 않습니다. 주로 java.lang.ThreadLocal 클래스에 반영되지만 static, temporary 등의 Java 키워드 지원은 없습니다.
1.AbstractMap 추상 클래스 및 SortedMap 인터페이스
AbstractMap 추상 클래스: (HashMap은 AbstractMap을 상속함) equals() 및 hashCode() 메서드를 재정의하여 두 개의 동일한 매핑이 동일한 해시 코드를 반환하도록 합니다. 두 맵의 크기가 동일하고, 동일한 키를 포함하며, 각 키가 두 맵에서 동일한 값을 갖는 경우 두 맵은 동일합니다. 지도의 해시 코드는 지도 요소의 해시 코드 합계입니다. 여기서 각 요소는 Map.Entry 인터페이스의 구현입니다. 따라서 두 개의 동일한 매핑은 매핑의 내부 순서에 관계없이 동일한 해시 코드를 보고합니다.
SortedMap 인터페이스: (TreeMap은 SortedMap에서 상속됨) 키의 정렬된 순서를 유지하는 데 사용됩니다. SortedMap 인터페이스는 두 개의 엔드포인트를 포함하여 이미지의 보기(하위 집합)에 대한 액세스 방법을 제공합니다. SortedMap 처리는 정렬이 맵의 키에 대해 수행된다는 점을 제외하면 SortedSet 처리와 동일합니다. SortedMap 구현 클래스에 추가된 요소는 Comparable 인터페이스를 구현해야 합니다. 그렇지 않으면 해당 생성자에 Comparator 인터페이스 구현을 제공해야 합니다. TreeMap 클래스는 유일한 구현입니다.

2. 두 가지 기존 Map 구현
HashMap: 해시 테이블 구현 기반. HashMap을 사용하려면 추가된 키 클래스가 hashCode() 및 equals()를 명확하게 정의해야 합니다. [hashCode() 및 equals()는 재정의될 수 있습니다.] HashMap 공간 사용을 최적화하기 위해 초기 용량 및 로드 요소를 조정할 수 있습니다.
(1)HashMap(): 빈 해시 이미지 생성
(2)HashMap(Map m): 해시 이미지를 생성하고 이미지 m의 모든 매핑을 추가합니다.
(3)HashMap( intinitialCapacity): 특정 용량을 가진 빈 해시 이미지 생성
(4)HashMap(intinitialCapacity, float loadFactor): 특정 용량 및 로드 팩터를 가진 빈 해시 이미지 생성
TreeMap: 레드-블랙 트리 구현을 기반으로 합니다. 트리는 항상 균형을 이루기 때문에 TreeMap에 대한 조정 옵션은 없습니다.
(1)TreeMap(): 빈 이미지 트리 생성
(2)TreeMap(Map m): 이미지 트리를 생성하고 이미지 m에 모든 요소 추가
(3)TreeMap(Comparator c ): 이미지 트리를 구축하고 특정 비교기를 사용하여 키워드 정렬
(4)TreeMap(SortedMap s): 이미지 트리를 구축하고 이미지 트리에 모든 매핑을 추가하고 정렬된 이미지를 사용합니다. 동일한 비교기 정렬

3. 두 가지 일반적인 Map 속성
HashMap: Map에 요소를 삽입, 삭제 및 위치 지정하는 데 적합합니다.
트리맵: 자연 순서 또는 맞춤 순서로 키를 순회하는 데 적합합니다.

4. 요약
HashMap은 일반적으로 TreeMap보다 약간 빠릅니다(트리 및 해시 테이블의 데이터 구조로 인해). HashMap을 더 많이 사용하고 Map 정렬이 필요한 경우에만 TreeMap을 사용하는 것이 좋습니다. .

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

실행 결과는 다음과 같습니다.
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(키)는 :ccc
tmp.get(키)는 :aaa
tmp.get(키)는 :bbb
tmp.get(키)는 :ccc
tmp .get( key) is :cdc
HashMap의 결과는 정렬되지 않지만 TreeMap의 결과 출력은 정렬됩니다.
이 기사의 주제를 살펴보겠습니다. 먼저 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); 
} 
}

HashMap에서는 get()을 통해 값을 가져와서 put()을 통해 값을 삽입하고, ContainsKey()를 통해 객체가 이미 존재하는지 확인합니다. ArrayList의 작업과 비교할 때 키를 통해 콘텐츠를 인덱싱하는 것 외에 HashMap은 다른 측면에서 크게 다르지 않다는 것을 알 수 있습니다.
앞서 소개한 것처럼 HashMap은 HashCode를 기반으로 합니다. 모든 객체의 상위 클래스인 Object에 HashCode() 메서드가 있지만, equals 메서드와 마찬가지로 모든 상황에 적용할 수 있는 것은 아니므로 다시 작성해야 합니다. .HashCode() 메서드. 예를 들면 다음과 같습니다.

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