当前位置：首页 > 科技 > 软件

阿里面试官：你说一下Java的TreeMap底层实现原理？

来源：责编：时间：2023-11-30 09:29:54 157观看

导读阿里这段时间忙着制定下半年的OKR，其实在制定OKR的时候就能看出团队里谁是领导的嫡系，谁是团队的边角料。嫡系的OKR都是从领导的核心项目分出来的，而其他人的OKR不会体现在领导的OKR里面，只配给嫡系做打下手的工作。“员

阿里这段时间忙着制定下半年的OKR，其实在制定OKR的时候就能看出团队里谁是领导的嫡系，谁是团队的边角料。嫡系的OKR都是从领导的核心项目分出来的，而其他人的OKR不会体现在领导的OKR里面，只配给嫡系做打下手的工作。

“员工的绩效，在制定OKR的时候，已经确定了”。

职场失意，摸鱼得意。我还是安心的更新《解读Java源码专栏》，在这个系列中，我将手把手带着大家剖析Java核心组件的源码，内容包含集合、线程、线程池、并发、队列等，深入了解其背后的设计思想和实现细节，轻松应对工作面试。这是解读Java源码系列的第六篇，将跟大家一起学习Java中比较特殊的数据结构 - TreeMap。

引言

上篇文章讲到LinkedHashMap可以保证元素的插入顺序或者访问顺序，而TreeMap也能保证元素顺序，不过按照键的顺序进行排序。插入到TreeMap中的键值对，会自动按照键的顺序进行排序。

简介

HashMap底层结构是基于数组实现的，而TreeMap底层结构是基于红黑树实现的。TreeMap利用红黑树的特性实现对键的排序。额外介绍一下红黑树的特性：

节点是红色或者黑色
根节点是黑色
所有叶子节点是黑色
每个红色结点的两个子结点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色结点）
从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点。

红黑树是基于平衡二叉树的改进，而平衡二叉树是为了解决二叉搜索树在特殊情况下，退化成链表，查找、插入效率退化成 O(n)，规定左右子树高度差不超过1，但是插入、删除节点的时候，所做的平衡操作比较复杂。而红黑树的特性，保证了平衡操作实现相对简单，树的高度仅比平衡二叉树高了一倍，查找、插入、删除的时间复杂度是 O(log n)。

图片

使用示例

利用TreeMap可以自动对键进行排序的特性，比较适用一些需要排序的场景，比如排行榜、商品列表等。

Map<Integer, String> map = new TreeMap<>();map.put(1, "One");map.put(3, "Three");map.put(2, "Two");System.out.println(map); // 输出：{1=One, 2=Two, 3=Three}

实现一个简单的热词排行榜功能：

/** * @author 一灯架构 * @apiNote 热词 **/public class HotWord {    /**     * 热词内容     */    String word;    /**     * 热度     */    Integer count;    public HotWord(String word, Integer count) {        this.word = word;        this.count = count;    }}

import java.util.Comparator;import java.util.TreeMap;/** * @author 一灯架构 * @apiNote 热词排行榜 **/public class Leaderboard {    /**     * 自定义排序方式，按照热度降序排列     */    private static final Comparator<HotWord> HOT_WORD_COMPARATOR = new Comparator<HotWord>() {        @Override        public int compare(HotWord o1, HotWord o2) {            return Integer.compare(o2.count, o1.count); // 降序排列        }    };    // 使用TreeMap存储排行榜数据，key是热词对象，value是热词标题    private TreeMap<HotWord, String> rankMap = new TreeMap<>(HOT_WORD_COMPARATOR);    // 添加成绩    public void addHotWord(String name, int score) {        rankMap.put(new HotWord(name, score), name);    }    /**     * 打印排行榜     */    public void printLeaderboard() {        System.out.println("热词排行榜:");        int rank = 1;        for (HotWord hotWord : rankMap.keySet()) {            System.out.println("#" + rank + " " + hotWord);            rank++;        }    }    public static void main(String[] args) {        Leaderboard leaderboard = new Leaderboard();        leaderboard.addHotWord("闲鱼崩了", 90);        leaderboard.addHotWord("淘宝崩了", 95);        leaderboard.addHotWord("闲鱼崩了", 85);        leaderboard.addHotWord("钉钉崩了", 80);        leaderboard.printLeaderboard();    }}

输出结果：

热词排行榜:#1 HotWord(word=淘宝崩了, count=95)#2 HotWord(word=闲鱼崩了, count=90)#3 HotWord(word=闲鱼崩了, count=85)#4 HotWord(word=钉钉崩了, count=80)

类属性

看一下TreeMap的类属性，包含哪些字段？

public class TreeMap<K, V>        extends AbstractMap<K, V>        implements NavigableMap<K, V>, Cloneable, java.io.Serializable {    /**     * 排序方式     */    private final Comparator<? super K> comparator;    /**     * 红黑树根节点     */    private transient Entry<K, V> root;    /**     * 红黑树节点数     */    private transient int size = 0;    /**     * 红黑树的红黑节点表示     */    private static final boolean RED = false;    private static final boolean BLACK = true;    /**     * 红黑树节点对象     */    static final class Entry<K, V> implements Map.Entry<K, V> {        K key;        V value;        Entry<K, V> left;        Entry<K, V> right;        Entry<K, V> parent;        boolean color = BLACK;        /**         * 构造方法         */        Entry(K key, V value, Entry<K, V> parent) {            this.key = key;            this.value = value;            this.parent = parent;        }    }}

TreeMap类属性比较简单，包含排序方式comparator、红黑树根节点root、节点个数size等。自定义了一个红黑树节点类Entry，内部属性包括键值对、左右子树、父节点、红黑标记值等。

初始化

TreeMap常用的初始化方式有下面三个：

无参初始化，使用默认的排序方式。
指定排序方式的初始化
将普通Map转换为TreeMap，使用默认的排序方式。

/** * 无参初始化 */Map<Integer, Integer> map1 = new TreeMap<>();/** * 指定排序方式初始化 */Map<Integer, Integer> map2 = new TreeMap<>(new Comparator<Integer>() {    @Override    public int compare(Integer o1, Integer o2) {        return o1.compareTo(o2);    }});/** * 将普通Map转换为TreeMap */Map<Integer, Integer> map3 = new TreeMap<>(new HashMap<>());

再看一下对应的源码实现：

/** * 无参初始化 */public TreeMap() {    comparator = null;}/** * 指定排序方式初始化 */public TreeMap(Comparator<? super K> comparator) {    this.comparator = comparator;}/** * 将普通Map转换为TreeMap */public TreeMap(Map<? extends K, ? extends V> m) {    comparator = null;    putAll(m);}

方法列表

由于TreeMap存储是按照键的顺序排列的，所以还可以进行范围查询，下面举一些示例。

import java.util.Collections;import java.util.Map;import java.util.TreeMap;/** * @author 一灯架构 * @apiNote TreeMap方法测试 */public class TreeMapTest {    public static void main(String[] args) {        // 1. 创建一个热词排行榜（按热度倒序），key是热度，value是热词内容        TreeMap<Integer, String> rankMap = new TreeMap<>(Collections.reverseOrder());        rankMap.put(80, "阿里云崩了");        rankMap.put(100, "淘宝崩了");        rankMap.put(90, "钉钉崩了");        rankMap.put(60, "闲鱼崩了");        rankMap.put(70, "支付宝崩了");        System.out.println("热词排行榜：");        for (Map.Entry<Integer, String> entry : rankMap.entrySet()) {            System.out.println("#" + entry.getKey() + " " + entry.getValue());        }        System.out.println("-----------");        // 2. 获取排行榜的第一个元素        Map.Entry<Integer, String> firstEntry = rankMap.firstEntry();        System.out.println("firstEntry: " + firstEntry);        // 3. 获取排行榜的最后一个元素        Map.Entry<Integer, String> lastEntry = rankMap.lastEntry();        System.out.println("lastEntry: " + lastEntry);        // 4. 获取排行榜的大于指定键的最小元素（由于是倒序排列，所以结果是反的）        Map.Entry<Integer, String> higherEntry = rankMap.higherEntry(70);        System.out.println("higherEntry: " + higherEntry);        // 5. 获取排行榜的小于指定键的最大元素        Map.Entry<Integer, String> lowerEntry = rankMap.lowerEntry(70);        System.out.println("lowerEntry: " + lowerEntry);        // 6. 获取排行榜的大于等于指定键的最小元素        Map.Entry<Integer, String> ceilingEntry = rankMap.ceilingEntry(70);        System.out.println("ceilingEntry: " + ceilingEntry);        // 7. 获取排行榜的小于等于指定键的最大元素        Map.Entry<Integer, String> floorEntry = rankMap.floorEntry(70);        System.out.println("floorEntry: " + floorEntry);    }}

输出结果：

热词排行榜：#100 淘宝崩了#90 钉钉崩了#80 阿里云崩了#70 支付宝崩了#60 闲鱼崩了-----------firstEntry: 100=淘宝崩了lastEntry: 60=闲鱼崩了higherEntry: 60=闲鱼崩了lowerEntry: 80=阿里云崩了ceilingEntry: 70=支付宝崩了floorEntry: 70=支付宝崩了

其他方法的还包括：

作用	方法签名
获取第一个键	K firstKey()
获取最后一个键	K lastKey()
获取大于指定键的最小键	K higherKey(K key)
获取小于指定键的最大键	K lowerKey(K key)
获取大于等于指定键的最小键	K ceilingKey(K key)
获取小于等于指定键的最大键	K floorKey(K key)
获取第一个键值对	Map.Entry<K,V> firstEntry()
获取最后一个键值对	Map.Entry<K,V> lastEntry()
获取并删除第一个键值对	Map.Entry<K,V> pollFirstEntry()
获取并删除最后一个键值对	Map.Entry<K,V> pollLastEntry()
获取大于指定键的最小键值对	Map.Entry<K,V> higherEntry(K key)
获取小于指定键的最大键值对	Map.Entry<K,V> lowerEntry(K key)
获取大于等于指定键的最小键值对	Map.Entry<K,V> ceilingEntry(K key)
获取小于等于指定键的最大键值对	Map.Entry<K,V> floorEntry(K key)
获取子map，左闭右开	SortedMap<K,V> subMap(K fromKey, K toKey)
获取前几个子map，不包含指定键	SortedMap<K,V> headMap(K toKey)
获取前几个子map	NavigableMap<K,V> headMap(K toKey, boolean inclusive)
获取后几个子map，不包含指定键	SortedMap<K,V> tailMap(K fromKey)
获取后几个子map	NavigableMap<K,V> tailMap(K fromKey, boolean inclusive)
获取其中一段子map	NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)

put源码

再看一下TreeMap的put源码：

/** * put源码入口 */public V put(K key, V value) {    Entry<K,V> t = root;    // 1. 如果根节点为空，则创建根节点    if (t == null) {        compare(key, key);        root = new Entry<>(key, value, null);        size = 1;        modCount++;        return null;    }    int cmp;    Entry<K,V> parent;    // 2. 判断是否传入了排序方式，如果没有则使用默认    Comparator<? super K> cpr = comparator;    if (cpr != null) {        // 3. 如果传入了排序方式，使用do-while循环，找到目标值所在位置，并赋值        do {            parent = t;            cmp = cpr.compare(key, t.key);            // 4. 利用红黑树节点左小右大的特性，进行查找            if (cmp < 0) {                t = t.left;            } else if (cmp > 0) {                t = t.right;            } else {                return t.setValue(value);            }        } while (t != null);    } else {        // 5. TreeMap不允许key为null        if (key == null) {            throw new NullPointerException();        }        // 6. 如果没有传入排序方式，则使用Comparable进行比较        Comparable<? super K> k = (Comparable<? super K>) key;        // 7. 跟上面一致，使用do-while循环，利用红黑树节点左小右大的特性，查找目标值所在位置，并赋值        do {            parent = t;            cmp = k.compareTo(t.key);            if (cmp < 0) {                t = t.left;            } else if (cmp > 0) {                t = t.right;            } else {                return t.setValue(value);            }        } while (t != null);    }    // 8. 如果没有找到，则创建新节点    Entry<K,V> e = new Entry<>(key, value, parent);    if (cmp < 0) {        parent.left = e;    } else {        parent.right = e;    }    // 9. 插入新节点后，需要调整红黑树节点位置，保持红黑树的特性    fixAfterInsertion(e);    size++;    modCount++;    return null;}

put源码逻辑比较简单：

判断红黑树根节点是否为空，如果为空，则创建根节点。
判断是否传入了排序方式，如果没有则使用默认，否则使用自定义排序。
循环遍历红黑树，利用红黑树节点左小右大的特性，进行查找。
如果找到，就覆盖。如果没找到，就插入新节点。
插入新节点后，调整红黑树节点位置，保持红黑树的特性。

get源码

再看一下get源码：

/** * get源码入口 */public V get(Object key) {    // 调用查找节点的方法    Entry<K, V> p = getEntry(key);    return (p == null ? null : p.value);}/** * 查找节点方法 */final Entry<K, V> getEntry(Object key) {    // 1. 判断如果传入了排序方式，则使用排序方式查找节点    if (comparator != null) {        return getEntryUsingComparator(key);    }    if (key == null) {        throw new NullPointerException();    }    // 2. 否则使用默认方式查找    Comparable<? super K> k = (Comparable<? super K>) key;    Entry<K, V> p = root;    // 3. 利用红黑树节点左小右大的特性，循环查找    while (p != null) {        int cmp = k.compareTo(p.key);        if (cmp < 0) {            p = p.left;        } else if (cmp > 0) {            p = p.right;        } else {            return p;        }    }    return null;}/** * 使用传入的排序方式，查找节点方法 */final Entry<K, V> getEntryUsingComparator(Object key) {    K k = (K) key;    Comparator<? super K> cpr = comparator;    if (cpr != null) {        Entry<K, V> p = root;        // 3. 跟上面类似，利用红黑树节点左小右大的特性，循环查找        while (p != null) {            int cmp = cpr.compare(k, p.key);            if (cmp < 0) {                p = p.left;            } else if (cmp > 0) {                p = p.right;            } else {                return p;            }        }    }    return null;}

get方法源码与put方法逻辑类似，都是利用红黑树的特性遍历红黑树。

总结

TreeMap是一种有序Map集合，具有以下特性：

保证以键的顺序进行排列
具有一些以键的顺序进行范围查询的方法，比如firstEntry()、lastEntry()、higherEntry(K key)、 lowerEntry(K key) 等。
可以自定义排序方式，初始化的时候，可以指定是正序、倒序或者自定义排序。
不允许key为null，因为null值无法比较大小。
底层基于红黑树实现，查找、插入、删除的时间复杂度是O(log n)，而HashMap的时间复杂度是O(1)。

本文链接：http://www.28at.com/showinfo-26-35325-0.html阿里面试官：你说一下Java的TreeMap底层实现原理？

声明：本网页内容旨在传播知识，若有侵权等问题请及时与本网联系，我们将在第一时间删除处理。邮件：2376512515@qq.com

上一篇：你不知道的Websocket协议，这次给你讲明白！

下一篇：嵌入式软件设计原则随想

标签：

热门焦点

俄罗斯：将审查iPhone等外国公司设备保数据安全

iPhone和特斯拉都属于在各自领域领头羊的品牌，推出的产品也也都是数一数二的，但对于一些国家而言，它们的产品可靠性和安全性还是在限制范围内。近日，俄罗斯联邦通信、信息技术
小米平板5 Pro 12.4简评：多专多能兼顾影音娱乐的大屏利器

疫情带来了网课，网课盘活了安卓平板，安卓平板市场虽然中途停滞了几年，但好的一点就是停滞的这几年行业又有了新的发展方向，例如超窄边框、高刷新率、多摄镜头组合等，这就让安卓
一篇聊聊Go错误封装机制

%w 是用于错误包装（Error Wrapping）的格式化动词。它是用于 fmt.Errorf 和 fmt.Sprintf 函数中的一个特殊格式化动词，用于将一个错误（或其他可打印的值）包装在一个新的错误中。使
Flowable工作流引擎的科普与实践

一.引言当我们在日常工作和业务中需要进行各种审批流程时，可能会面临一系列技术和业务上的挑战。手动处理这些审批流程可能会导致开发成本的增加以及业务复杂度的上升。在这
一文掌握 Golang 模糊测试（Fuzz Testing）

模糊测试（Fuzz Testing）模糊测试（Fuzz Testing）是通过向目标系统提供非预期的输入并监视异常结果来发现软件漏洞的方法。可以用来发现应用程序、操作系统和网络协议等中的漏洞或
OPPO、vivo、小米等国内厂商Q2在印度智能手机市场份额依旧高达55%

7月20日消息，据外媒报道，研究机构的报告显示，在全球智能手机出货量同比仍在下滑的大背景下，印度这一有潜力的市场也未能幸免，出货量同比也有下滑，多家厂
iQOO Neo8 Pro即将开售：到手价3099元起安卓性能最强旗舰

5月23日，iQOO如期举行了新品发布会，全新的iQOO Neo8系列也正式与大家见面，包含iQOO Neo8和iQOO Neo8 Pro两个版本，其中标准版搭载高通骁龙8+，而Pro版更
OPPO Reno10 Pro英雄联盟定制礼盒公布：萨勒芬妮同款配色梦幻十足

5月24日，OPPO推出了全新的OPPO Reno 10系列，包含OPPO Reno10、OPPO Reno10 Pro和OPPO Reno10 Pro+三款新机，全系标配了超光影长焦镜头，是迄今为止拍照
外交部：美方应停止在网络安全问题上不负责任地指责他国

　中国外交部今天（16日）举行例行记者会。会上，有记者问，美国情报官员称，他们正在阻拦来自中国以及其他国家的黑客获取相关科研成果。中方对此有何评论？对此