TreeMap

基于红黑树（Red-Black tree）的 NavigableMap 实现。该映射根据其键的自然顺序进行排序，或者根据创建映射时提供的 Comparator 进行排序，具体取决于使用的构造方法。此实现为 containsKey、get、put 和 remove 操作提供受保证的 log(n) 时间开销。
这些算法是 Cormen、Leiserson 和 Rivest 的 Introduction to Algorithms 中的算法的改编。

关于TreeMap中红黑树：TreeMap红黑树分析

TreeMap的继承实现结构

public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable

TreeMap<K,V>：TreeMap是以key-value形式存储数据的。

extends AbstractMap<K,V>：继承了AbstractMap，实现Map接口时需要实现的工作量大大减少了。

implements NavigableMap：实现了NavigableMap，可以返回特定条件最近匹配的导航方法。方法 lowerEntry、floorEntry、ceilingEntry 和 higherEntry 分别返回与小于、小于等于、大于等于、
大于给定键的键关联的 Map.Entry 对象，如果不存在这样的键，则返回 null。

implements Cloneable：表明其可以调用clone()方法来返回实例的field-for-field拷贝。

implements Serializable：表明该类是可以序列化的。

主要字段：

/**
 * treeMap的排序规则，如果为null，则根据键的自然顺序进行排序
 */
private final Comparator<? super K> comparator;

/**
 * 红黑数的根节点
 */
private transient Entry<K,V> root;

/**
 * 红黑树节点的个数
 */
private transient int size = 0;

/**
 * treeMap的结构性修改次数。实现fast-fail机制的关键。
 */
private transient int modCount = 0;

/**
 * 视图只有在第一次请求时创建并只创建一个
 */
private transient EntrySet entrySet;
private transient KeySet<K> navigableKeySet;
private transient NavigableMap<K,V> descendingMap;

构造方法：

• TreeMap()：使用key的自然排序来构造一个空的treeMap。
• TreeMap(Comparator<? super K> comparator)：使用给定的比较器来构造一个空的treeMap。
• TreeMap(Map<? extends K, ? extends V> m)：使用key的自然排序来构造一个treeMap，treeMap包含给定map中所有的键值对。
  public TreeMap(Map<? extends K, ? extends V> m) { comparator = null; putAll(m); }
• TreeMap(SortedMap<K, ? extends V> m)：使用指定的sortedMap来构造treeMap。treeMap中含有sortedMap中所有的键值对，键值对顺序和sortedMap中相同。使用一个有序的map构造新的treemap。这个方法需要线性时间

主要方法：

get方法：

 /**
 * 通用二叉树的查找算法。提供log2(n)的复杂度
 * @param key
 * @return
 */
final Entry<K,V> getEntry(Object key) {
    // Offload comparator-based version for sake of performance
    // 直接使用指定的比较器查找
    if (comparator != null)
        return getEntryUsingComparator(key);// 与当前方法类似，只是使用compare(o1,o2)比较
    // 不允许null
    if (key == 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);
        // key小于当前节点取左节点比较
        if (cmp < 0)
            p = p.left;
        // key大于当前节点取右节点比较
        else if (cmp > 0)
            p = p.right;
        // 找到
        else
            return p;
    }
    // 没有找到
    return null;
}

 /**
 * 返回大于等于key的最小键。如果不存在就返回null。
 * 算法：
 * 1.如果key < 当前节点p，寻找左子树，若左子树不存在，p就是最小大于key的
 * 2.如果key > 当前节点p，寻找右子树，若右子树不存在，需要向上回溯第一个大于key的键
 * 即key < 节点p，使用左链接(一个大于等于key的键的左子树中不存在更小的大于等于key的键)
 * @param key
 * @return
 */
final Entry<K,V> getCeilingEntry(K key) {
    Entry<K,V> p = root;
    while (p != null) {
        // 静态方法，比较器comparator为空就是用默认的比较
        int cmp = compare(key, p.key);
        // key比当前节点小
        if (cmp < 0) {
            // 当前节点存在更小的子节点
            if (p.left != null)
                p = p.left;
            // 没有更小的子节点，当前节点就是树中最小大于key的节点
            else
                return p;
        } 
        // key比当前节点大
        else if (cmp > 0) {
            // 当前节点存在更大的子节点
            if (p.right != null) {
                p = p.right;
            }
            // 当前节点没有更大的节点能大于key，即子树中不存在大于key的键。只能向上回溯第一个使用左链接比较的节点
            // 即当一个节点p大于key时，仍然在左子树中寻找小于p大于key的键，那么第一个左链接节点必定是最小大于key的
            else {
                Entry<K,V> parent = p.parent;
                Entry<K,V> ch = p;
                // parent.left连接时退出循环或不存在大于等于key的键
                while (parent != null && ch == parent.right) {
                    ch = parent;
                    parent = parent.parent;
                }
                return parent;
            }
        } 
        // 找到key相等节点p
        else
            return p;
    }
    return null;
}

 /**
 * 取小于等于key的最大键。遇到第一个key.compareTo(p) > 0的就会到右子树中取最小值
 * 算法：
 * 1.如果key < 当前节点p，若p的左子树存在，就查找左子树，如果不存在，就回溯找第一个小于key的键
 * 即k > 节点p，使用右连接的父节点(原理是当一个节点小于key，就会查找右子树是否有大一点的节点小于key)
 * 2.如果key > 当前节点p，寻找右子树，若右子树不存在就返回p最小大于等于key的
 * @param key
 * @return
 */
