江苏龙网

  1. 主页 > 生活百科 > >

Java的TreeMap底层实现原理？

Java

阿里这段时间忙着制定下半年的OKR，其实在制定OKR的时候就能看出团队里谁是领导的嫡系，谁是团队的边角料 。嫡系的OKR都是从领导的核心项目分出来的，而其他人的OKR不会体现在领导的OKR里面，只配给嫡系做打下手的工作 。
“员工的绩效 ， 在制定OKR的时候 ， 已经确定了” 。
职场失意 ， 摸鱼得意 。我还是安心的更新《解读JAVA源码专栏》，在这个系列中，我将手把手带着大家剖析Java核心组件的源码 ， 内容包含集合、线程、线程池、并发、队列等，深入了解其背后的设计思想和实现细节，轻松应对工作面试 。这是解读Java源码系列的第六篇，将跟大家一起学习Java中比较特殊的数据结构 - TreeMap 。
引言上篇文章讲到LinkedHashMap可以保证元素的插入顺序或者访问顺序，而TreeMap也能保证元素顺序，不过按照键的顺序进行排序 。插入到TreeMap中的键值对，会自动按照键的顺序进行排序 。
简介HashMap底层结构是基于数组实现的，而TreeMap底层结构是基于红黑树实现的 。TreeMap利用红黑树的特性实现对键的排序 。额外介绍一下红黑树的特性：

  1. 节点是红色或者黑色
  2. 根节点是黑色
  3. 所有叶子节点是黑色
  4. 每个红色结点的两个子结点都是黑色 。（从每个叶子到根的所有路径上不能有两个连续的红色结点）
  5. 从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点 。
红黑树是基于平衡二叉树的改进，而平衡二叉树是为了解决二叉搜索树在特殊情况下，退化成链表，查找、插入效率退化成 O(n)，规定左右子树高度差不超过1，但是插入、删除节点的时候，所做的平衡操作比较复杂 。而红黑树的特性 ， 保证了平衡操作实现相对简单，树的高度仅比平衡二叉树高了一倍，查找、插入、删除的时间复杂度是 O(log n) 。

Java的TreeMap底层实现原理？

文章插图
使用示例利用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();    }}


推荐阅读


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

下一篇：图解Kafka适用场景，全网最全！