Java集合系列---TreeMap源码解析（巨好懂！！！）

TreeMap底层是基于红黑树实现，能实现根据key值对节点进行排序，排序可分为自然排序和定制排序。
自然排序：TreeMap的所有key必须实现Comparable接口，
定制排序：创建TreeMap的时候，传入一个Comparator对象，该对象负责对TreeMap的所有key进行排序，不需要key实现Comparable接口。

1 基本属性和构造器

//基本属性//比较器private final Comparator<? super K> comparator;//表示红黑树的根节点private transient Entry<K,V> root;//TreeMap中的元素个数private transient int size = 0;//TreeMap修改次数private transient int modCount = 0;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;//节点的颜色默认是黑色}//构造方法，comparator用键的顺序做比较
public TreeMap() {comparator = null;
}//构造方法，提供比较器，用指定比较器排序
public TreeMap(Comparator<? super K> comparator) {his.comparator = comparator;
}//将m中的元素转化daoTreeMap中，按照键的顺序做比较排序
public TreeMap(Map<? extends K, ? extends V> m) {comparator = null;putAll(m);
}//构造方法，指定的参数为SortedMap
//采用m的比较器排序
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) {}
}  

2 核心方法

1） put

public V put(K key, V value) {Entry<K,V> t = root; //记录根节点if (t == null) {compare(key, key); // type (and possibly null) check 检查是否为空//构造根节点，因为根节点没有父节点，传入null值。root = new Entry<>(key, value, null);size = 1;modCount++;return null;}int cmp;Entry<K,V> parent;// split comparator and comparable pathsComparator<? super K> cpr = comparator; //获取比较器if (cpr != null) { //如果获取了比较器则采用比较器进行比较do {parent = t;cmp = cpr.compare(key, t.key);if (cmp < 0)//如果key < t.key , 指向左子t = t.left;else if (cmp > 0) //如果key > t.key , 指向它的右孩子节点t = t.right;elsereturn t.setValue(value);//如果它们相等，替换key的值} 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;elsereturn t.setValue(value);} while (t != null);}Entry<K,V> e = new Entry<>(key, value, parent);//创建新节点，并制定父节点 此时父节点已经遍历到合适的位置if (cmp < 0)parent.left = e;elseparent.right = e;fixAfterInsertion(e);//新插入节点后重新调整红黑树 size++;modCount++;return null;}

2）比较方法

//比较方法，如果comparator==null ,采用comparable.compartTo进行比较，否则采用指定比较器比较大小
final int compare(Object k1, Object k2) {return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2): comparator.compare((K)k1, (K)k2);
}

