treemap（3、TreeMap源码解析）

时间2025-05-05 20:08:28分类IT科技浏览3740

导读：1 TreeMap基本介绍 Java TreeMap实现了SortedMap接口，也就是说会按照key的大小顺序对Map中的元素进行排序 key大小的评判可以通过其本身的自然顺序(natural ordering ，也可以通过构造时传入的比较器(Comparator 。 Tre...

1 TreeMap基本介绍

Java TreeMap实现了SortedMap接口，也就是说会按照key的大小顺序对Map中的元素进行排序 key大小的评判可以通过其本身的自然顺序(natural ordering) ，也可以通过构造时传入的比较器(Comparator) 。 TreeMap底层通过红黑树实现 TreeMap是非同步的。可以通过如下方式将TreeMap包装成同步的：SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...)); TreeMap 跟 HashMap是两种不同的结构，TreeMap没有使用hash相关概念

2 红黑树数据结构回顾

每个节点颜色不是黑色，就是红色根节点是黑色的红色节点不能连续对于每个节点，从该节点到其树尾端的简单路径上，均包含相同数目的黑色节点

3 成员变量

private final Comparator<? super K> comparator; //排序器，如果空，按照key的字典顺序来排序（升序）；comparator为空时用Comparable的排序接口 private transient Entry<K,V> root; //根节点 private transient int size = 0; //树中entry个数，即红黑树大小 private transient int modCount = 0; //数结构被修改的次数的 /** * Fields initialized to contain an instance of the entry set view * the first time this view is requested. Views are stateless, so * theres no reason to create more than one. */ private transient EntrySet entrySet; private transient KeySet<K> navigableKeySet; private transient NavigableMap<K,V> descendingMap; /** * Dummy value serving as unmatchable fence key for unbounded * SubMapIterators */ private static final Object UNBOUNDED = new Object(); private static final boolean RED = false; //红节点默认false private static final boolean BLACK = true; // 黑节点默认true

4 内部类Entry

它是组成树的节点的类型

