HashMap vs. TreeMap vs. Hashtable vs. LinkedHashMap
原文地址：http://www.programcreek.com/2013/03/hashmap-vs-treemap-vs-hashtable-vs-linkedhashmap/
Map 是 Java 中最重要的数据结构之一。 在这篇文章中，我将演示如何使用不同类型的 Map，如 HashMap，TreeMap，HashTable 和 LinkedHashMap。
1. Map 概述
Java SE 中有 4 个常用的 Map 实现-- HashMap，TreeMap，Hashtable 和 LinkedHashMap。 如果我们用一句话描述它们：
- HashMap 被实现为哈希表，并且在键或值上没有进行排序。
- TreeMap 基于红黑树结构实现，按键排序。
- LinkedHashMap 保留插入的顺序
- Hashtable 与 HashMap 相比，它是同步的，它具有同步的开销。
因为如果程序是线程安全的，应该使用 HashMap。
2. HashMap
如果 HashMap 的键是自定义对象，则需要遵循 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 dog"，但是 HashMap 接受了它。 这是没有道理的，因此现在我们很困惑，到底有多少只"white dog" 在里面。
Dog 类应该定义成下面这样：
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";
}
}
现在结果为：
3
red dog - 10
white dog - 20
black dog - 15
原因是 HashMap 不允许两个相同的元素。 默认情况下，如果要使用 Object 类，必须要实现 hashCode() 和 equals() 方法。 对于不同的对象，默认的 hashCode() 方法返回不同的整数，当引用相同的对象时，equals() 方法只返回 true。 如果不太清楚，请查看 the hashCode() and equals() contract 。
点击 most frequently used methods for 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)
由于 TreeMaps 是按键排序的，所以键的对象必须能够相互比较，这就是为什么它必须实现 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 size"。
如果将例子中的 "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（）方法比较键。不同的 size 代表不同的 dog。
4. Hashtable
Java 文档的解释： HashMap 大致相当于 Hashtable，除了它是不同步的，并允许空值，而 Hashtable 则不行。
5. LinkedHashMap
LinkedHashMap 是 HashMap 的子类。 这意味着它继承了 HashMap 的全部功能。 另外，链表还保留了插入顺序。
我们用与 HashMap 相同的代码来测试（LinkedHashMap 替换 HashMap）：
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