深入底层：TreeMap与TreeSet源码理解

2024-03-29 14:53| 来源: 网络整理| 查看: 265

目录一、TreeMap二、TreeSet

一、TreeMap

1.基本特征：二叉树、二叉查找树、二叉平衡树、红黑树 TreeMap结构 2.每个节点的结构由：key value left right parent color 六部分组成

static final class Entry implements Map.Entry { K key; //键 V value; //值 Entry left;//左节点 Entry right;//右节点 Entry parent;//父节点 boolean color = BLACK;//颜色，默认黑色 }

3.添加原理从根节点开始比较，添加过程就是构造二叉平衡树的过程，会自动平衡，平衡离不开比较：外部比较器优先，然后是内部比较器。如果两个比较器都没有，就抛出异常

public V put(K key, V value) { Entry t = root; //如果是第一个节点，则进入if if (t == null) { //即使是添加第一个节点，也要使用比较器 compare(key, key); // type (and possibly null) check //创建根节点 root = new Entry(key, value, null); //此时只有一个节点 size = 1; return null; } //添加非第一个节点，则如下 int cmp; Entry parent; Comparator cpr = comparator; //如果外部比较器存在，就使用外部比较器 if (cpr != null) { do { parent = t; cmp = cpr.compare(key, t.key); if (cmp 0) t = t.right; //在右子树查找 else //找到了对应的key，使用新的value覆盖旧的value return t.setValue(value); } while (t != null); } else { //如果外部比较器没有，就使用内部比较器 .... } //找到了要添加的位置，创建新节点加到树中 Entry e = new Entry(key, value, parent); if (cmp //如果外部比较器存在，就使用外部比较器 if (comparator != null) return getEntryUsingComparator(key); if (key == null) throw new NullPointerException(); @SuppressWarnings("unchecked") //如果外部比较器不存在，就使用内部比较器 Comparable k = (Comparable) key; Entry p = root; while (p != null) { int cmp = k.compareTo(p.key); if (cmp 0) p = p.right; else //如果找到了，就返回Entry return p; } //如果没有找到，就返回null return null; }

3.TreeMap主要的成员变量及其含义

public class TreeMap implements NavigableMap { private final Comparator comparator;//外部比较器 private transient Entry root = null; //根节点 private transient int size = 0;//节点个数 public TreeMap() { comparator = null;//没有指定外部比较器 } public TreeMap(Comparator comparator) { this.comparator = comparator;//指定外部比较器 } } 二、TreeSet

1.TreeSet的底层使用的是TreeMap，所以底层也是红黑树 2.TreeSet的元素e是存储在TreeMap的key中，value统一为同一个 Object对象

public class TreeSet implements NavigableSet { //底层是TreeMap private transient NavigableMap m; private static final Object PRESENT = new Object();//同一个对象 public TreeSet() { //创建TreeSet对象就是创建一个TreeMap对象 this(new TreeMap()); } TreeSet(NavigableMap m) { this.m = m; } public boolean add(E e) { return m.put(e, PRESENT) == null; } public int size() { return m.size(); } }

【本文地址】

公司简介

联系我们