java源码解析（java新手代码大全）
TreeMap
简介
TreeMap是一个直接由红黑树实现的结构，对于Key值得比较来排序，显然得到：
1.key的class必须实现comparable方法， 不能抛出ClassCastException异常，否则必须指定一个comprartor
2.由于TreeMap实现了Serializable接口，所以默认的或者自定义的comparator也应该实现该接口
最重要的是，实现了NavigableMap，我理解为导航map,提供了各种操作map视图的操作
public class TreeMap&<K,V&> extends AbstractMap&<K,V&> implements NavigableMap&<K,V&>, Cloneable, java.io.Serializable{}复制代码构造方法
四个构造方法，其实就是是否使用默认的compatator
对于无序Map，直接调用putAll,有序的SortedMap话递归调用buildFromSorted，提高效率
public TreeMap() { comparator = null;}public TreeMap(Comparator&<? super K&> comparator) { this.comparator = comparator; }?public TreeMap(Map&<? extends K, ? extends V&> m) { comparator = null; putAll(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) { }}复制代码但是putAll依然判断了map instanceof SortedMap
具体的红黑树的操作在此不作赘述
remove(),put()最根本的操作是红黑树的操作，get()也是二叉搜索树比较直观的实现
方法详解
有关树的操作的方法，其实就是代码分支比较多，需要考虑各种情况然后转换为代码就好了比较的话看如果有comparator就用，没有就用key默认的comparable
successor() 查找下个节点
在containsValue()从第一个节点开始successor遍历在forEach()从第一个节点开始successor遍历replaceAll()从第一个节点开始successor遍历赋值新的valueremove()遍历找出Object删除
static &<K,V&> TreeMap.Entry&<K,V&> successor(Entry&<K,V&> t) { // 首先明确，下个节点是比当前节点大的节点，为当前节点右节点的左叶子节点 if (t == null) return null; else if (t.right != null) { Entry&<K,V&> p = t.right; while (p.left != null) p = p.left; return p; } else { Entry&<K,V&> p = t.parent; Entry&<K,V&> ch = t; // 当右节点为空，并且是父节点的右节点时，下个节点当前分支树的父节点 while (p != null &&&& ch == p.right) { ch = p; p = p.parent; } // 当右节点为空，并且是父节点的左节点时，下个节点当前节点的父节点 return p; }}复制代码getCeilingEntry()/getFloorEntry 获取[low,key]/[key,high]的最大/小值，没有返回null
// 这个跟successor是相似的，其实如果根据搜索树没找到，就是找的下一个节点final Entry&<K,V&> getCeilingEntry(K key) { Entry&<K,V&> p = root; while (p != null) { int cmp = compare(key, p.key); //比当前节点小，再跟左子节点比较 if (cmp &< 0) { if (p.left != null) p = p.left; else return p; } else if (cmp &> 0) { //比当前节点大，再跟右子节点比较 if (p.right != null) { p = p.right; } else { //这里跟successor相同，比最右叶子大，下一个为当前子树的父节点 Entry&<K,V&> parent = p.parent; Entry&<K,V&> ch = p; while (parent != null &&&& ch == parent.right) { ch = parent; parent = parent.parent; } return parent; } } else //相等的话返回当前节点 return p; } return null;}//跟上面是镜像的过程final Entry&<K,V&> getFloorEntry(K key) { Entry&<K,V&> p = root; while (p != null) { int cmp = compare(key, p.key); //比当前节点大，跟右子节点比较 if (cmp &> 0) { if (p.right != null) p = p.right; else return p; } else if (cmp &< 0) { //比当前节点小，再跟左子节点比较 if (p.left != null) { p = p.left; } else { Entry&<K,V&> parent = p.parent; Entry&<K,V&> ch = p; //比最左叶子小，下一个为当前子树的父节点 while (parent != null &&&& ch == parent.left) { ch = parent; parent = parent.parent; } return parent; } } else //相等的话返回当前节点 return p;? } return null;}复制代码getHigherEntry()/getLowerEntry获取[low,key)/(key,high]的最大/小值，没有返回null
跟getCeilingEntry一样的只不过对于相等的情况，不考虑相等的情况
final Entry&<K,V&> getHigherEntry(K key) { Entry&<K,V&> p = root; while (p != null) { int cmp = compare(key, p.key); if (cmp &< 0) { if (p.left != null) p = p.left; else return p; } else { if (p.right != null) { p = p.right; } else { Entry&<K,V&> parent = p.parent; Entry&<K,V&> ch = p; while (parent != null &&&& ch == parent.right) { ch = parent; parent = parent.parent; } return parent; } } } return null;}复制代码DescendingMap()翻转map
底层由DescendingSubMap()实现，其实还是这个map，只不过对于所有的操作，比如getfist()，会将其转换为getLast()来执行,所以对于DescendingMap()的操作依然会影响原Map
同样的，subMap()的操作也会影响原Map
static final class DescendingSubMap&<K,V&> extends NavigableSubMap&<K,V&> { private static final long serialVersionUID = 912986545866120460L; // m是当前Map,fromStart是否从头开始为ture则lo为null，lo开始位置，loInclusive是否包含开始位置 DescendingSubMap(TreeMap&<K,V&> m, boolean fromStart, K lo, boolean loInclusive, boolean toEnd, K hi, boolean hiInclusive) { super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive); }复制代码//DescendingSubMap一些方法的实现TreeMap.Entry&<K,V&> subLowest() { return absHighest(); }TreeMap.Entry&<K,V&> subHighest() { return absLowest(); }TreeMap.Entry&<K,V&> subCeiling(K key) { return absFloor(key); }TreeMap.Entry&<K,V&> subHigher(K key) { return absLower(key); }TreeMap.Entry&<K,V&> subFloor(K key) { return absCeiling(key); }TreeMap.Entry&<K,V&> subLower(K key) { return absHigher(key); }复制代码subMap()+headMap()+tailMap()
正常map调用的是AscendingSubMap，跟DescendingMap相同，只是相反的实现