Java-01-源码篇-04集合-05-SortedMap NavigableMap TreeMap

一，SortedMap

二，NavigableMap

三，TreeMap

3.1 TreeMap 继承结构

3.2 TreeMap 属性

3.3 TreeMap 构造器

3.4 TreeMap 内部类

3.4.1 Values

3.4.2 KeySet

3.4.3 EntrySet

3.4.5 相关集合迭代器

3.4.5.1 PrivateEntryIterator 迭代器

3.4.5.2 ValueIterator 迭代器

3.4.5.3 KeyIterator 迭代器

3.4.5.4 EntryIterator 迭代器

3.4.5.5 DescendingKeyIterator 倒排 key 迭代器

3.4.6 相关子集Map

3.4.7 相关分割器

3.4.8 Entry 映射实体类（红黑树节点）

3.5 TreeMap 新增业务

3.5.1 put(key, value)

3.5.2 putIfAbsent(key, value)

3.5.3 put(key, value, replaceOld)

3.5.4 addEntryToEmptyMap(key, value)

3.5.5 addEntry(key, value, parent, addToLeft)

3.6 TreeMap 删除业务

3.6.1 remove(key)

3.6.2 deleteEntry(e)

3.7 TreeMap 查询业务

3.8 TreeMap的 NavigableMap 的 lowerEntry(key)

2.9 TreeMap 与 HashMap 区别

一，SortedMap

SortedMap 是 Java 中 Map 接口的一个子接口，它提供一些额外的方法来处理有序的简直对映射。SortedMap 保证键以自然顺序或指定的比较器顺序排序。其接口方法源码如下：

package java.util;

/**
 * @since 1.2
 */
public interface SortedMap<K,V> extends Map<K,V> {
    /** 用于对键进行排序的比较器。如果使用键的自然顺序进行排序，则返回 null */
    Comparator<? super K> comparator();

    /** 
     * 获取一个子映射[fromKey, toKey)，用于处理特定范围的键值对 
     * @param fromKey    
     * @param toKey     
     */
    SortedMap<K,V> subMap(K fromKey, K toKey);

    /**
     * 获取所有键小于 toKey 值的子映射
     */
    SortedMap<K,V> headMap(K toKey);

    /**
     * 获取所有键大于等于 fromKey值 的子映射
     */
    SortedMap<K,V> tailMap(K fromKey);
    
    /** 返回当前映射中第一个（最小的）键。 */
    K firstKey();

    /** 返回当前映射中最后一个（最大的）键 */
    K lastKey();

    /** 返回一个包含此映射中所有键的 Set 视图。集合中的键按照升序排列 */
    Set<K> keySet();

    /** 返回一个包含此映射中所有值的 Collection 视图。集合中的值按照对应键的升序排列。*/
    Collection<V> values();

    /** 返回一个包含此映射中所有键值对的 Set 视图。集合中的条目按照键的升序排列 */
    Set<Map.Entry<K, V>> entrySet();
}

SortedMap 提供了一些用于处理有序键值对映射的额外方法，这些方法允许你获取子映射、获取特定范围的映射，以及按顺序访问键、值和键值对。

二，`NavigableMap`

NavigableMap 是 Java 集合框架中的一个接口，扩展了 SortedMap 接口，提供了导航方法来检索按顺序映射的键及其关联的值。它允许更灵活地处理键和值，并提供了查找最接近的匹配项的方法。

NavigableMap 主要用于处理有序键值对，并提供了额外的导航方法，例如获取最接近的键，逆向视图等。与 SortedMap 不同， NavigableMap 提供了更丰富的方法集，使得更加灵活的操作有序映射。其接口源码如下：

package java.util;

/**
 * @author Doug Lea
 * @author Josh Bloch
 * @param <K> the type of keys maintained by this map
 * @param <V> the type of mapped values
 * @since 1.6
 */
public interface NavigableMap<K,V> extends SortedMap<K,V> {
    /************************** 基本导航方法 **************************/
    /**
     * 查找 小于 指定键的最大键值的键值对映射，如果没有返回 null
     * @param key the key
     * @return 
     * @throws ClassCastException
     * @throws NullPointerException
     */
    Map.Entry<K,V> lowerEntry(K key);

    /**
     * 查找 小于 指定键的最大键值，如果没有返回 null
     *
     * @param key the key
     * @throws ClassCastException
     * @throws NullPointerException
     */
    K lowerKey(K key);

    /**
     * 查找 小于或等于 指定键的最大键值对，如果没有返回 null
     *
     * @param key the key
     * @throws ClassCastException 
     * @throws NullPointerException
     */
    Map.Entry<K,V> floorEntry(K key);

    /**
     * 查找 小于或等于 指定键的最大键
     *
     * @param key the key
     * @throws ClassCastException 
     * @throws NullPointerException
     */
    K floorKey(K key);

    /**
     * 查找 大于或等于 指定键的最小键值对，如果没有返回null
     *
     * @param key the key
     * @throws ClassCastException 
     * @throws NullPointerException
     */
    Map.Entry<K,V> ceilingEntry(K key);

    /**
     * 查找 大于或等于 指定键的最小键。
     *
     * @param key the key
     * @throws ClassCastException 
     * @throws NullPointerException
     */
    K ceilingKey(K key);

    /**
     * 查找 大于 指定键的最小键值对。
     *
     * @param key the key
     * @throws ClassCastException
     * @throws NullPointerException 
     */
    Map.Entry<K,V> higherEntry(K key);

    /**
     * 查找 大于 指定键的最小键
     *
     * @param key the key
     * @throws ClassCastException 
     * @throws NullPointerException 
     */
    K higherKey(K key);

    /************************** 最小和最大方法 **************************/
    /**
     * 获取映射中的第一个键值对
     * @return 返回映射中的第一个（键的最小）键值映射，或返回 null 如果映射为空
     */
    Map.Entry<K,V> firstEntry();

    /**
     * 返回映射中的最后一个（键的最大）键值映射，或返回 null 如果映射为空。
     * @return 获取映射中的最后一个键值对
     */
    Map.Entry<K,V> lastEntry();

    /**
     * 移除并返回映射中的第一个（键的最小）键值映射，或返回 null 如果映射为空
     * 简单理解：删除并返回映射中的第一个键值对。
     */
    Map.Entry<K,V> pollFirstEntry();

    /**
     * 移除并返回映射中的最后一个（键的最大）键值映射，或返回 null 如果映射为空。
     * 简单理解：删除并返回映射中的最后一个键值对
     */
    Map.Entry<K,V> pollLastEntry();

    /************************** 视图操作 **************************/
    /** 获取映射的键按逆序排列的视图。 */
    NavigableMap<K,V> descendingMap();

    /** 获取所有键的 NavigableSet 视图 */
    NavigableSet<K> navigableKeySet();

    /** 获取所有键的逆序 NavigableSet 视图 */
    NavigableSet<K> descendingKeySet();

    /************************** 子映射操作 **************************/
    /**
     * 返回键在 fromKey 到 toKey 范围内的子映射，是否包含边界由 fromInclusive 和 toInclusive 决定。
     * @param fromKey 子映射集合的起点
     * @param fromInclusive 子映射是否包含起点 true - 包含 | false - 不包含
     * @param toKey high 子映射集合的终点
     * @param toInclusive 子映射是否包含终点 true - 包含 | false - 不包含
     * @throws ClassCastException 
     * @throws NullPointerException 
     * @throws IllegalArgumentException 
     */
    NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
                             K toKey,   boolean toInclusive);

    /**
     * 返回键小于（或等于，如果 inclusive 为 true）toKey 的子映射
     * @param toKey 子映射集合的终点
     * @param inclusive 子映射是否包含终点 true - 包含 | false - 不包含
     * @throws ClassCastException
     * @throws NullPointerException
     * @throws IllegalArgumentException
     */
    NavigableMap<K,V> headMap(K toKey, boolean inclusive);

    /**
     * 返回键大于（或等于，如果 inclusive 为 true）fromKey 的子映射
     * @param fromKey 子映射集合的起点
     * @param inclusive 子映射是否包含起点 true - 包含 | false - 不包含
     * @throws ClassCastException 
     * @throws NullPointerException 
     * @throws IllegalArgumentException
     */
    NavigableMap<K,V> tailMap(K fromKey, boolean inclusive);

    /************************** SortedMap 兼容方法 **************************/
    /**
     * 等价于 subMap(fromKey, true, toKey, false)
     * @throws ClassCastException       {@inheritDoc}
     * @throws NullPointerException     {@inheritDoc}
     * @throws IllegalArgumentException {@inheritDoc}
     */
    SortedMap<K,V> subMap(K fromKey, K toKey);

    /**
     * 等价于 headMap(toKey, false)
     * @throws ClassCastException       {@inheritDoc}
     * @throws NullPointerException     {@inheritDoc}
     * @throws IllegalArgumentException {@inheritDoc}
     */
    SortedMap<K,V> headMap(K toKey);

    /**
     * 等价于 tailMap(fromKey, true)
     * @throws ClassCastException       {@inheritDoc}
     * @throws NullPointerException     {@inheritDoc}
     * @throws IllegalArgumentException {@inheritDoc}
     */
    SortedMap<K,V> tailMap(K fromKey);
}

NavigableMap 的这些方法使得对有序映射的操作更加灵活和方便，可以轻松实现查找、子集和导航等操作。Java 中的 TreeMap 是 NavigableMap 接口的一个常见实现

三，TreeMap

TreeMap 是 NavigableMap 的子类，并且是一颗通过红黑树实现 NavigableMap。

3.1 TreeMap 继承结构

package java.util;
public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable
{/** 忽略代码 */}

3.2 TreeMap 属性

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

    /** 比较器，用于 key 排序 */
    @SuppressWarnings("serial")
    private final Comparator<? super K> comparator;

    /** TreeMap 的根节点，毕竟是一颗红黑树 */
    private transient Entry<K,V> root;

    /** 当前 TreeMap 的元素数量大小 */
    private transient int size = 0;

    /** 当前集合修改次数 */
    private transient int modCount = 0;

    /** 忽略其他代码 */
}

3.3 TreeMap 构造器

【无参构造】默认指定比较器，默认使用key的自然排序

    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);
    }

【单参构造】指定SortedMap 元素集进行构造，并且直接使用 SortedMap的比较器

    public TreeMap(SortedMap<K, ? extends V> m) {
        comparator = m.comparator();
        try {
            buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
        } catch (java.io.IOException | ClassNotFoundException cannotHappen) {
        }
    }

3.4 TreeMap 内部类

3.4.1 Values

Values 是 TreeMap 中所有 value 的视图集合。

3.4.2 KeySet

KeySet 是 TreeMap 中所有 key 的视图集合，类型为 Set 集合，原因是 key 是不允许有重复的；该类还实现NavigableSet 意味着同样丰富的导航视图方法

3.4.3 EntrySet

key 有对应的视图，value 也有对应的视图，剩下就是key-value 的映射键值对没有对应的视图，所以EntrySet 就是 TreeMap 中所有映射键值对的视图集合。但是 TreeMap 本身就不是一个映射键值对的集合吗？为什么其内部还要在追加一个 EntrySet 视图集合？？？ EntrySet 视图集合的重点在于视图，一般视图都是重点在可读，也就是在迭代，查询等业务中使用到的。有一些特殊情况，也会提高一两个写的方法。比如下面的删除。

3.4.5 相关集合迭代器

3.4.5.1 PrivateEntryIterator 迭代器

privateEntryIterator 迭代器，是 TreeMap 所有迭代器的基类。

3.4.5.2 ValueIterator 迭代器

value 的迭代器，直接逐个迭代到最后一个为止