介绍 TreeMap 集合

在大学的一天，我需要编写代码对同学的姓氏进行升序排序，姓氏是他们个人数据的关键。我在这上面花了很多时间。但如果我当时知道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之所以能够存储空键，是因为它根据哈希值确定它们的去向，而计算哈希值不需要比较。所以所有的空键都有它们的位置。

好了——现在您知道了当您需要按排序顺序存储值时该使用什么，以及如何设置排序规则。