TreeMap 源码分析 - 新增
TreeMap 源码分析-新增
TreeMap 整体架构
TreeMap 底层的数据结构也是红黑树，和 HashMap 的红黑树结构一样。
但是 TreeMap 利用了红黑树左节点小、右节点大的性质，根据 key 进行了排序，使每个元素能够插入大小适当的位置，红黑树中维护了 key 的大小关系，适用于 key 需要排序的场景。
containsKey、get、put、remove 等方法的时间复杂度都是 log(n)。
属性
TreeMap 常见的属性有：
private final Comparator<? super K> comparator;比较器，如果外部有传进来 Comparator 比较器则优先用外部的，如果外部比较器为空，则使用 key 自己实现的 Comparable-compareTo() 方法
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> {}红黑树的节点
新增节点
TreeMap 新增节点的步骤如下：
判断红黑树的节点是否为空，为空的话，新增的节点直接作为根节点
根据红黑树左小右大的特性，进行判断，找到应该新增节点的父节点
在父节点的左边或右边插入新增节点
源代码：
Entry<K,V> t = root; if (t == null) {//红黑树根节点为空，直接新建
compare(key, key);compare 方法限制了 key 不能为 null
if (cpr != null) { do{} while()自旋找到 key 应该新增的位置，就是应该挂载那个节点的头上
parent = t;一次循环结束时，parent 就是上次比过的对象
cmp = cpr.compare(key, t.key);通过 compare 来比较 key 的大小
if (cmp < 0) t = t.left;key 小于 t，把 t 左边的值赋给 t，因为红黑树左边的值比较小，循环再比
else if (cmp > 0) t = t.right; key 大于 t，把 t 右边的值赋予 t，因为红黑树右边的值比较大，循环再比
return t.setValue(value); 如果相等的话，直接覆盖原值
if (cmp < 0) parent.left = e;cmp 代表最后一次对比的大小，小于 0 ，代表 e 在上一节点的左边
还未添加个人签名 2020.02.06 加入
还未添加个人简介
评论