Java如何使用TreeMap？解析和用法示例

2021年3月28日14:00:54 发表评论 1,202 次浏览

Java中的TreeMap用于实现Map接口和NavigableMap以及AbstractMap类。该Map是根据其键的自然顺序或按比较器在Map创建时提供, 取决于所使用的构造函数。事实证明, 这是排序和存储键值对的有效方法。不论显式比较器如何, 树图所维护的存储顺序都必须与equals保持一致, 就像任何其他排序图一样。树形图实现在某种意义上是不同步的, 即如果一个图被多个线程同时访问, 并且至少一个线程在结构上修改了该图, 则它必须在外部进行同步。

Java中的Map和Treemap

例子：以下实现演示如何创建, 插入和遍历TreeMap.

// Java code to show creation, insertion, // searching, and traversal in a TreeMap
  
import java.util.*;
import java.util.concurrent.*;
  
public class TreeMapImplementation {
  
     // Declaring a TreeMap
     static TreeMap<Integer, String> tree_map;
  
     // Function to create TreeMap
     static void create()
     {
         // Creating an empty TreeMap
         tree_map
             = new TreeMap<Integer, String>();
  
         System.out.println(
             "TreeMap successfully"
             + " created" );
     }
  
     // Function to Insert values in
     // the TreeMap
     static void insert()
     {
         // Mapping string values to int keys
         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(
             "\nElements successfully"
             + " inserted in the TreeMap" );
     }
  
     // Function to search a key in TreeMap
     static void search( int key)
     {
  
         // Checking for the key
         System.out.println(
             "\nIs key \""
             + key + "\" present? "
             + tree_map.containsKey(key));
     }
  
     // Function to search a value in TreeMap
     static void search(String value)
     {
  
         // Checking for the value
         System.out.println(
             "\nIs value \""
             + value + "\" present? "
             + tree_map.containsValue(value));
     }
  
     // Function to display the elements in TreeMap
     static void display()
     {
         // Displaying the TreeMap
         System.out.println(
             "\nDisplaying the TreeMap:" );
  
         System.out.println(
             "TreeMap: " + tree_map);
     }
  
     // Function to traverse TreeMap
     static void traverse()
     {
         System.out.println( "\nTraversing the TreeMap:" );
         for (Map.Entry<Integer, String> e : tree_map.entrySet())
             System.out.println(e.getKey()
                                + " "
                                + e.getValue());
     }
  
     // Driver code
     public static void main(String[] args)
     {
  
         // Creating the TreeMap
         create();
  
         // Inserting values in the TreeMap
         insert();
  
         // Search key "50" in the TreeMap
         search( 50 );
  
         // Search value "Geeks" in the TreeMap
         search( "Geeks" );
  
         // Display the elements in TreeMap
         display();
  
         // Traverse the TreeMap
         traverse();
     }
}

输出如下：

TreeMap successfully created
Elements successfully inserted in the TreeMap
Is key "50" present? false
Is value "Geeks" present? true
Displaying the TreeMap:
TreeMap: {10=Geeks, 15=4, 20=Geeks, 25=Welcomes, 30=You}
Traversing the TreeMap:
10 Geeks
15 4
20 Geeks
25 Welcomes
30 You

在TreeMap上执行各种操作

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

1.添加元素：为了将元素添加到TreeMap, 我们可以使用put()方法。但是, 插入顺序不会保留在TreeMap中。在内部, 对于每个元素, 键均按升序进行比较和排序。

// Java program to demonstrate
// the working of TreeMap
  
import java.util.*;
class GFG {
     public static void main(String args[])
     {
         // Default Initialization of a
         // TreeMap
         TreeMap tm1 = new TreeMap();
  
         // Initialization of a TreeMap
         // using Generics
         TreeMap<Integer, String> tm2
             = new TreeMap<Integer, String>();
  
         // Inserting the Elements
         tm1.put( 3 , "Geeks" );
         tm1.put( 2 , "For" );
         tm1.put( 1 , "Geeks" );
  
         tm2.put( new Integer( 3 ), "Geeks" );
         tm2.put( new Integer( 2 ), "For" );
         tm2.put( new Integer( 1 ), "Geeks" );
  
         System.out.println(tm1);
         System.out.println(tm2);
     }
}

输出如下：

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

2.改变要素：添加元素后, 如果我们希望更改元素, 可以通过再次添加带有put()方法。由于树形图中的元素是使用键索引的, 因此可以通过简单地为我们希望更改的键插入更新后的值来更改键的值。

// Java program to demonstrate
// the working of TreeMap
  
import java.util.*;
class GFG {
     public static void main(String args[])
     {
         // Initialization of a TreeMap
         // using Generics
         TreeMap<Integer, String> tm
             = new TreeMap<Integer, String>();
  
         // Inserting the Elements
         tm.put( 3 , "Geeks" );
         tm.put( 2 , "Geeks" );
         tm.put( 1 , "Geeks" );
  
         System.out.println(tm);
  
         tm.put( 2 , "For" );
  
         System.out.println(tm);
     }
}

输出如下：

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

3.移除元件：为了从TreeMap中删除一个元素, 我们可以使用remove()方法。此方法获取键值, 并从该树图中删除键的映射(如果映射中存在)。

// Java program to demonstrate
// the working of TreeMap
  
import java.util.*;
class GFG {
     public static void main(String args[])
     {
         // Initialization of a TreeMap
         // using Generics
         TreeMap<Integer, String> tm
             = new TreeMap<Integer, String>();
  
         // Inserting the Elements
         tm.put( 3 , "Geeks" );
         tm.put( 2 , "Geeks" );
         tm.put( 1 , "Geeks" );
         tm.put( 4 , "For" );
  
         System.out.println(tm);
  
         tm.remove( 4 );
  
         System.out.println(tm);
     }
}

输出如下：

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

4.遍历TreeMap：有多种方法可以遍历Map。最著名的方法是使用每个循环并获取钥匙。密钥的值可以通过使用getValue()方法。

// Java program to demonstrate
// the working of TreeMap
  
import java.util.*;
class GFG {
     public static void main(String args[])
     {
         // Initialization of a TreeMap
         // using Generics
         TreeMap<Integer, String> tm
             = new TreeMap<Integer, String>();
  
         // Inserting the Elements
         tm.put( 3 , "Geeks" );
         tm.put( 2 , "For" );
         tm.put( 1 , "Geeks" );
  
         for (Map.Entry mapElement : tm.entrySet()) {
             int key
                 = ( int )mapElement.getKey();
  
             // Finding the value
             String value
                 = (String)mapElement.getValue();
  
             System.out.println(key + " : "
                                + value);
         }
     }
}

输出如下：

1 : Geeks
2 : For
3 : Geeks

TreeMap的功能：

树形图的一些重要功能包括：

  1. 这是该课程的成员Java集合框架。
  2. 类实现Map接口包含NavigableMap, SortedMap并扩展AbstractMap类。
  3. Java中的TreeMap不允许使用空键(例如Map), 因此空指针异常被抛出。但是, 多个空值可以与不同的键关联。
  4. 此类中的方法及其视图返回的条目对表示生成映射时的快照。他们不支持Entry.setValue方法。

同步的TreeMap：

TreeMap的实现不同步。这意味着, 如果多个线程同时访问树集, 并且至少有一个线程修改了该树集, 则必须在外部对其进行同步。这通常是通过使用Collections.synchronizedSortedSet方法。最好在创建时完成此操作, 以防止意外地异步访问集合。可以这样完成：

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

TreemMap如何在内部工作？

TreeMap中的方法在获取键集和值时会返回本质上是快速失败的Iterator。因此, 任何并发修改都会抛出ConcurrentModificationException。 TreeMap基于红黑树数据结构。树中的每个节点都具有：

  • 3个变量(K键=键, V值=值, 布尔色=颜色)
  • 3参考(左侧输入=左侧, 右侧输入=右侧, 父级输入=父级)
树状图内部工作

TreeMap中的构造方法

为了创建TreeMap, 我们需要创建TreeMap类的对象。 TreeMap类由各种构造函数组成, 这些构造函数允许创建TreeMap。以下是此类中可用的构造函数：

1. TreeMap()：该构造函数用于构建一个空的树图, 该树图将使用其键的自然顺序进行排序。让我们通过一个例子来理解这一点：

// Java program to demonstrate an
// example of TreeMap using the
// default constructor
  
import java.util.*;
import java.util.concurrent.*;
  
public class TreeMapImplementation {
  
     // Function to show TreeMap()
     // constructor example
     static void Example1stConstructor()
     {
         // Creating an empty TreeMap
         TreeMap<Integer, String> tree_map
             = new TreeMap<Integer, String>();
  
         // Mapping string values to int keys
         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" );
  
         // Displaying the TreeMap
         System.out.println( "TreeMap: "
                            + tree_map);
     }
  
     // Driver code
     public static void main(String[] args)
     {
  
         System.out.println( "TreeMap using "
                            + "TreeMap() constructor:\n" );
  
         Example1stConstructor();
     }
}

输出如下：

TreeMap using TreeMap() constructor:
TreeMap: {10=Geeks, 15=4, 20=Geeks, 25=Welcomes, 30=You}

2. TreeMap(Comparator comp)：此构造函数用于构建一个空的TreeMap对象, 其中的元素将需要排序顺序的外部说明。让我们通过一个例子来理解这一点：

// Java program to demonstrate
// an example of TreeMap using
// a comparator constructor
  
import java.util.*;
import java.util.concurrent.*;
  
// A class to represent a student.
class Student {
     int rollno;
     String name, address;
  
     // Constructor
     public Student( int rollno, String name, String address)
     {
         this .rollno = rollno;
         this .name = name;
         this .address = address;
     }
  
     // Used to print student details
     // in main()
     public String toString()
     {
         return this .rollno + " "
             + this .name + " "
             + this .address;
     }
}
  
// Comparator implementattion
class Sortbyroll
     implements Comparator<Student> {
  
     // Used for sorting in ascending order of
     // roll number
     public int compare(Student a, Student b)
     {
         return a.rollno - b.rollno;
     }
}
  
public class TreeMapImplementation {
  
     static void Example2ndConstructor()
     {
         // Creating an empty TreeMap
         TreeMap<Student, Integer> tree_map
             = new TreeMap<Student, Integer>( new Sortbyroll());
  
         // Mapping string values to int keys
         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 );
  
         // Displaying the TreeMap
         System.out.println( "TreeMap: "
                            + tree_map);
     }
  
     public static void main(String[] args)
     {
  
         System.out.println( "TreeMap using "
                            + "TreeMap(Comparator)"
                            + " constructor:\n" );
         Example2ndConstructor();
     }
}

输出如下：

TreeMap using TreeMap(Comparator) constructor:
TreeMap: {111 bbbb london=2, 121 cccc jaipur=1, 131 aaaa nyc=3}

3. TreeMap(Map M)：此构造函数用于使用给定映射M中的条目初始化TreeMap, 这些条目将使用键的自然顺序进行排序。让我们通过一个例子来理解这一点：

// Java program to demonstrate an
// example of TreeMap using the
// default constructor
  
import java.util.*;
import java.util.concurrent.*;
  
public class TreeMapImplementation {
  
     static void Example3rdConstructor()
     {
         // Creating a Map
         Map<Integer, String> hash_map
             = new HashMap<Integer, String>();
  
         // Mapping string values to int keys
         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" );
  
         // Creating the TreeMap using the Map
         TreeMap<Integer, String> tree_map
             = new TreeMap<Integer, String>(hash_map);
  
         // Displaying the TreeMap
         System.out.println( "TreeMap: "
                            + tree_map);
     }
  
     public static void main(String[] args)
     {
  
         System.out.println( "TreeMap using "
                            + "TreeMap(Map)"
                            + " constructor:\n" );
         Example3rdConstructor();
     }
}

输出如下：

TreeMap using TreeMap(Map) constructor:
TreeMap: {10=Geeks, 15=4, 20=Geeks, 25=Welcomes, 30=You}

4. TreeMap(SortedMap sm)：此构造函数用于使用给定项中的条目初始化TreeMap排序图它将以与给定排序图相同的顺序存储。让我们通过一个例子来理解这一点：

// Java program to demonstrate an
// example of TreeMap using the
// sortedmap constructor
  
import java.util.*;
import java.util.concurrent.*;
  
public class TreeMapImplementation {
  
     // Function to show
     // TreeMap(SortedMap) constructor example
     static void Example4thConstructor()
     {
         // Creating a SortedMap
         SortedMap<Integer, String> sorted_map
             = new ConcurrentSkipListMap<Integer, String>();
  
         // Mapping string values to int keys
         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" );
  
         // Creating the TreeMap using the SortedMap
         TreeMap<Integer, String> tree_map
             = new TreeMap<Integer, String>(sorted_map);
  
         // Displaying the TreeMap
         System.out.println( "TreeMap: "
                            + tree_map);
     }
  
     // Driver code
     public static void main(String[] args)
     {
  
         System.out.println( "TreeMap using "
                            + "TreeMap(SortedMap)"
                            + " constructor:\n" );
         Example4thConstructor();
     }
}

输出如下：

TreeMap using TreeMap(SortedMap) constructor:
TreeMap: {10=Geeks, 15=4, 20=Geeks, 25=Welcomes, 30=You}

TreeMap类中的方法

方法 描述
clear() 该方法从此TreeMap中删除所有映射并清除Map。
clone() 该方法返回此TreeMap的浅表副本。
containsKey(对象键) 如果此映射包含指定键的映射, 则返回true。
containsValue(对象值) 如果此映射将一个或多个键映射到指定值, 则返回true。
entrySet() 返回此映射中包含的映射的设置视图。
firstKey() 返回此排序映射中当前的第一个(最低)键。
get(对象键) 返回此映射将指定键映射到的值。
headMap(Object key_value) 该方法返回的Map部分视图严格小于参数key_value。
keySet() 该方法返回树形图中包含的键的Set视图。
lastKey() 返回当前在此排序映射中的最后一个(最高)键。
put(对象键, 对象值) 该方法用于将映射插入Map。
putAll(Map) 将所有映射从指定映射复制到此映射。
delete(对象键) 如果存在, 则从此TreeMap中删除此键的映射。
size() 返回此映射中的键值映射数。
subMap((K startKey, K endKey) 该方法返回此映射的一部分, 其键的范围从startKey(包括)到endKey(不包括)。
values() 返回此映射中包含的值的集合视图。
木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: