CodeGym /Java 课程 /模块 1 /介绍 TreeMap 集合

介绍 TreeMap 集合

模块 1
第 18 级 , 课程 1
可用

在大学的一天,我需要编写代码对同学的姓氏进行升序排序,姓氏是他们个人数据的关键。我在这上面花了很多时间。但如果我当时知道TreeMap类,我会更快地完成任务。

什么是树图?它是一种类似字典的数据结构,将元素存储为键值对,并按键对它们进行排序。

在哪里以及如何使用它?好吧,用我同学的姓氏来完成同样的作业是很理想的。如果我需要按升序存储值,而不是编写自己的排序算法,我所要做的就是创建一个TreeMap并将值放入其中。

它按升序对IntegerString等类型进行排序。但是,如果您想将自己的自定义类型放入 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");

运行这段代码给我们一个错误:

java.base/java.util.TreeMap.put(TreeMap.java:561) 线程“main”中的异常 java.lang.NullPointerException

问题在于TreeMap类在内部使用compareTo()方法比较值。您当然可以传入一个值,代码将编译。但是在运行时你会得到一个错误,因为该方法将在空值上调用,导致抛出NullPointerException 。

HashMap 和 TreeMap 的比较

与TreeMap不同,HashMap允许您将null存储为键。该结构对所有空键都有一个特定的位置。HashMap之所以能够存储键,是因为它根据哈希值确定它们的去向,而计算哈希值不需要比较。所以所有的键都有它们的位置。

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

评论
TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION