当前位置：极客教程 > Java > Java 集合教程 > Java中的TreeMap

Java中的TreeMap

Java中的TreeMap

Java中的TreeMap用于实现Map接口、NavigableMap接口和AbstractMap类。地图按照其键的自然顺序或在地图创建时提供的比较器进行排序，具体取决于使用哪种构造函数。这证明了按键值对进行排序和存储的有效方法。与任何其他排序映射一样，维护的存储顺序必须与等于一致。Treemap实现没有同步，如果多个线程并发访问映射，并且至少有一个线程在结构上修改了映射，则它必须在外部同步。

Java中的TreeMap是java.util.SortedMap接口的具体实现。它提供了一个按键值排序的有序集合，其中键根据其自然顺序或传递给构造函数的自定义比较器排序。

TreeMap使用Red-Black树来实现，这是一种类型的自平衡二叉搜索树。这为常见的操作（例如添加、删除和检索元素）提供了高效的性能，平均时间复杂度为O(log n)。

下面是如何使用TreeMap类的示例：

import java.util.Map;
import java.util.TreeMap;
 
public class Main {
    public static void main(String[] args) {
        Map<String, Integer> treeMap = new TreeMap<>();
 
        // Adding elements to the tree map
        treeMap.put("A", 1);
        treeMap.put("C", 3);
        treeMap.put("B", 2);
 
        // Getting values from the tree map
        int valueA = treeMap.get("A");
        System.out.println("Value of A: " + valueA);
 
        // Removing elements from the tree map
        treeMap.remove("B");
 
        // Iterating over the elements of the tree map
        for (String key : treeMap.keySet()) {
            System.out.println("Key: " + key + ", Value: " + treeMap.get(key));
        }
    }
}

输出

Value of A: 1
Key: A, Value: 1
Key: C, Value: 3

Java中的TreeMap

TreeMap的特点

Treemap的一些重要特点如下：

  1. 该类是Java集合框架的成员。
  2. 该类实现Map接口，包括NavigableMap，SortedMap，并扩展AbstractMap类。
  3. Java中的TreeMap不允许空键（像Map一样），因此会抛出NullPointerException。但是，可以将多个空值与不同的键相关联。
  4. 此类及其视图中的方法返回的条目对表示它们生成时的映射的快照。它们不支持Entry.setValue方法。

现在让我们向前迈进，讨论SynchronizedTreeMap。 **** TreeMap的实现未同步。这意味着，如果多个线程同时访问树集，并且至少有一个线程修改了集合，则必须在外部同步。这通常是通过使用Collections.synchronizedSortedMap方法来实现的。最好在创建时完成，以防止意外的未同步访问集合。可以这样做：

SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...)); 

Geeks，现在你们一定想知道TreeMap在内部是如何工作的？

在获取keyset和values的TreeMap方法中，返回的是一种快速失败的迭代器。因此，任何并发修改都会抛出ConcurrentModificationException。TreeMap基于红黑树数据结构实现。

树中的每个节点具有：

  • 3个变量( K键 = Key, V值 = Value, 布尔型color = Color )
  • 3个引用( 条目left = Left, 条目right = Right, 条目parent = Parent )

TreeMap中的构造函数

为了创建TreeMap，我们需要创建TreeMap类的一个对象。 TreeMap类包括各种构造函数，允许可能创建TreeMap。以下是此类中可用的构造函数。

  1. TreeMap()
  2. TreeMap(Comparator comp)
  3. TreeMap(Map M)
  4. TreeMap(SortedMap sm)

让我们逐个讨论它们，并实现每个构造函数如下：

构造函数1： TreeMap()

该构造函数用于构建一个将使用其键的自然顺序进行排序的空Treemap。

示例

// Java程序演示TreeMap
// 使用默认构造函数
 
// 导入所需的类
import java.util.*;
import java.util.concurrent.*;
 
// 主类
// TreeMapImplementation
public class GFG {
 
    // 方法1
    // 显示TreeMap构造函数
    static void Example1stConstructor()
    {
        // 创建一个空的TreeMap
        TreeMap tree_map
            = new TreeMap();
 
        // 将字符串值映射到int键
        // 使用put()方法
        tree_map.put(10, "Geeks");
        tree_map.put(15, "4");
        tree_map.put(20, "Geeks");
        tree_map.put(25, "Welcomes");
        tree_map.put(30, "You");
 
        // 打印TreeMap的元素
        System.out.println("TreeMap: " + tree_map);
    }
 
