Java Map 对比：HashMap vs. TreeMap vs. Hashtable vs. LinkedHashMap

Bertha 。 2024-03-27 09:17 110阅读 0赞

## Java Map 对比：HashMap vs. TreeMap vs. Hashtable vs. LinkedHashMap ##

*本文译自：[HashMap vs. TreeMap vs. Hashtable vs. LinkedHashMap][]*

Map是Java中最重要的数据结构之一。在这篇文章中，我将说明如何使用不同类型的映射，例如 HashMap、TreeMap、HashTable 和 LinkedHashMap。

### 1 Map 概览 ###

![在这里插入图片描述][5da8817330024831912e9b58ddb23d91.png_pic_center]

Java SE 中有 4 种常用的 Map 实现——HashMap、TreeMap、Hashtable 和 LinkedHashMap。如果我们只用一句话来描述每个实现，那就是：

*  HashMap 实现为 Hashtable，键或值没有排序。
 *  TreeMap是基于红黑树结构实现的，按key排序。
 *  LinkedHashMap 保留插入顺序
 *  Hashtable 是同步的，与 HashMap 不同。它有同步开销。

这就是如果程序是线程安全的，就应该使用HashMap的原因。

### 2 HashMap ###

如果HashMap的key是自定义对象，则需要遵循equals()和hashCode()约定。

class Dog {
        
    	String color;
     
    	Dog(String c) {
        
    		color = c;
    	}
    	public String toString(){
        	
    		return color + " dog";
    	}
    }
     
    public class TestHashMap {
        
    	public static void main(String[] args) {
        
    		HashMap<Dog, Integer> hashMap = new HashMap<Dog, Integer>();
    		Dog d1 = new Dog("red");
    		Dog d2 = new Dog("black");
    		Dog d3 = new Dog("white");
    		Dog d4 = new Dog("white");
     
    		hashMap.put(d1, 10);
    		hashMap.put(d2, 15);
    		hashMap.put(d3, 5);
    		hashMap.put(d4, 20);
     
    		//print size
    		System.out.println(hashMap.size());
     
    		//loop HashMap
    		for (Entry<Dog, Integer> entry : hashMap.entrySet()) {
        
    			System.out.println(entry.getKey().toString() + " - " + entry.getValue());
    		}
    	}
    }

输出：

4
    white dog - 5
    black dog - 15
    red dog - 10
    white dog - 20

注意这里，我们错误地添加了两次“white dogs”，但是 HashMap 接受了它。这没有意义，因为现在我们对那里到底有多少只白Dog感到困惑。

Dog 类应该定义如下：

现在输出是：

3
    red dog - 10
    white dog - 20
    black dog - 15

原因是 HashMap 不允许有两个相同的元素。默认情况下，使用在 Object 类中实现的 hashCode() 和 equals() 方法。默认的 hashCode() 方法为不同的对象提供不同的整数，而 equals() 方法仅在两个引用引用同一对象时才返回 true。如果这对您来说不是很明显，请查看[hashCode() 和 equals() 合同。][hashCode_ _ equals_]

查看[HashMap 最常用的方法][HashMap]，如迭代、打印等。

### 3 TreeMap ###

TreeMap 按键排序。我们先来看下面的例子来理解“按键排序”的思想。

class Dog {
        
    	String color;
     
    	Dog(String c) {
        
    		color = c;
    	}
    	public boolean equals(Object o) {
        
    		return ((Dog) o).color.equals(this.color);
    	}
     
    	public int hashCode() {
        
    		return color.length();
    	}
    	public String toString(){
        	
    		return color + " dog";
    	}
    }
     
    public class TestTreeMap {
        
    	public static void main(String[] args) {
        
    		Dog d1 = new Dog("red");
    		Dog d2 = new Dog("black");
    		Dog d3 = new Dog("white");
    		Dog d4 = new Dog("white");
     
    		TreeMap<Dog, Integer> treeMap = new TreeMap<Dog, Integer>();
    		treeMap.put(d1, 10);
    		treeMap.put(d2, 15);
    		treeMap.put(d3, 5);
    		treeMap.put(d4, 20);
     
    		for (Entry<Dog, Integer> entry : treeMap.entrySet()) {
        
    			System.out.println(entry.getKey() + " - " + entry.getValue());
    		}
    	}
    }

输出：

