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

2023年 11月 29日 95.0k 0

阿里这段时间忙着制定下半年的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 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 HOT_WORD_COMPARATOR = new Comparator() {
            @Override
            public int compare(HotWord o1, HotWord o2) {
                return Integer.compare(o2.count, o1.count); // 降序排列
            }
        };
    
        // 使用TreeMap存储排行榜数据,key是热词对象,value是热词标题
        private TreeMap 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
    extends AbstractMap
    implements NavigableMap, Cloneable, java.io.Serializable {
    /**
    * 排序方式
    */
    private final Comparator

    相关文章

    JavaScript2024新功能:Object.groupBy、正则表达式v标志
    PHP trim 函数对多字节字符的使用和限制
    新函数 json_validate() 、randomizer 类扩展…20 个PHP 8.3 新特性全面解析
    使用HTMX为WordPress增效:如何在不使用复杂框架的情况下增强平台功能
    为React 19做准备:WordPress 6.6用户指南
    如何删除WordPress中的所有评论

    发布评论