    // 方法2
    // 主驱动程序方法
    public static void main(String[] args)
    {
        System.out.println("TreeMap使用TreeMap()构造函数：\n");
 
        // 调用构造函数
        Example1stConstructor();
    }
}

输出

TreeMap使用TreeMap()构造函数：

TreeMap: {10=Geeks, 15=4, 20=Geeks, 25=Welcomes, 30=You}

构造函数2： TreeMap(Comparator comp)

该构造函数用于构建一个空的TreeMap对象，其中的元素需要外部指定排序顺序。

示例

// Java程序演示TreeMap
// 使用比较器构造函数
 
// 引入所需的类
import java.util.*;
import java.util.concurrent.*;
 
// Class 1
// 表示学生的帮助类
class Student {
 
    // 学生的属性
    int rollno;
    String name, address;
 
    // 构造方法
    public Student(int rollno, String name, String address)
    {
 
        // this关键字是指当前对象本身
        this.rollno = rollno;
        this.name = name;
        this.address = address;
    }
 
    // 这个类的方法，打印学生详细信息
    public String toString()
    {
        return this.rollno + " " + this.name + " "
            + this.address;
    }
}
 
// Class 2
// 帮助类 - 比较器实现
class Sortbyroll implements Comparator<Student> {
 
    // 用于按升序排序的方法
    // 根据编号
    public int compare(Student a, Student b)
    {
        return a.rollno - b.rollno;
    }
}
 
// Class 3
// 主类
public class GFG {
 
    // 在main()中调用构造函数
    static void Example2ndConstructor()
    {
        // 创建空的TreeMap
        TreeMap<Student, Integer> tree_map
            = new TreeMap<Student, Integer>(
                new Sortbyroll());
 
        // 映射字符串值到整数键
        tree_map.put(new Student(111, "bbbb", "london"), 2);
        tree_map.put(new Student(131, "aaaa", "nyc"), 3);
        tree_map.put(new Student(121, "cccc", "jaipur"), 1);
 
        // 打印TreeMap的元素
        System.out.println("TreeMap: " + tree_map);
    }
 
    // 主驱动程序方法
    public static void main(String[] args)
    {
 
        System.out.println("使用TreeMap(Comparator)"
                           + "构造函数的TreeMap：\n");
        Example2ndConstructor();
    }
}

输出

使用TreeMap(Comparator)构造函数的TreeMap：

TreeMap: {111 bbbb london=2, 121 cccc jaipur=1, 131 aaaa nyc=3}

构造函数3： TreeMap(Map M)

此构造函数用于使用键的自然顺序初始化给定映射M中的条目的TreeMap。

示例

// Java程序演示TreeMap
// 使用默认构造函数
 
// 引入所需的类
import java.util.*;
import java.util.concurrent.*;
 
// 主类
public class TreeMapImplementation {
 
    // 方法1
    // 演示构造方法<Map>
    static void Example3rdConstructor()
    {
        // 创建一个空的HashMap
        Map<Integer, String> hash_map
            = new HashMap<Integer, String>();
 
        // 使用put()方法将字符串值映射到整数键
        hash_map.put(10, "Geeks");
        hash_map.put(15, "4");
        hash_map.put(20, "Geeks");
        hash_map.put(25, "Welcomes");
        hash_map.put(30, "You");
 
        // 使用Map创建TreeMap
        TreeMap<Integer, String> tree_map
            = new TreeMap<Integer, String>(hash_map);
 
        // 打印TreeMap的元素
        System.out.println("TreeMap: " + tree_map);
    }
 
    // 方法2
    // 主驱动程序方法
    public static void main(String[] args)
    {
 
        System.out.println("使用TreeMap(Map)构造函数的TreeMap：\n");
 
        Example3rdConstructor();
    }
}

