简介

TreeMap的继承实现关系图谱：

TreeMap是基于红黑树实现的一种map集合。
红黑树参考链接：https://blog.csdn.net/weixin_43598687/article/details/121732144

红黑树是天生支持排序的一种数据结构，TreeMap中默认情况下通过Key值的自然顺序进行排序。

public static void main(String[] args) {
        Map<Integer,String> treeMap = new TreeMap<>();

        treeMap.put(3,"three");
        treeMap.put(5,"five");
        treeMap.put(1,"one");
        treeMap.put(2,"two");
        treeMap.put(4,"four");

        System.out.println(treeMap);
    }

可以看到控制台中按TreeMap中key的自然顺序，打印出所有的键值对映射。

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

TreeMap继承至AbstractMap，并且实现了NavigableMap接口, Cloneable, java.io.Serializable，支持可复制以及序列化操作。
由于实现了NavigableMap接口，它也具有了为给定搜索目标报告最接近匹配项的导航方法。
NavigableMap解析：从源码分析SortedMap与NavigableMap

构造方法

在TreeMap中提供了多种构造方法，如下：

TreeMap()

使用其键的自然排序构造一个新的空TreeMap。

public TreeMap() {
        comparator = null;
    }

TreeMap(Comparator<? super K> comparator)

使用指定的比较器对其键排序，构造一个新的空TreeMap。

public TreeMap(Comparator<? super K> comparator) {
        this.comparator = comparator;
    }

TreeMap(Map<? extends K, ? extends V> m)

构造一个新的TreeMap，其中包含与给定map相同的映射，根据其键的自然顺序进行排序。

public TreeMap(Map<? extends K, ? extends V> m) {
        comparator = null;
        putAll(m);
    }

常用方法

int size()

返回此TreeMap中键值映射的数量。

public int size() {
        return size;
    }

V get(Object key)

返回到指定键所映射的值。

public V get(Object key) {
        Entry<K,V> p = getEntry(key);
        return (p==null ? null : p.value);
    }

boolean containsKey(Object key)

如果此映射包含指定键的映射，则返回 true 。

public boolean containsKey(Object key) {
        return getEntry(key) != null;
    }
    final Entry<K,V> getEntry(Object key) {
        // Offload comparator-based version for sake of performance
        if (comparator != null)
            return getEntryUsingComparator(key);
        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);
            if (cmp < 0)
                p = p.left;
            else if (cmp > 0)
                p = p.right;
            else
                return p;
        }
        return null;
    }

V put(K key, V value)

将指定的值与此映射中的指定键相关联。

public V put(K key, V value) {
        Entry<K,V> t = root;
        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;
        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);
        }
        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;
                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;
    }

void putAll(Map<? extends K, ? extends V> map)

将指定map的所有映射复制到此map。

public void putAll(Map<? extends K, ? extends V> map) {
        int mapSize = map.size();
        if (size==0 && mapSize!=0 && map instanceof SortedMap) {
            Comparator<?> c = ((SortedMap<?,?>)map).comparator();
            if (c == comparator || (c != null && c.equals(comparator))) {
                ++modCount;
                try {
                    buildFromSorted(mapSize, map.entrySet().iterator(),
                                    null, null);
                } catch (java.io.IOException cannotHappen) {
                } catch (ClassNotFoundException cannotHappen) {
                }
                return;
            }
        }
        super.putAll(map);
    }

V remove(Object key)

从该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;
    }

void clear()

从该map中删除所有的映射。

public void clear() {
        modCount++;
        size = 0;
        root = null;
    }

boolean containsValue(Object value)

如果此map将一个或多个键映射到指定的值，则返回 true 。

public boolean containsValue(Object value) {
        for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e))
            if (valEquals(value, e.value))
                return true;
        return false;
    }

Comparator<? super K> comparator()

返回用于比较此TreeMap的键的比较器。

