当前位置:首页 » 《我的小黑屋》 » 正文

TreeMap源码详解

28 人参与  2024年10月02日 08:02  分类 : 《我的小黑屋》  评论

点击全文阅读


优质博文:IT-BLOG-CN

背景:昨天有人问我,他想将Map中的Key按照顺序进行遍历,我说直接使用keySet方法获取到Set集合,因为它是集成Collection接口,所以包含了sort方法后遍历取value值即可。但当看到TreeMap的那一刻,我发现自己错了。

再说一个很重要的概念:
【1】TreeMapkey不能为nullvalue可以为null;
【2】HashMapkey可以为nullvalue可以为null;
【3】ConcurrentHashMapHashTablekeyvalue都不可以为null;

一、TreeMap 结构

如类图所示:TreeMap也是一种Map实现了SortedMap<K,V>接口,说明他内部对Key进行了排序。而HashMap内部的Key是无序的。TreeMap的底层是一颗红黑树,这是一种自然平衡二叉搜索树,可以保证在插入,删除,查找等操作中的时间复杂度为O(log n)

使用TreeMap时,放入的Key必须实现Comparable接口。StringInteger这些类已经实现了Comparable接口,因此可以直接作为Key使用。作为Value的对象则没有任何要求。

如果作为Keyclass没有实现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接口要求实现一个比较方法,它负责比较传入的两个元素p1p2,如果p1 < p2,则返回负数,通常是-1,如果p1 == p2,则返回0,如果p1 > p2,则返回正数,通常是1TreeMap内部根据比较结果对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】firstKeylastKey:分别返回TreeMap中最小和最大的键;

// 返回 TreeMap 中最小和最大的键System.out.println(map.firstKey()); // AliceSystem.out.println(map.lastKey()); // David

【2】lowerKeyhigherKey:分别返回TreeMap中小于和大于给定键的最近的键;

// 返回 TreeMap 中小于和大于给定键的最近的键System.out.println(map.lowerKey("Bob")); // AliceSystem.out.println(map.higherKey("Bob")); // Charlie

【3】floorKeyceilingKey:分别返回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】headMaptailMap:分别返回一个子映射,包含小于或等于给定键或大于或等于给定键的所有键值对;

// 返回一个子映射,包含小于或等于给定键或大于或等于给定键的所有键值对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】firstEntrylastEntry:分别返回TreeMap中最小和最大的键值对;

// 返回 TreeMap 中最小和最大的键值对System.out.println(map.firstEntry()); // Alice=90System.out.println(map.lastEntry()); // David=60

【7】lowerEntryhigherEntry:分别返回TreeMap中小于和大于给定键的最近的键值对;

// 返回 TreeMap 中小于和大于给定键的最近的键值对System.out.println(map.lowerEntry("Bob")); // Alice=90System.out.println(map.higherEntry("Bob")); // Charlie=70

【8】floorEntryceilingEntry:分别返回TreeMap中小于等于和大于等于给定键的最近的键值对;

// 返回 TreeMap 中小于等于和大于等于给定键的最近的键值对System.out.println(map.floorEntry("Bob")); // Bob=80System.out.println(map.ceilingEntry("Bob")); // Bob=80

【9】pollFirstEntrypollLastEntry:分别返回并删除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,则需要进行同步处理。


点击全文阅读


本文链接:http://zhangshiyu.com/post/167044.html

<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

关于我们 | 我要投稿 | 免责申明

Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1