• Index

关于作者

使用TreeMap

       ┌───┐
│Map│
└───┘
▲
┌────┴─────┐
│          │
┌───────┐ ┌─────────┐
│HashMap│ │SortedMap│
└───────┘ └─────────┘
▲
│
┌─────────┐
│ TreeMap │
└─────────┘


SortedMap保证遍历时以Key的顺序来进行排序。例如，放入的Key是"apple""pear""orange"，遍历的顺序一定是"apple""orange""pear"，因为String默认按字母排序：

import java.util.*;
----
public class Main {
public static void main(String[] args) {
Map<String, Integer> map = new TreeMap<>();
map.put("orange", 1);
map.put("apple", 2);
map.put("pear", 3);
for (String key : map.keySet()) {
System.out.println(key);
}
// apple, orange, pear
}
}


import java.util.*;
----
public class Main {
public static void main(String[] args) {
Map<Person, Integer> map = new TreeMap<>(new Comparator<Person>() {
public int compare(Person p1, Person p2) {
return p1.name.compareTo(p2.name);
}
});
map.put(new Person("Tom"), 1);
map.put(new Person("Bob"), 2);
map.put(new Person("Lily"), 3);
for (Person key : map.keySet()) {
System.out.println(key);
}
// {Person: Bob}, {Person: Lily}, {Person: Tom}
System.out.println(map.get(new Person("Bob"))); // 2
}
}

class Person {
public String name;
Person(String name) {
this.name = name;
}
public String toString() {
return "{Person: " + name + "}";
}
}


import java.util.*;
----
public class Main {
public static void main(String[] args) {
Map<Student, Integer> map = new TreeMap<>(new Comparator<Student>() {
public int compare(Student p1, Student p2) {
return p1.score > p2.score ? -1 : 1;
}
});
map.put(new Student("Tom", 77), 1);
map.put(new Student("Bob", 66), 2);
map.put(new Student("Lily", 99), 3);
for (Student key : map.keySet()) {
System.out.println(key);
}
System.out.println(map.get(new Student("Bob", 66))); // null?
}
}

class Student {
public String name;
public int score;
Student(String name, int score) {
this.name = name;
this.score = score;
}
public String toString() {
return String.format("{%s: score=%d}", name, score);
}
}


for循环中，我们确实得到了正确的顺序。但是，且慢！根据相同的Key：new Student("Bob", 66)进行查找时，结果为null

public int compare(Student p1, Student p2) {
return p1.score > p2.score ? -1 : 1;
}


p1.scorep2.score不相等的时候，它的返回值是正确的，但是，在p1.scorep2.score相等的时候，它并没有返回0！这就是为什么TreeMap工作不正常的原因：TreeMap在比较两个Key是否相等时，依赖Key的compareTo()方法或者Comparator.compare()方法。在两个Key相等时，必须返回0。因此，修改代码如下：

public int compare(Student p1, Student p2) {
if (p1.score == p2.score) {
return 0;
}
return p1.score > p2.score ? -1 : 1;
}


小结

SortedMap在遍历时严格按照Key的顺序遍历，最常用的实现类是TreeMap