public Comparator<? super K> comparator() {
        return comparator;
    }

K firstKey()

返回此TreeMap中当前的第一个（最低）键。

public K firstKey() {
        return key(getFirstEntry());
    }

K lastKey()

返回此TreeMap中当前的最后一个（最高）键。

public K lastKey() {
        return key(getLastEntry());
    }

Set keySet()

返回此map中包含的键的Set视图。

public Set<K> keySet() {
        return navigableKeySet();
    }
    public NavigableSet<K> navigableKeySet() {
        KeySet<K> nks = navigableKeySet;
        return (nks != null) ? nks : (navigableKeySet = new KeySet<>(this));
    }

Collection values()

返回此map中包含的值的Collection视图。

public Collection<V> values() {
        Collection<V> vs = values;
        if (vs == null) {
            vs = new Values();
            values = vs;
        }
        return vs;
    }

boolean replace(K key, V oldValue, V newValue)

仅当当前映射到指定的值时，才能替换指定键的条目。

public boolean replace(K key, V oldValue, V newValue) {
        Entry<K,V> p = getEntry(key);
        if (p!=null && Objects.equals(oldValue, p.value)) {
            p.value = newValue;
            return true;
        }
        return false;
    }

V replace(K key, V value)

只有当目标映射到某个值时，才能替换指定键的条目。

public V replace(K key, V value) {
        Entry<K,V> p = getEntry(key);
        if (p!=null) {
            V oldValue = p.value;
            p.value = value;
            return oldValue;
        }
        return null;
    }

Object clone()

返回此 TreeMap实例的浅拷贝：键和值本身不被克隆。

public Object clone() {
        TreeMap<?,?> clone;
        try {
            clone = (TreeMap<?,?>) super.clone();
        } catch (CloneNotSupportedException e) {
            throw new InternalError(e);
        }

        // Put clone into "virgin" state (except for comparator)
        clone.root = null;
        clone.size = 0;
        clone.modCount = 0;
        clone.entrySet = null;
        clone.navigableKeySet = null;
        clone.descendingMap = null;

        // Initialize clone with our mappings
        try {
            clone.buildFromSorted(size, entrySet().iterator(), null, null);
        } catch (java.io.IOException cannotHappen) {
        } catch (ClassNotFoundException cannotHappen) {
        }
        return clone;
    }

Map.Entry<K,V> firstEntry()

返回与该TreeMap中的最小键相关联的键值映射，如果TreeMap为空，则返回 null 。

public Map.Entry<K,V> firstEntry() {
        return exportEntry(getFirstEntry());
    }

Map.Entry<K, V> lastEntry()

返回与该TreeMap中的最大键相关联的键值映射，如果TreeMap为空，则返回 null 。

public Map.Entry<K,V> lastEntry() {
        return exportEntry(getLastEntry());
    }

Map.Entry <K,V> pollFirstEntry()

删除并返回与该TreeMap中的最小键相关联的键值映射，如果TreeMap为空，则返回 null 。

public Map.Entry<K,V> pollFirstEntry() {
        Entry<K,V> p = getFirstEntry();
        Map.Entry<K,V> result = exportEntry(p);
        if (p != null)
            deleteEntry(p);
        return result;
    }

Map.Entry <K,V> pollLastEntry()

删除并返回与该TreeMap中的最大键相关联的键值映射，如果TreeMap为空，则返回 null 。

public Map.Entry<K,V> pollLastEntry() {
        Entry<K,V> p = getLastEntry();
        Map.Entry<K,V> result = exportEntry(p);
        if (p != null)
            deleteEntry(p);
        return result;
    }

Set<Map.Entry<K,V>> entrySet()

返回此map中包含的映射的Set视图。

public Set<Map.Entry<K,V>> entrySet() {
        EntrySet es = entrySet;
        return (es != null) ? es : (entrySet = new EntrySet());
    }

从源码分析TreeMap

简介