static final class Entry<K,V> implements Map.Entry<K,V> { K key; // key V value; //value Entry<K,V> left; //左孩子 Entry<K,V> right; //右孩子 Entry<K,V> parent; //父节点 boolean color = BLACK; //默认黑色 //根据 key value 父节点创建新节点 Entry(K key, V value, Entry<K,V> parent) { this.key = key; this.value = value; this.parent = parent; } public K getKey() { return key; } public V getValue() { return value; } //替换value ，返回旧value public V setValue(V value) { V oldValue = this.value; this.value = value; return oldValue; } // 重写equals方法：key 和 value的引用都相等 public boolean equals(Object o) { if (!(o instanceof Map.Entry)) return false; Map.Entry<?,?> e = (Map.Entry<?,?>)o; return valEquals(key,e.getKey()) && valEquals(value,e.getValue()); } //重写hashCode方法，返回 key 和 value的hashCode 的异或运算结构 public int hashCode() { int keyHash = (key==null ? 0 : key.hashCode()); int valueHash = (value==null ? 0 : value.hashCode()); return keyHash ^ valueHash; } public String toString() { return key + "=" + value; } }

5 构造函数

// 构造函数一：不指定排序器。按照key的字典顺序来排序（升序） public TreeMap() { comparator = null; } // 构造函数二：指定排序器 public TreeMap(Comparator<? super K> comparator) { this.comparator = comparator; } //构造函数三：构造并返回跟参数m有相同键值映射结构的treeMap（m变为红黑树） public TreeMap(Map<? extends K, ? extends V> m) { comparator = null; putAll(m); } //构造函数四：构造并返回跟参数m（有序的）有相同键值映射结构的treeMap public TreeMap(SortedMap<K, ? extends V> m) { comparator = m.comparator(); try { buildFromSorted(m.size(), m.entrySet().iterator(), null, null); } catch (java.io.IOException cannotHappen) { } catch (ClassNotFoundException cannotHappen) { } }

Comparator Integer类型倒序排序

public static void main(String[] args) { TreeMap treeMap = new TreeMap<Integer ,String>(new ComparatorObj()); treeMap.put(2,"ss"); treeMap.put(3,"sss"); System.out.println(treeMap); } static class ComparatorObj implements Comparator<Integer>{ @Override public int compare(Integer o1, Integer o2) { return o2-o1; //倒序排序 } }

输出结果：

2022-07-11 18:02:23,871 [INFO] main: {3=sss, 2=ss}

6 重要方法分析

6.1 get方法分析

（实际调用getEntry(Object key)）

get(Object key)方法是对接口Map的方法实现 get(Object key)方法转为对getEntry(Object key)方法的实现分析：算法思想是根据key的自然顺序(或者比较器顺序)对二叉查找树进行查找，直到找到满足k.compareTo(p.key) == 0的entry，再返回entry的value 。

源码分析如下：

public V get(Object key) { Entry<K,V> p = getEntry(key); //根据key找到entry ，再返回其value return (p==null ? null : p.value); } //重点分析该方法 final Entry<K,V> getEntry(Object key) { if (comparator != null) return getEntryUsingComparator(key); if (key == null) throw new NullPointerException(); //key非空校验 @SuppressWarnings("unchecked") Comparable<? super K> k = (Comparable<? super K>) key; //自然顺序，使用Comparable的排序接口 Entry<K,V> p = root; while (p != null) { //从根节点开始循环遍历 int cmp = k.compareTo(p.key); //compareTo：左边减去右边 if (cmp < 0) //参数key值小于父节点key p = p.left; //取左子节点 else if (cmp > 0) p = p.right; //参数key值大于父节点key，取右子节点 else return p; //key相等，则直接返回当前entry } return null; }

查询方法说明：

在while循环外，创建动态游标节点，游标首次指向root节点，以游标!=null作为循环条件在while循环内，根据compareTo结果，取游标的左子节点或右子节点，作为新的游标找到满足k.compareTo(p.key) == 0的entry ，退出循环

getEntryUsingComparator源码：

//提供自定义排序器的查询找方法，原理类似 final Entry<K,V> getEntryUsingComparator(Object key) { @SuppressWarnings("unchecked") K k = (K) key; Comparator<? super K> cpr = comparator; if (cpr != null) { Entry<K,V> p = root; while (p != null) { int cmp = cpr.compare(k, p.key); //cpr.compare 第一个参数减去第二个参数 if (cmp < 0) p = p.left; else if (cmp > 0) p = p.right; else return p; } } return null; }

6.2 put方法分析

public V put(K key, V value) { Entry<K,V> t = root; // 情况一：根节点为空，将当前key value作为root if (t == null) { compare(key, key); //key为null则抛异常 root = new Entry<>(key, value, null);//初始化root size = 1; //叶子个数+1 modCount++; // 结构修改次数自增 return null; //新叶子，所以old value 为空 } // 情况二：如果找到key相同的，则更新value ，过程类似get方法 int cmp; Entry<K,V> parent; Comparator<? super K> cpr = comparator; if (cpr != null) { do { parent = t; cmp = cpr.compare(key, t.key); if (cmp < 0) t = t.left; else if (cmp > 0) t = t.right; else return t.setValue(value); } while (t != null); } else { if (key == null) throw new NullPointerException(); @SuppressWarnings("unchecked") Comparable<? super K> k = (Comparable<? super K>) key; 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); } //情况三：没有相同的key ，则添加新叶子。 //经过上面的两种遍历，完成了二分法查找，找到适合插入的地方：parent 。 Entry<K,V> e = new Entry<>(key, value, parent); //创建新的entry //确定新增叶子作为parent的左孩子还是右孩子，插入的动作完成 if (cmp < 0) parent.left = e; else parent.right = e; fixAfterInsertion(e); //插入完成后，对二叉树进行调整 size++; modCount++; return null; } //这个方法实际上是对key做null检查，如果是null会抛出异常（测试代码验证过） public TreeMap(Comparator<? super K> comparator) { this.comparator = comparator; }

put方法说明：

如果root为空，则新增的entry作为root 遍历搜索是否存在相同的key ，存在则替换value 。这过程也是二叉排序树的二分查找法：找到了作为插入点的parent 。 插入操作：找到parent ，并将其left或者right指向新的entry 。如果是插入，则需要对红黑树进行结构调整 。（插入：节点默认为红色，root节点：设置为黑色，覆盖节点：颜色保持不变）维护成员变量：size ，modCount 。

6.3 插入调整函数fixAfterInsertion()解析

/** From CLR */ private void fixAfterInsertion(Entry<K,V> x) { x.color = RED; //新增节点默认为红色，再进行规则判断 // 从树末端开始遍历：父节点是红色，则需要对树进行调整 while (x != null && x != root && x.parent.color == RED) { if (parentOf(x) == leftOf(parentOf(parentOf(x)))) { Entry<K,V> y = rightOf(parentOf(parentOf(x))); if (colorOf(y) == RED) { setColor(parentOf(x), BLACK); setColor(y, BLACK); setColor(parentOf(parentOf(x)), RED); x = parentOf(parentOf(x)); } else { if (x == rightOf(parentOf(x))) { x = parentOf(x); rotateLeft(x); } setColor(parentOf(x), BLACK); setColor(parentOf(parentOf(x)), RED); rotateRight(parentOf(parentOf(x))); } } else { Entry<K,V> y = leftOf(parentOf(parentOf(x))); if (colorOf(y) == RED) { setColor(parentOf(x), BLACK); setColor(y, BLACK); setColor(parentOf(parentOf(x)), RED); x = parentOf(parentOf(x)); } else { if (x == leftOf(parentOf(x))) { x = parentOf(x); rotateRight(x); } setColor(parentOf(x), BLACK); setColor(parentOf(parentOf(x)), RED); rotateLeft(parentOf(parentOf(x))); } } } root.color = BLACK; //在遍历外面，确保root一定是黑色 }

方法说明：

新增的节点默认为红色 ，并从树末端往上遍历 如果新增节点的父亲是红色 ，则需要进行结构调整 结构调整这部分有点复杂，回头再深入理解todo

6.4 删除方法remove()解析

知识回顾：

二叉排序树的删除过程

：（情况一，treeMap用后继代替，其实用前驱或者后继是一样的）

源码如下：

// 调用getEntry(key)找到对应entry ，调用deleteEntry 删除节点 public V remove(Object key) { Entry<K,V> p = getEntry(key); if (p == null) return null; V oldValue = p.value; deleteEntry(p); return oldValue; } //执行删除操作 private void deleteEntry(Entry<K,V> p) { //先对全局变量modCount 、size 进行调整 modCount++; size--; //情况1：左右孩子都不为空：后继节点代替 if (p.left != null && p.right != null) { Entry<K,V> s = successor(p); //寻找后继（另外分析） //将删除点的key 、value 、引用分别更新为代替节点 p.key = s.key; p.value = s.value; p = s; // } //情况2：有1个孩子 Entry<K,V> replacement = (p.left != null ? p.left : p.right); if (replacement != null) { replacement.parent = p.parent; //左孩子父亲更新删除节点的父亲 //父亲为root ，则后继变为新的root if (p.parent == null) root = replacement; //左孩子顶上 else if (p == p.parent.left) p.parent.left = replacement; //右孩子顶上 else p.parent.right = replacement; // 删除节点的left 、right 、parent置空：被移除出树 p.left = p.right = p.parent = null; // 删除黑色节点：调整结构 if (p.color == BLACK) fixAfterDeletion(replacement); } else if (p.parent == null) { //删除root节点 root = null; } else { // 情况1：没孩子 if (p.color == BLACK) fixAfterDeletion(p); //将父亲的左孩子或者有孩子清空 if (p.parent != null) { if (p == p.parent.left) p.parent.left = null; else if (p == p.parent.right) p.parent.right = null; p.parent = null; } } }

删除说明：

删除过程遵从二叉排序树的删除特点（1 、有一个孩子则孩子顶上；2两个孩子就用后继顶上，没有孩子则直接移除）节点删除，即left 、right 、parent置空；删除后，需要更新父亲节点的的左孩子或右孩子考虑是否需要更新全局变量root节点 只有删除点是BLACK的时候，才会触发调整函数 ，因为删除RED节点不会破坏红黑树的任何约束，而删除BLACK节点会破坏规则4 。

6.5 删除调整函数fixAfterDeletion()解析

private void fixAfterDeletion(Entry<K,V> x) { while (x != root && colorOf(x) == BLACK) { if (x == leftOf(parentOf(x))) { Entry<K,V> sib = rightOf(parentOf(x)); if (colorOf(sib) == RED) { setColor(sib, BLACK); setColor(parentOf(x), RED); rotateLeft(parentOf(x)); sib = rightOf(parentOf(x)); } if (colorOf(leftOf(sib)) == BLACK && colorOf(rightOf(sib)) == BLACK) { setColor(sib, RED); x = parentOf(x); } else { if (colorOf(rightOf(sib)) == BLACK) { setColor(leftOf(sib), BLACK); setColor(sib, RED); rotateRight(sib); sib = rightOf(parentOf(x)); } setColor(sib, colorOf(parentOf(x))); setColor(parentOf(x), BLACK); setColor(rightOf(sib), BLACK); rotateLeft(parentOf(x)); x = root; } } else { // symmetric Entry<K,V> sib = leftOf(parentOf(x)); if (colorOf(sib) == RED) { setColor(sib, BLACK); setColor(parentOf(x), RED); rotateRight(parentOf(x)); sib = leftOf(parentOf(x)); } if (colorOf(rightOf(sib)) == BLACK && colorOf(leftOf(sib)) == BLACK) { setColor(sib, RED); x = parentOf(x); } else { if (colorOf(leftOf(sib)) == BLACK) { setColor(rightOf(sib), BLACK); setColor(sib, RED); rotateLeft(sib); sib = leftOf(parentOf(x)); } setColor(sib, colorOf(parentOf(x))); setColor(parentOf(x), BLACK); setColor(leftOf(sib), BLACK); rotateRight(parentOf(x)); x = root; } } } setColor(x, BLACK); }

说明：结构调整这部分有点复杂，回头再深入理解todo

6.6 寻找后继函数successor()解析

//寻找任意节点后继 static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) { if (t == null) return null; //情况1：右孩子不为空，向后代遍历：找到右孩子中孙子最小的那个节点（不断寻找left，直至为空） else if (t.right != null) { Entry<K,V> p = t.right; while (p.left != null) p = p.left; return p; } else { // 情况2：右孩子为空，向祖先遍历，当任意节点是它父亲的左孩子时，则该节点的父亲为t的后继 Entry<K,V> p = t.parent; Entry<K,V> ch = t; while (p != null && ch == p.right) { ch = p; p = p.parent; } return p; } }

寻找后继的算法说明： 对于任意k：

情况一：k的右孩子不为空，向后代遍历：找到右孩子的子孙子中辈分最低的左孩子（不断寻找left ，直至为空）情况二：key的右孩子为空，向祖先遍历：当任意节点是它父亲的左孩子时，则该节点的父亲为t的后继

右孩子不为空的后继寻找：

右孩子为空为空的后继寻找：

7 解惑：

1 TreeMap支持key自定义排序，而红黑树对key的固定的排序规则，两者如何兼容的?

支持key自定义排序：指通过自定义的排序器，计算出任意key相对其它key的大小关系红黑树对key的固定的排序：指按照红黑树的数据结构（二叉排序树+红黑节点规则），来组织key的树状结构，其中二叉排序的大小关系是根据排序器的计算出来的两者不冲突

声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。