输出 使用TreeMap(Map)构造函数的TreeMap： TreeMap: {10=Geeks, 15=4, 20=Geeks, 25=Welcomes, 30=You}
“`

构造函数4： TreeMap(SortedMap sm)

该构造函数用于使用给定的排序映射表中的条目初始化TreeMap，这些条目将按照给定的排序映射表相同的顺序存储。

示例

// Java程序演示TreeMap
// 使用SortedMap构造函数
 
// 导入所需的类
import java.util.*;
import java.util.concurrent.*;
 
// 主类
// TreeMapImplementation
public class GFG {
 
    // 方法
    // 演示TreeMap(SortedMap)构造函数
    static void Example4thConstructor()
    {
        // 创建一个SortedMap
        SortedMap<Integer, String> sorted_map
            = new ConcurrentSkipListMap<Integer, String>();
 
        // 使用put()方法将字符串值映射到整数键
        sorted_map.put(10, "Geeks");
        sorted_map.put(15, "4");
        sorted_map.put(20, "Geeks");
        sorted_map.put(25, "Welcomes");
        sorted_map.put(30, "You");
 
        // 使用SortedMap创建TreeMap
        TreeMap<Integer, String> tree_map
            = new TreeMap<Integer, String>(sorted_map);
 
        // 打印TreeMap的元素
        System.out.println("TreeMap: " + tree_map);
    }
 
    // 方法2
    // 主驱动程序方法
    public static void main(String[] args)
    {
 
        System.out.println("使用TreeMap(SortedMap)构造函数的TreeMap：\n");
 
        Example4thConstructor();
    }
}

输出

使用TreeMap(SortedMap)构造函数的TreeMap：

TreeMap：{10=Geeks，15=4，20=Geeks，25=Welcomes，30=You}

TreeMap类中的方法

方法 执行操作
clear() 该方法从该TreeMap中移除所有映射并清除映射。
clone() 该方法返回此TreeMap的浅拷贝。
containsKey(Object key) 如果该映射包含指定键的映射，则返回true。
containsValue(Object value) 如果该映射将一个或多个键映射到指定值，则返回true。
entrySet() 返回包含在此映射中的映射的Set视图。
firstKey() 返回当前排序映射中的第一个(最低)键。
get(Object key) 返回此映射将指定键映射到的值。
headMap(Object key_value) 该方法返回严格小于参数key_value的map部分的视图。
keySet() 该方法返回treemap中包含的键的Set视图。
lastKey() 返回当前排序映射中的最后一个(最高)键。
put(Object key, Object value) 该方法用于插入一个映射到一个映射中。
putAll(Map map) 将指定映射中的所有映射复制到此映射中。
remove(Object key) 如果存在，则从该TreeMap中删除此键的映射。
size() 返回此映射中键值映射的数量。
subMap((K startKey, K endKey) 该方法返回键范围从startKey(包括)到endKey(不包括)的此映射的部分。
values() 返回此映射中包含的值的Collection视图。

实现: 下面的程序将更好地演示如何创建、插入和遍历TreeMap。

说明:

// Java程序，展示TreeMap的操作，如创建、插入、搜索和遍历
 
//导入所需的类
import java.util.*;
import java.util.concurrent.*;
 
//主类
//TreeMap的实现
public class GFG {
 
    //声明TreeMap
    static TreeMap<Integer, String> tree_map;
 
    //方法1——创建TreeMap
    static void create()
    {
 
        //创建一个空的TreeMap
        tree_map = new TreeMap<Integer, String>();
 
        //仅显示信息
        System.out.println("创建TreeMap成功");
    }
 
    //方法2——向TreeMap插入值
    static void insert()
    {
 
        //使用put()方法，将字符串值映射到整数键
        tree_map.put(10, "Geeks");
        tree_map.put(15, "4");
        tree_map.put(20, "Geeks");
        tree_map.put(25, "Welcomes");
        tree_map.put(30, "You");
 
        //仅显示信息
        System.out.println("\n成功插入元素到TreeMap中");
    }
 
    //方法3——在TreeMap中搜索键
    static void search(int key)
    {
 
        //检查键是否存在
        System.out.println("\n键 \"" + key
                           + "\" 是否存在？"
                           + tree_map.containsKey(key));
    }
 
    //方法4——在TreeMap中搜索值
    static void search(String value)
    {
 
        //检查值是否存在
        System.out.println("\n值 \"" + value
                           + "\" 是否存在？"
                           + tree_map.containsValue(value));
    }
 
    //方法5——显示TreeMap的元素
    static void display()
    {
 
        //显示TreeMap
        System.out.println("\n显示TreeMap:");
 
        System.out.println("TreeMap: " + tree_map);
    }
 
    //方法6——遍历TreeMap
    static void traverse()
    {
 
        //仅显示信息
        System.out.println("\n遍历TreeMap:");
 
        for (Map.Entry<Integer, String> e :
             tree_map.entrySet())
            System.out.println(e.getKey() + " "
                               + e.getValue());
    }
 
    //方法6——主方法
    public static void main(String[] args)
    {
 
        //在主函数中调用自定义方法
 
        //创建TreeMap
        create();
 
        //向TreeMap中插入值
        insert();
 
        //在TreeMap中搜索键值为"50"的元素
        search(50);
 
        //在TreeMap中搜索值为"Geeks"的元素
        search("Geeks");
 
        //显示TreeMap的元素
        display();
 
        //遍历TreeMap
        traverse();
    }
}

输出

创建TreeMap成功

成功插入元素到TreeMap中

键 "50" 是否存在？false

值 "Geeks" 是否存在？true

显示TreeMap:
TreeMap: {10=Geeks, 15=4, 20=Geeks, 25=Welcomes, 30=You}

遍历TreeMap:
10 Geeks
15 4
20 Geeks
25 Welcomes
30 You

在TreeMap上执行各种操作

在Java 1.5引入泛型之后，可以限制存储在TreeMap中的对象类型。现在，让我们看一下如何在TreeMap上执行一些常用操作。

操作1： 添加元素

要向TreeMap中添加元素，可以使用put()方法。但是，TreeMap并不保留插入顺序。内部，在每个元素中，键会被比较并按升序排序。

示例

// Java程序演示了使用put()方法在TreeMap中添加元素

//导入所需类
import java.util.*;

//主类
class GFG {

//主驱动程序
public static void main(String args[])
{
//默认初始化一个TreeMap
TreeMap tm1 = new TreeMap();

//使用put()方法在TreeMap中插入元素
tm1.put(3, "Geeks");
tm1.put(2, "For");
tm1.put(1, "Geeks");

//使用泛型初始化一个TreeMap
TreeMap<Integer, String> tm2
= new TreeMap<Integer, String>();

//再次使用put()方法在TreeMap中插入元素
tm2.put(new Integer(3), "Geeks");
tm2.put(new Integer(2), "For");
tm2.put(new Integer(1), "Geeks");

//打印两个TreeMap的元素

//Map 1
System.out.println(tm1);
//Map 2
System.out.println(tm2);
}
}

输出

{1=Geeks, 2=For, 3=Geeks}
{1=Geeks, 2=For, 3=Geeks}

操作2:修改元素

在添加元素后，如果我们希望更改元素，可以再次使用put()方法添加元素。由于Treemap中的元素是使用键索引的，因此可以通过为我们希望更改的键插入已更新的值来更改键的值。

示例

// Java程序演示了使用put()方法在TreeMap中更新元素

//导入所需类
import java.util.*;

//主类
class GFG {

//主驱动程序
public static void main(String args[])
{
//使用泛型初始化一个TreeMap
TreeMap<Integer, String> tm
= new TreeMap<Integer, String>();

//使用put()方法在Map中插入元素
tm.put(3, "Geeks");
tm.put(2, "Geeks");
tm.put(1, "Geeks");

//打印Map中的所有元素
System.out.println(tm);

//在对应于指定键的位置插入元素
tm.put(2, "For");

//打印更新后的Map中的元素
System.out.println(tm);
}
}

输出

{1=Geeks, 2=Geeks, 3=Geeks}
{1=Geeks, 2=For, 3=Geeks}

操作3:删除元素

为了从TreeMap中删除元素，我们可以使用remove()方法。此方法接受键值并从该treemap中删除该键的映射，如果它存在于映射中。

示例

// Java程序演示了使用remove()方法从TreeMap中删除元素

//导入所需类
import java.util.*;

//主类
class GFG {

//主驱动程序
public static void main(String args[])
{
//使用泛型初始化一个TreeMap
TreeMap<Integer, String> tm
= new TreeMap<Integer, String>();

//使用put()方法插入元素
tm.put(3, "Geeks");
tm.put(2, "Geeks");
tm.put(1, "Geeks");
tm.put(4, "For");

//打印Map的所有元素
System.out.println(tm);

//删除与键对应的元素
tm.remove(4);

//打印更新后的Treemap
System.out.println(tm);
}
}

输出

{1=Geeks, 2=Geeks, 3=Geeks, 4=For}
{1=Geeks, 2=Geeks, 3=Geeks}

操作4： 遍历 TreeMap

可以通过多种方式遍历 Map，其中最常用的方式是使用 for-each 循环并获取键。使用 getValue() 方法 可以找到键的值。

例

// Java Program to Illustrate Iterating over TreeMap
// using
 
// Importing required classes
import java.util.*;
 
// Main class
class GFG {
 
    // Main driver method
    public static void main(String args[])
    {
        // Initialization of a TreeMap
        // using Generics
        TreeMap<Integer, String> tm
            = new TreeMap<Integer, String>();
 
        // Inserting the elements
        // using put() method
        tm.put(3, "Geeks");
        tm.put(2, "For");
        tm.put(1, "Geeks");
 
        // For-each loop for traversal over Map
        // via entrySet() Method
        for (Map.Entry mapElement : tm.entrySet()) {
 
            int key = (int)mapElement.getKey();
 
            // Finding the value
            String value = (String)mapElement.getValue();
 
            // Printing the key and value
            System.out.println(key + " : " + value);
        }
    }
}

输出

1 : Geeks
2 : For
3 : Geeks

TreeMap 的优点：

  1. 有序：TreeMap 根据其键的自然顺序或传递给构造函数的自定义比较器提供其元素的有序顺序。这使得在需要按特定顺序检索元素的情况下非常有用。
  2. 可预测的迭代顺序：因为 TreeMap 中的元素按排序顺序存储，所以您可以预测它们在迭代期间返回的顺序，这使得编写按特定顺序处理元素的算法变得更加容易。
  3. 搜索性能：TreeMap 提供了 Map 接口的高效实现，允许您以对数时间检索元素，这使得在需要快速检索元素的搜索算法中非常有用。
  4. 自平衡：TreeMap 使用红黑树实现，这是一种自平衡二叉查找树类型。这提供了对添加、删除和检索元素的高效性能，以及对元素的有序维护。

TreeMap 的缺点：

  1. 插入元素时速度慢：插入元素到 TreeMap 中可能比插入元素到常规 Map 中慢，因为 TreeMap 需要维护其元素的有序顺序。
  2. 键的限制：TreeMap 中的键必须实现 java.lang.Comparable 接口，或者必须提供自定义比较器。如果需要使用不实现此接口的自定义键，则可能受到限制。

Python教程

Python 教程

Python 教程
Tkinter 教程

Tkinter 教程
Pandas 教程

Pandas 教程
NumPy 教程

NumPy 教程
Flask 教程

Flask 教程
Django 教程

Django 教程
PySpark 教程

PySpark 教程
wxPython 教程

wxPython 教程
SymPy 教程

SymPy 教程
Seaborn 教程

Seaborn 教程
SciPy 教程

SciPy 教程
RxPY 教程

RxPY 教程
Pycharm 教程

Pycharm 教程
Pygame 教程

Pygame 教程
PyGTK 教程

PyGTK 教程
PyQt 教程

PyQt 教程
PyQt5 教程

PyQt5 教程
PyTorch 教程

PyTorch 教程
Matplotlib 教程

Matplotlib 教程
Web2py 教程

Web2py 教程
BeautifulSoup 教程

BeautifulSoup 教程

Java教程

Java 教程

Java 教程

Web教程

HTML 教程

HTML 教程
CSS 教程

CSS 教程
CSS3 教程

CSS3 教程
jQuery 教程

jQuery 教程
Ajax 教程

Ajax 教程
AngularJS 教程

AngularJS 教程
TypeScript 教程

TypeScript 教程
WordPress 教程

WordPress 教程
Laravel 教程

Laravel 教程
Next.js 教程

Next.js 教程
PhantomJS 教程

PhantomJS 教程
Three.js 教程

Three.js 教程
Underscore.JS 教程

Underscore.JS 教程
WebGL 教程

WebGL 教程
WebRTC 教程

WebRTC 教程
VueJS 教程

VueJS 教程

数据库教程

SQL 教程

SQL 教程
MySQL 教程

MySQL 教程
MongoDB 教程

MongoDB 教程
PostgreSQL 教程

PostgreSQL 教程
SQLite 教程

SQLite 教程
Redis 教程

Redis 教程
MariaDB 教程

MariaDB 教程

图形图像教程

Vulkan 教程

Vulkan 教程
OpenCV 教程

OpenCV 教程

大数据教程

R语言 教程

R语言 教程

开发工具教程

Git 教程

Git 教程
VSCode 教程

VSCode 教程
Docker 教程

Docker 教程
Gerrit 教程

Gerrit 教程
Excel 教程

Excel 教程

计算机教程

Go语言 教程

Go语言 教程
C++ 教程

C++ 教程

Java 精品教程