TreeMap 和 LinkedHashMap 核心源码解析

1 知识储备

在了解 TreeMap 之前,我们来看下日常工作中排序的两种方式,作为我们学习的基础储备,两种方式的代码如下:

package com.young.source.map;

/**
 * @author Shaw_Young
 * @date 2020/7/12 22:27
 */
public class DTO implements Comparable<DTO> {

    private Integer id;

    public DTO(Integer id) {
        this.id = id;
    }

    public Integer getId() {
        return id;
    }

    public void setId(Integer id) {
        this.id = id;
    }

    @Override
    public String toString() {
        return "DTO{" +
                "id=" + id +
                '}';
    }

    @Override
    public int compareTo(DTO o) {
        // 默认从小到大排序
        return id - o.getId();
    }
}

package com.young.source.map;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

/**
 * @author Shaw_Young
 * @date 2020/7/12 22:28
 */
public class TestTwoComparable {

    public static void main(String[] args) {
        // 第一种排序,从小到大排序,实现 Comparable 的 compareTo 方法进行排序
        ArrayList<DTO> list = new ArrayList<>();
        for (int i = 5; i > 0; i--) {
            list.add(new DTO(i));
        }
        Collections.sort(list);
        System.out.println(list);
        // 第二种排序,从大到小,利用外部排序器 Comparator 进行排序
        Comparator comparator = (Comparator<DTO>) (o1, o2) -> o2.getId() - o1.getId();
        ArrayList<DTO> list2 = new ArrayList<>();
        for (int i = 5; i > 0; i--) {
            list2.add(new DTO(i));
        }
        Collections.sort(list, comparator);
        System.out.println(list2);
    }

}

第一种排序输出的结果从小到大,结果是: [DTO{id=1}, DTO{id=2}, DTO{id=3}, DTO{id=4}, DTO{id=5}];
第二种输出的结果恰好相反,结果是: [DTO{id=5}, DTO{id=4}, DTO{id=3}, DTO{id=2}, DTO{id=1}]
以上两种就是分别通过Comparable和Comparator两者进行排序的方式,而 TreeMap 利用的也是此原理,从而实现了对 key 的排序,我们一起来看下。

2 TreeMap 整体架构

TreeMap 底层的数据结构就是红黑树,和 HashMap的红黑树结构一样。
不同的是, TreeMap 利用了红黑树左节点小,右节点大的性质,根据 key 进行排序,使每个元素能够插入到红黑树大小适当的位置,维护了key的大小关系,适用于key需要排序的场景。
因为底层使用的是平衡红黑树的结构,所以 containsKey、get、put、remove 等方法的时间复杂度都是 log(n)。

2.1 属性

TreeMap 常见的属性有:

//比较器，如果外部有传进来 Comparator 比较器，首先用外部的
//如果外部比较器为空，则使用 key 自己实现的 Comparable#compareTo 方法
//比较手段和上面日常工作中的比较 demo 是一致的
private final Comparator<? super K> comparator;

//红黑树的根节点
private transient Entry<K,V> root;

//红黑树的已有元素大小
private transient int size = 0;

//树结构变化的版本号，用于迭代过程中的快速失败场景
private transient int modCount = 0;

//红黑树的节点
static final class Entry<K,V> implements Map.Entry<K,V> {}

2.2 新增节点

我们来看下 TreeMap 新增节点的步骤:

  1. 判断红黑树的节点是否为空,为空的话,新增的节点直接作为根节点,代码如下:
Entry<K,V> t = root;
//红黑树根节点为空，直接新建
if (t == null) {
    // compare 方法限制了 key 不能为 null
    compare(key, key); // type (and possibly null) check
    // 成为根节点
    root = new Entry<>(key, value, null);
    size = 1;
    modCount++;
    return null;
}
  1. 根据红黑树左小右大的特性,进行判断,找到应该新增节点的父节点,代码如下:
Comparator<? super K> cpr = comparator;
if (cpr != null) {
    //自旋找到 key 应该新增的位置，就是应该挂载那个节点的头上
    do {
        //一次循环结束时，parent 就是上次比过的对象
        parent = t;
        // 通过 compare 来比较 key 的大小
        cmp = cpr.compare(key, t.key);
        //key 小于 t，把 t 左边的值赋予 t，因为红黑树左边的值比较小，循环再比
        if (cmp < 0)
            t = t.left;
        //key 大于 t，把 t 右边的值赋予 t，因为红黑树右边的值比较大，循环再比
        else if (cmp > 0)
            t = t.right;
        //如果相等的话，直接覆盖原值
        else
            return t.setValue(value);
        // t 为空，说明已经到叶子节点了
    } while (t != null);
}
  1. 在父节点的左边或右边插入新增节点,代码如下:
//cmp 代表最后一次对比的大小，小于 0 ，代表 e 在上一节点的左边
if (cmp < 0)
    parent.left = e;
//cmp 代表最后一次对比的大小，大于 0 ，代表 e 在上一节点的右边，相等的情况第二步已经处理了。
else
    parent.right = e;
  1. 着色旋转,达到平衡,结束。

从源码中,我们可以看到:

  1. 新增节点时,就是利用了红黑树左小右大的特性,从根节点不断往下查找,直到找到节点是null为止,节点为null说明到达了叶子节点;
  2. 查找过程中,发现key值已经存在,直接覆盖;
  3. TreeMap是禁止key是null值的。

类似的,TreeMap查找也是类似的原理。

2.3 小结

TreeMap 相对来说比较简单,红黑树和 HashMap 比较类似,比较关键的是通过 compare 来比较 key 的大小,然后利用红黑树左小右大的特性,为每个 key 找到自己的位置,从而维护了 key 的大小排序顺序。

3 LinkedHashMap 整体架构

HashMap 是无序的,TreeMap 可以按照 key 进行排序的,那有木有 Map 是可以维护插入的顺序的呢?接下来我们一起来看下 LinkedHashMap。

LinkedHashMap 本身是继承 HashMap 的,所以它拥有 HashMap 的所有特性,再此基础上,还提供了两大特性:

  • 按照插入顺序进行访问;
  • 实现了访问最少最先删除功能,其目的是把很久没有访问的key自动删除。

接着我们来看下上述两大特性

3.1 按照插入顺序访问

3.1.1 LinkedHashMap 链表结构

我们看下 LinkedHashMap 新增了哪些属性,以达到了链表结构的:

// 链表头
transient LinkedHashMap.Entry<K,V> head;

// 链表尾
transient LinkedHashMap.Entry<K,V> tail;

// 继承 Node，为数组的每个元素增加了 before 和 after 属性
static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

// 控制两种访问模式的字段，默认 false
// true 按照访问顺序，会把经常访问的 key 放到队尾
// false 按照插入顺序提供访问
final boolean accessOrder;

从上述 Map 新增的属性可以看到, LinkedHashMap的数据结构很像是把LinkedList的每个元素换成了HashMap的Node,像是两者的结合体,也正是因为增加了这些结构,从而能把Map的元素都串联起来,形成一个链表,而链表就可以保证顺序了,就可以维护元素插入进来的顺序。

3.1.2 如何按照顺序新增

LinkedHashMap 初始化时,默认 accessOrder为false,就是会按照插入顺序提供访问,插入方法使用的是父类 HashMap的put方法,不过覆写了put方法执行中调用的newNode/newThreeNode和afterNodeAccess方法。

newNode/newTreeNode方法,控制新增节点追加到链表的尾部,这样每次新节点都追加到尾部,即可保证插入顺序了,我们以newNode源码为例:

// 新增节点，并追加到链表的尾部
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
    // 新增节点
    LinkedHashMap.Entry<K,V> p =
        new LinkedHashMap.Entry<K,V>(hash, key, value, e);
    // 追加到链表的尾部
    linkNodeLast(p);
    return p;
}
// link at the end of list
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail;
    // 新增节点等于尾节点
    tail = p;
    // last 为空，说明链表为空，首尾节点相等
    if (last == null)
        head = p;
    // 链表有数据，直接建立新增节点和上个尾节点之间的前后关系即可
    else {
        p.before = last;
        last.after = p;
    }
}

LinkedHashMap 通过新增头节点、尾节点,给每个节点增加before、after属性,每次新增时,都会把节点追加到尾节点等手段,在新增的时候,就已经维护了按照插入顺序的链表结构了。

3.1.3 按顺序访问

LinkedHashMap 只提供了单向访问,即按照插入的顺序从头到尾进行访问,不能像 LinkedList那样可以双向访问。
我们主要通过迭代器进行访问,迭代器初始化的时候,默认从头节点开始访问,在迭代的过程中,不断访问当前节点的after节点即可。
Map对key、value和entity(节点)都提供出了迭代的方法,假设我们需要迭代entity,就可以使用LinkedHashMap.entrySet().iterator()这种写法直接返回LinkedHashIterator,LinkedHashIterator是迭代器,我们调用迭代器的nextNode方法就可以得到下一个节点,迭代器的源码如下:

// 初始化时，默认从头节点开始访问
LinkedHashIterator() {
    // 头节点作为第一个访问的节点
    next = head;
    expectedModCount = modCount;
    current = null;
}

final LinkedHashMap.Entry<K,V> nextNode() {
    LinkedHashMap.Entry<K,V> e = next;
    if (modCount != expectedModCount)// 校验
        throw new ConcurrentModificationException();
    if (e == null)
        throw new NoSuchElementException();
    current = e;
    next = e.after; // 通过链表的 after 结构，找到下一个迭代的节点
    return e;
}

在新增节点时,我们就已经维护了元素之间的插入顺序了,所以迭代访问时非常简单,只需要不断的访问当前节点的下一个节点即可。

3.2 访问最少删除策略

3.2.1 demo

这种策略也叫做LRU(Least recently used,最近最少使用),大概的意思就是经常访问的元素会被追加到队尾,这样不经常访问的数据自然就靠近队头,然后我们就可以设置删除策略,比如当Map元素个数大于多少时,把头节点删除,我们写个demo方便大家理解。

LinkedHashMap<Integer, Integer> map = new LinkedHashMap<Integer, Integer>(4, 0.75f, true) {
    {
        put(10, 10);
        put(9, 9);
        put(20, 20);
        put(1, 1);
    }

    @Override
    // 覆写了删除策略的方法，我们设定当节点个数大于 3 时，就开始删除头节点
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > 3;
    }
};
System.out.println("初始化: "+map);
map.get(9);
System.out.println("map.get(9): "+map);
map.get(20);
System.out.println("map.get(20): "+map);

打印出来的结果如下:

初始化: {9=9, 20=20, 1=1}
map.get(9): {20=20, 1=1, 9=9}
map.get(20): {1=1, 9=9, 20=20}

可以看到,map初始化的时候,我们放进去四个元素,但结果只有三个元素,10不见了,这个主要是因为们覆写了 removeEldestEntity 方法,我们实现了如果 map 中元素个数大于3时,我们就把队头的元素删除,当put(1,1)执行的时候,正好把队头的10删除,这个体现了达到我们设定的删除策略时,会自动的删除头节点。
当我们调用map.get(9)方法时,元素 9 移动到队尾,调用 map.get(20) 方法时,元素 20 被移动到队尾,这个体现了经常被访问的节点会被移动到队尾。

这个例子就很好的说明了访问最少删除策略,接下来我们看下原理。

3.2.2 元素被转移到队尾

我们先来看下为什么get时,元素会被移动到队尾:

public V get(Object key) {
    Node<K,V> e;
    // 调用 HashMap  get 方法
    if ((e = getNode(hash(key), key)) == null)
        return null;
    // 如果设置了 LRU 策略
    if (accessOrder)
    // 这个方法把当前 key 移动到队尾
        afterNodeAccess(e);
    return e.value;
}

从上述源码中，可以看到，通过 afterNodeAccess 方法把当前访问节点移动到了队尾，其实不仅仅是 get 方法，执行 getOrDefault、compute、computeIfAbsent、computeIfPresent、merge 方法时，也会这么做，通过不断的把经常访问的节点移动到队尾，那么靠近队头的节点，自然就是很少被访问的元素了。

3.2.3 删除策略

上述 demo 我们在执行 put 方法时，发现队头元素被删除了，LinkedHashMap 本身是没有 put 方法实现的，调用的是 HashMap 的 put 方法，但 LinkedHashMap 实现了 put 方法中的调用 afterNodeInsertion 方法，这个方式实现了删除，我们看下源码：

// 删除很少被访问的元素，被 HashMap 的 put 方法所调用
void afterNodeInsertion(boolean evict) { 
    // 得到元素头节点
    LinkedHashMap.Entry<K,V> first;
    // removeEldestEntry 来控制删除策略，如果队列不为空，并且删除策略允许删除的情况下，删除头节点
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        // removeNode 删除头节点
        removeNode(hash(key), key, null, false, true);
    }
}

3.3 小结

LinkedHashMap 提供了两个很有意思的功能：按照插入顺序访问和删除最少访问元素策略，简单地通过链表的结构就实现了，设计得非常巧妙。

©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 215,723评论 6赞 498
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 92,003评论 3赞 391
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 161,512评论 0赞 351
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 57,825评论 1赞 290
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 66,874评论 6赞 388
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 50,841评论 1赞 295
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,812评论 3赞 416
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 38,582评论 0赞 271
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 45,033评论 1赞 308
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,309评论 2赞 331
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,450评论 1赞 345
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 35,158评论 5赞 341
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,789评论 3赞 325
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,409评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,609评论 1赞 268
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 47,440评论 2赞 368
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 44,357评论 2赞 352