3)红黑树的调整方法

 private void fixAfterInsertion(Entry<K,V> x) {//插入节点默认是红色的x.color = RED;//情形1： 新节点x 是树的根节点，没有父节点不需要任何操作//情形2： 新节点x 的父节点颜色是黑色的，也不需要任何操作while (x != null && x != root && x.parent.color == RED) {/*情形3：新节点x的父节点颜色是红色的判断x的节点的父节点位置，是否属于左孩子*/if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {//获取x节点的父节点的兄弟节点，上面语句已经判断出x节点的父节点为左孩子，所以直接取右孩子Entry<K,V> y = rightOf(parentOf(parentOf(x)));if (colorOf(y) == RED) {//判断是否x节点的父节点的兄弟节点为红色。setColor(parentOf(x), BLACK);// x节点的父节点设置为黑色setColor(y, BLACK);// 父亲节点的兄弟节点颜色设置为黑色setColor(parentOf(parentOf(x)), RED); // x.parent.parent设置为红色x = parentOf(parentOf(x));} else {//x的父节点的兄弟节点是黑色或者缺少的if (x == rightOf(parentOf(x))) {x = parentOf(x);rotateLeft(x);//左旋转操作}//现在x节点是其父的左孩子setColor(parentOf(x), BLACK);setColor(parentOf(parentOf(x)), RED);rotateRight(parentOf(parentOf(x)));//进行右旋转}} else {Entry<K,V> y = leftOf(parentOf(parentOf(x)));//y 是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 是其父亲的左孩子x = parentOf(x);rotateRight(x);//以父节点为旋转点，进行右旋操作}setColor(parentOf(x), BLACK);//父节点为设置为黑色setColor(parentOf(parentOf(x)), RED);//祖父节点为设置为红色rotateLeft(parentOf(parentOf(x)));//以父节点为旋转点，进行左旋操作}}}root.color = BLACK;//通过节点位置的调整，最终将红色的节点条调换到了根节点的位置，根节点重新设置为黑色}

在网上找到的一份讲解

4）get方法

java 集合？其实就是获取红黑树的根节点然后遍历获取到该节点

public V get(Object key) {Entry<K,V> p = getEntry(key);return (p==null ? null : p.value);}//根据指定的键获取对应的值
final Entry<K,V> getEntry(Object key) {if (comparator != null) // 使用比较器的getEntry版本，返回与指定键对应的项return getEntryUsingComparator(key);if (key == null)	//  如果指定键为 null 并且此映射使用自然顺序throw new NullPointerException();@SuppressWarnings("unchecked")Comparable<? super K> k = (Comparable<? super K>) key; // 使用自然顺序比较器Entry<K,V> p = root; // 父节点while (p != null) {int cmp = k.compareTo(p.key);if (cmp < 0)	// 左子节点p = p.left;else if (cmp > 0) // 右子节点p = p.right;elsereturn p;}return null;}

5）遍历方法

主要还是调用keySet方法，返回的keySet实现了Iterable接口，可以返回一个迭代器，该迭代器的具体实现是KeyIterator，而 KeyIterator 类的核心逻辑是在PrivateEntryIterator中实现的。然后通过nextEntry方法来循环获取下一个值。

public Set<K> keySet() {return navigableKeySet();}
public NavigableSet<K> navigableKeySet() {KeySet<K> nks = navigableKeySet;return (nks != null) ? nks : (navigableKeySet = new KeySet<>(this));
}static final class KeySet<E> extends AbstractSet<E> implements NavigableSet<E> {private final NavigableMap<E, ?> m;KeySet(NavigableMap<E,?> map) { m = map; }public Iterator<E> iterator() {if (m instanceof TreeMap)return ((TreeMap<E,?>)m).keyIterator();elsereturn ((TreeMap.NavigableSubMap<E,?>)m).keyIterator();}// 省略非关键代码
}Iterator<K> keyIterator() {return new KeyIterator(getFirstEntry());
}final class KeyIterator extends PrivateEntryIterator<K> {KeyIterator(Entry<K,V> first) {super(first);}public K next() {return nextEntry().key;}
}abstract class PrivateEntryIterator<T> implements Iterator<T> {Entry<K,V> next;Entry<K,V> lastReturned;int expectedModCount;PrivateEntryIterator(Entry<K,V> first) {expectedModCount = modCount;lastReturned = null;next = first;}public final boolean hasNext() {return next != null;}final Entry<K,V> nextEntry() {Entry<K,V> e = next;if (e == null)throw new NoSuchElementException();if (modCount != expectedModCount)throw new ConcurrentModificationException();// 寻找节点 e 的后继节点next = successor(e);lastReturned = e;return e;}// 其他方法省略
}

6) remove

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--;//数量减一//判断它是否有两个孩子if (p.left != null && p.right != null) {Entry<K,V> s = successor(p);//寻找继承者，继承者为当前节点的右孩子节点或者右孩子节点的最小左孩子p.key = s.key;//替换key和valuep.value = s.value;p = s;//指向继承者} // p has 2 children//如果p找到替代节点的话，就是对替代节点的操作，否则的话就是对p的操作//根据上面的属性可以知道不可能存在左右两个孩子都存在的情况，successor寻找的就是最小节点Entry<K,V> replacement = (p.left != null ? p.left : p.right);if (replacement != null) {//判断最小节点是否有右孩子// Link replacement to parentreplacement.parent = p.parent;if (p.parent == null)//如果p没有父节点的话root = replacement;//则指向根节点//如果p为左孩子，则将p.parent.left = p.leftelse if (p == p.parent.left)//判断p是不是父节点的左节点p.parent.left  = replacement;elsep.parent.right = replacement;// Null out links so they are OK to use by fixAfterDeletion.//清空p节点p.left = p.right = p.parent = null;// Fix replacementif (p.color == BLACK)//调整红黑树fixAfterDeletion(replacement);} else if (p.parent == null) { // return if we are the only node.root = null;} else { //  No children. Use self as phantom replacement and unlink.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;}}}

• 注意到当p是有左右节点的时候，对红黑树的调整是fixAfterDeletion(replacement);，传入的参数不是p，这是因为该节点的颜色并没有修改，所以需要考虑顶替被它替换掉的节点位置的平衡，故传入的是replacement，其他情况需要调整的都是p

7） fixAfterDeletion

private void fixAfterDeletion(Entry<K,V> x) {//不是根节点，颜色为黑色，调整结构while (x != root && colorOf(x) == BLACK) {//判断x是否为左孩子if (x == leftOf(parentOf(x))) {//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)); //重新设置x的兄弟节点}if (colorOf(leftOf(sib))  == BLACK &&colorOf(rightOf(sib)) == BLACK) {setColor(sib, RED); //兄弟节点的两个孩子都是黑色的重新设置兄弟节点的颜色，修改为红色x = parentOf(x);   //将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;  //设置x为根节点}} else { // symmetric//x为父节点的右节点，参考上面的操作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);
}

参考博客:
https://segmentfault.com/a/1190000012775806