在大学的一天,我需要编写代码对同学的姓氏进行升序排序,姓氏是他们个人数据的关键。我在这上面花了很多时间。但如果我当时知道TreeMap类,我会更快地完成任务。
什么是树图?它是一种类似字典的数据结构,将元素存储为键值对,并按键对它们进行排序。
在哪里以及如何使用它?好吧,用我同学的姓氏来完成同样的作业是很理想的。如果我需要按升序存储值,而不是编写自己的排序算法,我所要做的就是创建一个TreeMap并将值放入其中。
它按升序对Integer和String等类型进行排序。但是,如果您想将自己的自定义类型放入 TreeMap 中,则您的类需要实现Comparable接口,以便它实现compareTo()方法,该方法指示如何对您的类的实例进行排序。
public class Person implements Comparable<Person> {
private String firstName;
private String lastName;
public Person(String firstName, String lastName) {
this.firstName = firstName;
this.lastName = lastName;
}
public String getFirstName() {
return firstName;
}
public void setFirstName(String firstName) {
this.firstName = firstName;
}
…
@Override
public int compareTo(Person person) {
return person.getFirstName().compareTo(firstName);
}
@Override
public String toString() {
return "Person{" +
"firstName='" + firstName + '\'' +
", lastName='" + lastName + '\'' +
'}';
}
}
让我们覆盖compareTo()方法,以便它按名字的逆字母顺序对值进行排序:
TreeMap map = new TreeMap<Person, String>();
map.put(new Person("AA","BB"), "aa");
map.put(new Person("BB","BB"), "aa");
map.put(new Person("DD","BB"), "aa");
map.put(new Person("CC","BB"), "aa");
这些值将按以下顺序存储:
Person{firstName='DD', lastName='BB'}
Person{firstName='CC', lastName='BB'}
Person{firstName='BB', lastName='BB'}
Person{firstName='AA', lastName='BB'}
TreeMap类实现了NavigableMap接口,后者又扩展了SortedMap接口。这让TreeMap类使用树来按排序顺序存储值。
正如维基百科所说,树是一种自平衡的二进制搜索结构,它在首先比较值后将数据存储在其节点中。 |
简单来说,红黑树是一种数据结构,如果值大于根,则将值存储在右子树中,如果值小于根,则存储在左子树中。此实现可以非常快速地查找结构中的值。
红黑树是自平衡的,因此它会随着每个新值的插入而改变其结构。首先添加的值最初被认为是根,但在平衡过程中另一个值可以成为根。
好了,现在您知道什么是TreeMap及其工作原理了。
请记住,TreeMap只能存储其类实现Comparable接口并重写compareTo()方法的对象。
但是,如果我们使用从各种库加载的第三方类并且无法在其中实现Comparable怎么办?有一个解决方案:编写自己的Comparator。
Comparator是一个具有 compare() 方法的接口。我们可以用它来比较对象并将它们存储在TreeMap中。
Comparator<Person> comparator = new Comparator<Person>() {
@Override
public int compare(Person person1, Person person2) {
return person1.getFirstName().compareTo(person2.getFirstName());
}
};
TreeMap map = new TreeMap<Person, String>(comparator);
在此示例中,我们创建了一个自定义Comparator并将TreeMap传递给该类。
从 Java 8 开始,我们可以使用 lambda 表达式来编写:
TreeMap map = new TreeMap<Person, String>((Person person1, Person person2) -> person1.getFirstName().compareTo(person2.getFirstName()));
换句话说,为了将值存储在TreeMap中,您需要指定如何对它们进行排序。有两种方法可以做到这一点:实施Comparable或实施您自己的Comparator。
但是,如果我们需要将null作为键放入TreeMap中怎么办?HashMap可以让你做到这一点。是的,但是TreeMap如何处理这个问题?
TreeMap map = new TreeMap<Person, String>();
map.put (null, "Person");
运行这段代码给我们一个错误:
问题在于TreeMap类在内部使用compareTo()方法比较值。您当然可以传入一个空值,代码将编译。但是在运行时你会得到一个错误,因为该方法将在空值上调用,导致抛出NullPointerException 。
HashMap 和 TreeMap 的比较
与TreeMap不同,HashMap允许您将null存储为键。该结构对所有空键都有一个特定的位置。HashMap之所以能够存储空键,是因为它根据哈希值确定它们的去向,而计算哈希值不需要比较。所以所有的空键都有它们的位置。
好了——现在您知道了当您需要按排序顺序存储值时该使用什么,以及如何设置排序规则。
GO TO FULL VERSION