final Entry<K,V> getFloorEntry(K key) {
    Entry<K,V> p = root;
    while (p != null) {
        int cmp = compare(key, p.key);
        // key比当前节点大
        if (cmp > 0) {
            if (p.right != null)
                p = p.right;
            // 找不到比key更大的键，就返回当前键是小于key的最大键
            else
                return p;
        } 
        // key比当前节点小
        else if (cmp < 0) {
            if (p.left != null) {
                p = p.left;
            } 
            // 找不到
            else {
                // 如果左子树中不存在跟接近key的节点就返回第一个右链接的父节点
                Entry<K,V> parent = p.parent;
                Entry<K,V> ch = p;
                // 当parent使用右链接时退出循环或不存在小于等于key的键
                while (parent != null && ch == parent.left) {
                    ch = parent;
                    parent = parent.parent;
                }
                return parent;
            }
        } 
        // 相等
        else
            return p;

    }
    return null;
}

put方法：

 /**
 * 在map中关联指定的键值对。不允许插入null。只对插入操作进行红黑树修复。提供log(n)复杂度
 */
public V put(K key, V value) {
    Entry<K,V> t = root;
    // 根节点为null就直接插入新键
    if (t == null) {
        compare(key, key); // type (and possibly null) check

        root = new Entry<>(key, value, null);
        size = 1;
        modCount++;
        return null;
    }
    // 引用放在循环外。是否感觉可以改善自己的代码啦啦？？？等到知道具体机制可能就不会这样想了。手动滑稽
    int cmp;
    Entry<K,V> parent;
    // split comparator and comparable paths
    Comparator<? super K> cpr = comparator;
    // 使用比较器查找到key进行替换操作
    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);
    }
    // 使用默认的顺序查找到key进行替换操作
    else {
        // 不允许为null
        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);
    }
    // 将新节点插入到父节点
    Entry<K,V> e = new Entry<>(key, value, parent);
    // 判断父节点应用哪个连接新节点
    if (cmp < 0)
        parent.left = e;
    else
        parent.right = e;
    // 修复操作
    fixAfterInsertion(e);
    size++;
    modCount++;
    return null;
}

/**
 * 将指定映射中的所有映射关系复制到此映射中。如果已经存在的映射会被替换新的值
 * 对于空treemap使用putAll提供线性时间。好于非空treemap的n*logn
 * @author Navy D
 */
public void putAll(Map<? extends K, ? extends V> map) {
    int mapSize = map.size();
    // treemap是空的  参数map是sortedMap
    if (size==0 && mapSize!=0 && map instanceof SortedMap) {
        Comparator<?> c = ((SortedMap<?,?>)map).comparator();
        // 比较器一样为null或同一个对象
        if (c == comparator || (c != null && c.equals(comparator))) {
            ++modCount;
            try {
                // 使用迭代器通过key构建排序数据，需要线性时间 这个方法暂时没用到就不看了，用到再更新吧
                buildFromSorted(mapSize, map.entrySet().iterator(),
                                null, null);
            } catch (java.io.IOException cannotHappen) {
            } catch (ClassNotFoundException cannotHappen) {
            }
            return;
        }
    }
    // abstractMap.putAll方法采用for调用put方法
    super.putAll(map);
}

delete方法：

 /**
 * 在map中删除指定的键和关联的值
 */
public V remove(Object key) {
    // 查找
    Entry<K,V> p = getEntry(key);
    if (p == null)
        return null;

    V oldValue = p.value;
    // 删除键值对
    deleteEntry(p);
    return oldValue;
}

 /**
 * 删除节点p且平衡树
 * 对于有两个子节点的删除节点p，使用右子树的最小节点替换，
 * 然后根据这个最小节点是叶子结点就先修复再删除，若有一个右子树就使用右子树中节点与父节点连接
 * 对于有一个子节点的删除节点p，使用删除节点的子节点与父节点连接
 * 对于没右子节点就修复后再删除
 * @param p
 */
private void deleteEntry(Entry<K,V> p) {
    modCount++;
    size--;
    // If strictly internal, copy successor's element to p and then make p
    // point to successor.
    // 待删除结点有两个孩子用中序后继覆盖删除节点
    if (p.left != null && p.right != null) {
        // 返回p的右子树中的最小节点
        Entry<K,V> s = successor(p);
        // 将后继的键值覆盖删除点p的键值  没有更换颜色
        p.key = s.key;
        p.value = s.value;
        // 将p引用为后继节点 注意不是覆盖到删除节点 删除点p已经被替换为后继
        p = s;
    } // p has 2 children

    // Start fixup at replacement node, if it exists.
    // 如果删除节点只有一个孩子就返回这个孩子。注意如果进入上一个if，返回的p如果是叶节点，即replacement=null
    // p如果不是叶节点，只会存在右子节点
    Entry<K,V> replacement = (p.left != null ? p.left : p.right);
    // 删除节点存在一个子节点(左或右)，父节点链接删除节点的子节点
    if (replacement != null) {
        // Link replacement to parent
        // 连接p的父节点与替换节点  删除p
        replacement.parent = p.parent;
        if (p.parent == null)
            root = replacement;
        // 替换父节点的左链接
        else if (p == p.parent.left)
            p.parent.left  = replacement;
        // 替换右链接
        else
            p.parent.right = replacement;

        // Null out links so they are OK to use by fixAfterDeletion.
        p.left = p.right = p.parent = null;

        // Fix replacement
        // 只有删除点是BLACK的时候，才会触发删除修复，因为删除RED节点不会破坏红黑树的任何约束，而删除BLACK节点会导致有不同个数的黑色节点
        if (p.color == BLACK)
            fixAfterDeletion(replacement);
    }
    // 只有root一个节点
    else if (p.parent == null) { // return if we are the only node.
        root = null;
    }
    // 没有孩子节点 p是叶子结点
    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;
        }
    }
}

iterator方法：初步看了一下源码，类有点多，等到需要时再更新吧

first_edited_20171016