Exception in thread "main" java.lang.ClassCastException: collection.Dog cannot be cast to java.lang.Comparable
    	at java.util.TreeMap.put(Unknown Source)
    	at collection.TestHashMap.main(TestHashMap.java:35)

由于 TreeMap 是按键排序的，因此键的对象必须能够相互比较，这就是为什么它必须实现 Comparable 接口。例如，您使用 String 作为键，因为 String 实现了 Comparable 接口。

让我们改变Dog，让它具有可比性。

class Dog implements Comparable<Dog>{
        
    	String color;
    	int size;
     
    	Dog(String c, int s) {
        
    		color = c;
    		size = s;
    	}
     
    	public String toString(){
        	
    		return color + " dog";
    	}
     
    	@Override
    	public int compareTo(Dog o) {
        
    		return  o.size - this.size;
    	}
    }
     
    public class TestTreeMap {
        
    	public static void main(String[] args) {
        
    		Dog d1 = new Dog("red", 30);
    		Dog d2 = new Dog("black", 20);
    		Dog d3 = new Dog("white", 10);
    		Dog d4 = new Dog("white", 10);
     
    		TreeMap<Dog, Integer> treeMap = new TreeMap<Dog, Integer>();
    		treeMap.put(d1, 10);
    		treeMap.put(d2, 15);
    		treeMap.put(d3, 5);
    		treeMap.put(d4, 20);
     
    		for (Entry<Dog, Integer> entry : treeMap.entrySet()) {
        
    			System.out.println(entry.getKey() + " - " + entry.getValue());
    		}
    	}
    }

输出：

red dog - 10
    black dog - 15
    white dog - 20

它按键排序，即在本例中为Dog的大小。

如果 “Dog d4 = new Dog(“white”, 10);” 替换为“Dog d4 = new Dog(“white”, 40);”，输出将是：

white dog - 20
    red dog - 10
    black dog - 15
    white dog - 5

原因是 TreeMap 现在使用 compareTo() 方法来比较键。不同的尺寸造就不同的Dog！

### 4 Hashtable ###

来自 Java Doc：  
HashMap 类大致等同于 Hashtable，只是它是非同步的并且允许空值。

### 5 LinkedHashMap ###

LinkedHashMap 是 HashMap 的子类。也就是说它继承了HashMap的特性。此外，LinkedHashMap保留了插入顺序。

让我们使用与 HashMap 相同的代码将 HashMap 替换为 LinkedHashMap。

class Dog {
        
    	String color;
     
    	Dog(String c) {
        
    		color = c;
    	}
     
    	public boolean equals(Object o) {
        
    		return ((Dog) o).color.equals(this.color);
    	}
     
    	public int hashCode() {
        
    		return color.length();
    	}
     
    	public String toString(){
        	
    		return color + " dog";
    	}
    }
     
    public class TestHashMap {
        
    	public static void main(String[] args) {
        
     
    		Dog d1 = new Dog("red");
    		Dog d2 = new Dog("black");
    		Dog d3 = new Dog("white");
    		Dog d4 = new Dog("white");
     
    		LinkedHashMap<Dog, Integer> linkedHashMap = new LinkedHashMap<Dog, Integer>();
    		linkedHashMap.put(d1, 10);
    		linkedHashMap.put(d2, 15);
    		linkedHashMap.put(d3, 5);
    		linkedHashMap.put(d4, 20);
     
    		for (Entry<Dog, Integer> entry : linkedHashMap.entrySet()) {
        
    			System.out.println(entry.getKey() + " - " + entry.getValue());
    		}		
    	}
    }

输出是：

red dog - 10
    black dog - 15
    white dog - 20

不同之处在于，如果我们使用 HashMap，则输出可能如下所示 - 插入顺序不会保留。

red dog - 10
    white dog - 20
    black dog - 15

[HashMap vs. TreeMap vs. Hashtable vs. LinkedHashMap]: https://www.programcreek.com/2013/03/hashmap-vs-treemap-vs-hashtable-vs-linkedhashmap/
[5da8817330024831912e9b58ddb23d91.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/f7d82bc426e04d10b45dde96d6c9cfe8.png
[hashCode_ _ equals_]: https://www.programcreek.com/2011/07/java-equals-and-hashcode-contract/
[HashMap]: https://www.programcreek.com/2013/04/frequently-used-methods-of-java-hashmap/