优质博文:IT-BLOG-CN
背景:昨天有人问我,他想将Map
中的Key
按照顺序进行遍历,我说直接使用keySet
方法获取到Set
集合,因为它是集成Collection
接口,所以包含了sort
方法后遍历取value
值即可。但当看到TreeMap
的那一刻,我发现自己错了。
再说一个很重要的概念:
【1】TreeMap
的key
不能为null
,value
可以为null
;
【2】HashMap
的key
可以为null
,value
可以为null
;
【3】ConcurrentHashMap
和HashTable
的key
和value
都不可以为null
;
一、TreeMap 结构
如类图所示:TreeMap
也是一种Map
实现了SortedMap<K,V>
接口,说明他内部对Key
进行了排序。而HashMap
内部的Key
是无序的。TreeMap
的底层是一颗红黑树,这是一种自然平衡二叉搜索树,可以保证在插入,删除,查找等操作中的时间复杂度为O(log n)
使用TreeMap
时,放入的Key
必须实现Comparable
接口。String
、Integer
这些类已经实现了Comparable
接口,因此可以直接作为Key
使用。作为Value
的对象则没有任何要求。
如果作为Key
的class
没有实现Comparable
接口,那么,必须在创建TreeMap
时同时指定一个自定义排序算法,我们可以先看下TreeMap
的构造器:
// 默认构造函数。使用该构造函数,TreeMap中的元素按照自然排序进行排列。TreeMap() // 创建的TreeMap包含MapTreeMap(Map<? extends K, ? extends V> copyFrom) // 指定Tree的比较器TreeMap(Comparator<? super K> comparator) // 创建的TreeSet包含copyFromTreeMap(SortedMap<K, ? extends V> copyFrom)
实际开发中案例:Comparator
接口要求实现一个比较方法,它负责比较传入的两个元素p1
和p2
,如果p1 < p2
,则返回负数,通常是-1
,如果p1 == p2
,则返回0
,如果p1 > p2
,则返回正数,通常是1
。TreeMap
内部根据比较结果对Key
进行排序。
import java.util.*;public class Main { public static void main(String[] args) { Map<Person, Integer> map = new TreeMap<>(new Comparator<Person>() { public int compare(Person p1, Person p2) { return p1.name.compareTo(p2.name); } }); map.put(new Person("Tim"), 1); map.put(new Person("Baby"), 2); map.put(new Person("Luna"), 3); for (Person key : map.keySet()) { System.out.println(key); } // {Person: Baby}, {Person: Luna}, {Person: Tim} System.out.println(map.get(new Person("Baby"))); // 2 }}class Person { public String name; Person(String name) { this.name = name; } public String toString() { return "{Person: " + name + "}"; }}
Person
类并未覆写equals()
和hashCode()
,因为TreeMap
不使用equals()
和hashCode()
。
二、TreeMap API
基础数据:
// 创建一个 TreeMapTreeMap<String, Integer> map = new TreeMap<>();// 向 TreeMap 中添加键值对map.put("Alice", 90);map.put("Bob", 80);map.put("Charlie", 70);map.put("David", 60);
TreeMap
因为排序等特性,所以包含了一些特殊的API
这里简单介绍一下:
【1】firstKey
和lastKey
:分别返回TreeMap
中最小和最大的键;
// 返回 TreeMap 中最小和最大的键System.out.println(map.firstKey()); // AliceSystem.out.println(map.lastKey()); // David
【2】lowerKey
和higherKey
:分别返回TreeMap
中小于和大于给定键的最近的键;
// 返回 TreeMap 中小于和大于给定键的最近的键System.out.println(map.lowerKey("Bob")); // AliceSystem.out.println(map.higherKey("Bob")); // Charlie
【3】floorKey
和ceilingKey
:分别返回TreeMap
中小于等于和大于等于给定键的最近的键;
// 返回 TreeMap 中小于等于和大于等于给定键的最近的键System.out.println(map.floorKey("Bob")); // BobSystem.out.println(map.ceilingKey("Bob")); // Bob
【4】subMap
:返回一个子映射,包含给定范围内的所有键值对;
// 返回一个子映射,包含给定范围内的所有键值对System.out.println(map.subMap("Alice", true, "Charlie", true)); // {Alice=90, Bob=80, Charlie=70}
【5】headMap
和tailMap
:分别返回一个子映射,包含小于或等于给定键或大于或等于给定键的所有键值对;
// 返回一个子映射,包含小于或等于给定键或大于或等于给定键的所有键值对System.out.println(map.headMap("Charlie", true)); // {Alice=90, Bob=80, Charlie=70}System.out.println(map.tailMap("Charlie", true)); // {Charlie=70, David=60}
【6】firstEntry
和lastEntry
:分别返回TreeMap
中最小和最大的键值对;
// 返回 TreeMap 中最小和最大的键值对System.out.println(map.firstEntry()); // Alice=90System.out.println(map.lastEntry()); // David=60
【7】lowerEntry
和higherEntry
:分别返回TreeMap
中小于和大于给定键的最近的键值对;
// 返回 TreeMap 中小于和大于给定键的最近的键值对System.out.println(map.lowerEntry("Bob")); // Alice=90System.out.println(map.higherEntry("Bob")); // Charlie=70
【8】floorEntry
和ceilingEntry
:分别返回TreeMap
中小于等于和大于等于给定键的最近的键值对;
// 返回 TreeMap 中小于等于和大于等于给定键的最近的键值对System.out.println(map.floorEntry("Bob")); // Bob=80System.out.println(map.ceilingEntry("Bob")); // Bob=80
【9】pollFirstEntry
和pollLastEntry
:分别返回并删除TreeMap
中最小和最大的键值对;
// 返回并删除 TreeMap 中最小和最大的键值对System.out.println(map.pollFirstEntry()); // Alice=90System.out.println(map.pollLastEntry()); // David=60
根据上述的API
可知,如果遇到如下场景时,应当想到使用TreeMap
:
【1】需要按照键的自然顺序或者指定的比较器进行排序的场景,例如字典,排行榜,日程安排等。
【2】需要快速找到映射中最小或者最大的键或者值的场景,例如优先队列,堆,区间查询等。
【3】需要快速找到映射中某个范围内的所有键或者值的场景,例如范围搜索,前缀匹配,区间统计等。
三、注意事项
【1】如果使用自然顺序进行排序,则需要保证键是可比较的(实现了Comparable
接口),否则会抛出ClassCastException
异常。
【2】如果使用指定的比较器进行排序,则需要保证比较器是一致的(满足自反性,对称性,传递性),否则可能导致排序结果不正确或者抛出ClassCastException
异常。
【3】如果在遍历TreeMap
的过程中修改了其结构(添加或删除了元素),则可能导致ConcurrentModificationException
异常或者不确定的行为。
【4】如果在遍历TreeMap
的过程中修改了其元素(改变了键或者值),则可能导致排序结果不正确或者不确定的行为。
【5】TreeMap
不是线程安全的,如果多个线程同时访问或修改TreeMap
,则需要进行同步处理。