Java 中的TreeMap

Java 中的`TreeMap`

原文：https://www.studytonight.com/java-examples/treemap-in-java

TreeMap类实现了映射接口，并且是 Java 集合接口的一部分。与其他映射实现不同，TreeMap以排序顺序存储键值对。

在本教程中，我们将了解更多关于 TreeMap 的排序功能。

`TreeMap`中的自然排序

默认情况下，TreeMap存储按关键字排序的条目。按键通过使用它们的自然排序来排序。例如，整数的自然顺序是升序。同样，字符串的自然顺序是字母顺序。

让我们创建一个存储整数-字符串对的TreeMap。当我们打印映射时，输出按排序顺序显示。

import java.util.Map.Entry;
import java.util.TreeMap;

public class TreeMapDemo
{
    public static void main(String[] args)
    {
        TreeMap<Integer, String> map = new TreeMap<>();
        map.put(4, "Harry");
        map.put(3, "Simon");
        map.put(2, "Jessica");
        map.put(5, "Victor");
        map.put(1, "Justin");

        //Printing the TreeMap
        for(Entry<Integer, String> e : map.entrySet())
            System.out.println(e.getKey() + "-->" + e.getValue());
    }
}

【Justin】【2】>【Jessica】【3】>【Simon】【4】>【Harry】【5】>victor

让我们使用字符串作为键并查看输出。

import java.util.Map.Entry;
import java.util.TreeMap;

public class TreeMapDemo
{
    public static void main(String[] args)
    {
        TreeMap<String, Integer> map = new TreeMap<>();
        map.put("Harry", 4);
        map.put("Jessica", 2);
        map.put("Victor", 5);
        map.put("Simon", 3);
        map.put("Justin", 1);

        //Printing the TreeMap
        for(Entry<String, Integer> e : map.entrySet())
            System.out.println(e.getKey() + "-->" + e.getValue());
    }
}

【哈利】>【4】【杰西卡】>【2】【贾斯汀】>【1】【西蒙】>【3】【维克多】> 5

Comparable接口用于设置自定义类的自然顺序。让我们创建一个实现Comparable接口的学生类。我们需要按学生的姓名(字母顺序)对他们进行排序。TreeMap 将自动使用 compareTo()方法中定义的自然顺序对数据进行排序和存储。

import java.util.Map.Entry;
import java.util.TreeMap;

class Student implements Comparable
{
    String name;
    Double gpa;

    Student(String s, Double d)
    {
        this.name = s;
        this.gpa = d;
    }

    //Defining the natural ordering for Students
    @Override
    public int compareTo(Object o)
    {
        return this.name.compareTo(( (Student) o).name);
    }
}
public class TreeMapDemo
{
    public static void main(String[] args)
    {
        TreeMap<Student, String> map = new TreeMap<>() ;
        map.put((new Student("Harry", 4.0)), "Harry");
        map.put((new Student("Jessica", 2.8)), "Jessica");
        map.put((new Student("Victor", 3.9)), "Victor");
        map.put((new Student("Simon", 4.4)), "Simon");
        map.put((new Student("Justin",3.01)), "Justin");

        //Printing the TreeMap
        for(Entry<Student, String> e : map.entrySet())
            System.out.println(e.getKey().gpa + "-->" + e.getValue());
    }
}

4.0 - >哈利【2.8】>【Jessica】【3.01】>【Justin】【4.4】>【Simon】【3.9】>victor

定义不同的排序顺序

在某些情况下，自然排序可能并不理想。TreeMap构造器可以用一个Comparator作为参数。我们可以使用这个Comparator来定义排序关键字的不同顺序。

例如，如果我们想以降序存储密钥，我们可以使用逆序Comparator。

import java.util.Comparator;
import java.util.Map.Entry;
import java.util.TreeMap;

public class TreeMapDemo
{
    public static void main(String[] args)
    {
        //Passing reverse order Comparator
        TreeMap<String, Integer> map = new TreeMap<>(Comparator.reverseOrder());
        map.put("Harry", 4);
        map.put("Jessica", 2);
        map.put("Victor", 5);
        map.put("Simon", 3);
        map.put("Justin", 1);

        //Printing the TreeMap
        for(Entry<String, Integer> e : map.entrySet())
            System.out.println(e.getKey() + "-->" + e.getValue());
    }
}

> 【西蒙】>【3】【贾斯汀】> 【杰西卡】>【2】【哈利】> 4

让我们尝试创建一个自定义的Comparator来处理前面定义的学生类。我们将根据学生的平均成绩对他们进行排序，而不是按他们的名字进行排序。在TreeMap中，绩点较高的学生应该是第一名。

import java.util.Comparator;
import java.util.Map.Entry;
import java.util.TreeMap;

class Student
{
    String name;
    Double gpa;

    Student(String s, Double d)
    {
        this.name = s;
        this.gpa = d;
    }
}
public class TreeMapDemo
{
    public static void main(String[] args)
    {
        //Comparator to sort by descending order of GPA
        Comparator<Student> c = (Student s1, Student s2) -> (-s1.gpa.compareTo(s2.gpa));        
        TreeMap<Student, String> map = new TreeMap<>(c) ;
        map.put((new Student("Harry", 4.0)), "Harry");
        map.put((new Student("Jessica", 2.8)), "Jessica");
        map.put((new Student("Victor", 3.9)), "Victor");
        map.put((new Student("Simon", 4.4)), "Simon");
        map.put((new Student("Justin",3.01)), "Justin");

        //Printing the TreeMap
        for(Entry<Student, String> e : map.entrySet())
            System.out.println(e.getKey().gpa + "-->" + e.getValue());
    }
}

4.4 - >西蒙【4.0】>【哈利】【3.9】>【victor】【3.01】>【Justin】【2.8】>Jessica

`TreeMap`是如何在 Java 中实现的？

TreeMap 实现了 NavigableMap 接口。它使用名为红黑树的高级数据结构来存储和排序键值对。
红黑树和普通的二分搜索法树非常相似。就像二叉查找树一样，红黑树将包含一个根，一个左子树和一个右子树。左子树的所有节点都应该小于该节点，右树的所有节点都应该大于该节点。
对于所有其他节点，该属性应该为真。物体的自然顺序决定了物体的大小。
与普通的 BST 不同，红黑树是自动平衡的。这确保了没有一半的树变得比另一半更深。
简而言之，对于树上的基本操作，这个属性给出了 O(logN)的时间复杂度。另一方面，BST 可以给出 O(N)的最坏情况时间复杂度。

常见的`TreeMap`方法

TreeMap 类提供了额外的方法来利用键的排序顺序。让我们来看看 TreeMap 类的一些重要方法。

firstKey() 方法用于从TreeMap中获取第一个或最小的键。
同样，使用 lastKey() 方法从映射中获取最大的关键点。
头标()方法以一个按键作为输入。它返回一个包含小于传递的键的键-值对的映射。
类似地， tailMap() 方法获取一个键，并返回一个包含所有大于等于传递的键的键值对的映射。

import java.util.Map.Entry;
import java.util.Set;
import java.util.TreeMap;

public class TreeMapDemo
{
    public static void main(String[] args)
    {
        TreeMap<String, Integer> map = new TreeMap<>();
        map.put("Harry", 4);
        map.put("Jessica", 2);
        map.put("Victor", 5);
        map.put("Simon", 3);
        map.put("Justin", 1);
        System.out.println("The TreeMap is: ");
        for(Entry<String, Integer> e : map.entrySet())
            System.out.println(e.getKey() + "-->" + e.getValue());

        String smallestKey = map.firstKey();
        String largestKey = map.lastKey();
        Set<String> keysSmallerThanVictor = map.headMap("Victor").keySet();//Excludes Victor
        Set<String> keysGreaterThanJustin = map.tailMap("Justin").keySet();//Includes Justin

        System.out.println("\nSmallest Key: " + smallestKey);
        System.out.println("Largest Key: " + largestKey);
        System.out.println("Keys Smaller than Victor: " + keysSmallerThanVictor);
        System.out.println("Keys Greater than Justin: " + keysGreaterThanJustin);
    }
}

TreeMap为: 哈利- > 4 杰西卡- > 2 贾斯汀- > 1 西蒙- > 3 维克多->5 T7】最小的钥匙:哈利最大的钥匙:维克多比维克多小的钥匙:【哈利、杰西卡、贾斯汀、西蒙】比贾斯汀大的钥匙:【贾斯汀、西蒙、维克多】

什么时候使用 TreeMap？

HashMap 没有保持插入的顺序，更多地被用作通用映射。存储和获取数据非常高效和快速。
LinkedHashMap 也非常快，并且还保持了插入的顺序。
当我们想要以排序顺序存储键值对时，TreeMap比 HashMap 和 LinkedHashMap 更受欢迎。我们可以完全控制数据在TreeMap中的存储顺序。
然而，排序会对TreeMap的整体性能造成影响。
这一切都归结为我们正在努力完成的任务。如果性能至关重要，那么更喜欢 HashMap 或 LinkedHashMap。如果数据必须按排序顺序存储，那么 TreeMap 应该是首选。

摘要

TreeMap 是一个重要的 Java 集合。TreeMap使用红黑树。这将确保元素的插入、删除和搜索花费对数时间。但是它的性能不如 HashMap 或者 LinkedHashMap。TreeMap 类为键值对的排序提供了很大的灵活性。我们可以使用键的自然顺序，也可以使用Comparator定义自己的顺序。在本教程中，我们讨论了 TreeMap 类的基础知识以及如何有效地使用它。

TreeMap中的自然排序

定义不同的排序顺序

TreeMap是如何在 Java 中实现的？

常见的TreeMap方法

什么时候使用 TreeMap？

摘要